hocky's blog

By hocky, 5 weeks ago, In English

logo

Hi Codeforces ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!

We're delighted to invite you to COMPFEST 13 — Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) on .

All problems were written and prepared by hocky, steven.novaryo, rama_pang, JulianFernando, Zap, Panji, richiesenlia, Sakamoto, and markus_geger.

I would also like to thank:

  • KAN for helping to host the mirror round;
  • (AVM.Martin, Ace_02), Berted, ardan, wijayareynaldo, and bukanYohandi for testing the round locally and improved the problems in early phases;
  • UWr Kobor 53 (w0nsh, kobor, Fly_37), Almost Retired (KAN, Um_nik, Ekler), and errorgorn for testing the round and their really useful feedbacks;
  • Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
  • prabowo for observing the contest;
  • fushar for the Judgels platform used in the official contest; and finally
  • MikeMirzayanov for the great Codeforces and our lovely Polygon!
  • Extra thanks for rama_pang and steven.novaryo for working hard night 🌚 and day 🌞 making sure the problems are well-prepared (the contest wouldn't exist without their hands).

The duration will be 5 hours, consisting of 13 problems. You can register individually, but teams are preferred. You may expect relatively easier problems than ICPC Regional Contests. You may code parallely with several computers with your teammates and use prewritten codes and templates.

COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.

We've put great effort into preparing this contest and we hope that you will enjoy it. See you! ありがとう~! 🐾

UPD: Editorial is out!!! Editowial UωU

Congratulations to our top 5!

  1. leziren (Retired_MiFaFaOvO, TLE, Miracle03)
  2. heno239
  3. bubble (riantkb, nuip, mtsd)
  4. gisp_zjz
  5. We Won it 0 time (aarr, afterall, Amoo_Safar)
 
 
 
 
  • Vote: I like it
  • +418
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How did you add emojis in the blog?

Everytime it says:-

Emoji (and other unusual UTF-8 characters) are not supported

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    🤔

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      How was the contwest UωU? I thought pweople would find K easiew than othews easy pwoblems (ಥ﹏ಥ)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it +8 Vote: I do not like it

        I would have liked harder problems (what I mean is that the phase of read+routine work+implement lasted a bit longer than I'd've liked, not that there weren't also hard problems).

        K is probably scoreboard effect (combined with a sneaky special case).

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          I see.. Thank you for the feedback!

          We were trying to fit in such vary skill range in our official contest. Hope you liked the problems ^^🐾~!

»
3 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Looking forward for exciting problemset! °(ಗдಗ。)°

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Somehow they're all during school :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very colourful post,indeed:)

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

You guys should have made this rated event like div1,2 combined round etc...

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

You may expect relatively easier problems than ICPC Regional Contests. this gives hope to look farward

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

As a participant of the official contest, i can say that the problemset quality is good with really diverse problems

»
3 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

As a tester, I'd say good luck and have fun!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I support this competition very much and hope to get contributions.

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

The problems in previous round were of the level of div 1.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve L ?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    You can formulate the problem as a 2D LIS, that can be solved with CDQ D&C.

    Implementation

    UPD: why downvotes? The solution is overkill, but the implementation is easy.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Maintain a vector(say track) of pairs {$$$i-a[i],a[i]$$$}. Sort it. Make an array b such that $$$b[i]=track[i].s$$$ . Find LIS of b.

    Link to submission.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C, F, M?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like it

    M: It is just convex hull. We solve each column seperately. Note that the cost are independent for column and row. So we for each row, we find the best pole that minimize the sum for that specific. Then we just put everything inside a convex hull.

    code: 130595020

    C: perhaps i overcomplicated but let the sum a single array be $$$tot$$$. Then then $$$pref$$$ be the prefix sum array, we want some condition like $$$pref[r]-pref[l]=0$$$ or $$$tot+pref[r]-pref[l]=0$$$ or $$$2 \cdot tot + pref[r]-pref[l]=0$$$ etc.

    Since $$$k$$$ is a prime, we can store the prefix in a order that makes $$$0,tot,2 \cdot tot, \ldots$$$ appear contiguously.

    You can probably modify this for non-prime as well using some sort of binary lifting thing. Details left as exercise to reader.

    code: 130595163

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

will be editorial available?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The editorial will be posted soon

»
3 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

why K so low accepteds?

this fact, as well as useless constraint for r and c, gives me suspicious this solution 130590785 is wrong

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

How do you solve G?

»
3 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Can't imagine such high ratio of sucessfully hacking on problem D.I hacked 30 codes in total:-)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what case did you use ?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      a string with leading zeros

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        like 0025 what is your expected output ?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          0

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            i guess this should have been mentioned in the question that the string is not having leading zeroes by itself its just sad :(

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Yes i also thought that, because they mentioned it will be given as integer representation. But don't know actually either 00025 is a integer representation or not. Can anyone tell me that?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                Rev. 2   Vote: I like it +16 Vote: I do not like it

                My intended solution was like this.

                I've added the fifth sample to solve this ambiguity in the future.(ಥ﹏ಥ)

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

MikeMirzayanov

Please update problem ratings as there is no need for plag-check in this round. Thanks in advance.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Retired_MiFaFaOvO came out of retirement?