hocky's blog

By hocky, 3 years 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, yz_, 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 (jqdai0815, TLE, Rewinding)
  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

| Write comment?
»
2 years 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

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

    🤔

    • »
      »
      »
      2 years 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 (ಥ﹏ಥ)

      • »
        »
        »
        »
        2 years 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).

        • »
          »
          »
          »
          »
          2 years 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 ^^🐾~!

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very colourful post,indeed:)

»
2 years 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...

»
2 years 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

»
2 years 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

»
2 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve L ?

  • »
    »
    2 years 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.

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C, F, M?

  • »
    »
    2 years 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

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

will be editorial available?

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

    The editorial will be posted soon

»
2 years 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

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How do you solve G?

»
2 years 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:-)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what case did you use ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      a string with leading zeros

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        like 0025 what is your expected output ?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          0

          • »
            »
            »
            »
            »
            »
            2 years 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 :(

            • »
              »
              »
              »
              »
              »
              »
              2 years 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years 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.(ಥ﹏ಥ)

»
2 years 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.