vishesh312's blog

Invitation to Exun 2021-22 (Rated for Div.2 & Div.3)
By vishesh312, 3 years ago, In English

Hello, Codeforces!

We would like to invite you all to participate in the Exun 2021-22 Competitive Programming contest this Wednesday, 12th January 2022 from 8 PM to 11 PM IST.

The contest is rated for both division 2 and 3. Participants of division 1 are also encouraged to participate unofficially to get a chance for prizes. The contest, authored by me and halemon123, will feature 7 problems in all divisions.

I would like to thank:

Participants have to be registered here to be eligible for the following:

  • From the Division 1 & 2 combined rank list:
    • Top 3 school students will receive cash & sponsor prizes.
    • Top 25 school students will be awarded certificates.
    • Top 8 Indian school students will qualify for Lockout.
    • Top 16 Indian school students will qualify for Challenge Programming.
  • Top 25 school students from the Division 3 rank list will be awarded certificates.

The event is a part of our annual tech symposium Exun 2021-22. If you're interested in participating in other technical events, such as Machine Learning and Hackathons, please check out our invite!

We hope you enjoy solving the problems, good luck!

UPD: The editorials are available here.

  • Vote: I like it
  • +50
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

nice yaar blobsmiley agooglethumbsup

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Feels good to see Indian school fests consisiting of CP events. I wish it was a thing when I was in high-school. Anyways, good luck guys :D

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Great problems! Thank you for the contest!

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Nice problems. I really liked MAKEODD.

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve GOODBINTREE ?

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Thanks for the contest! CIRCLEGAME and MAKEODD are some of the best problems I've seen in recent ERCs and Starters.

GRIDXOR — Cute troll cakewalk. I actually re-read the statement multiple times double and triple checking that just printing 1 everywhere would work.

SUMPARITY — Fairly easy but nice problem, pretty good for the position.

CIRCLEGAME — Brilliant problem. I had zero intuition that the answer for $$$i$$$ people could be obtained from the answer for $$$i - 1$$$ people when I first saw it, but it was really cool when it finally struck me.

RAINDROPS — Fairly obvious that the answer is going to be based purely on the number of leaves at each depth, but nice problem anyway.

GOODBINTREE — Fairly direct subtree dp + prefix sums, but fine for a rated for Div2 + Div3 ERC I guess.

MAKEODD — At first I thought this problem was just boring subarray dp where the answer for a subarray was the number of different non-zero trailing bits in it. Looking at the number of WAs in Div1 I suspect many others made the same mistake. I broke my head trying all sorts of ways to calculate the min cost for a mask doing all sorts of weird stuff that I couldn't prove the complexity of, before realizing I was being an idiot and the answer was trivially computable from smaller masks using some simple bitwise operations.

PRIMESETMUL — Ran out of time and couldn't make any inroads into the problem, so no comments here.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Thank you for the feedback, really appreciate this!

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    I really liked the problem CIRCLEGAME as well.

    I couldn't debug MAKEODD even after spending almost 2 hours on it.Does anyone have a testcase on which this submission doesn't work?.I made a total of 14 submissions in contest .Solution idea is correct though.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Your code fails on this case:

      1
4
32178 2304 29504 784

      My code prints 19, yours prints 20. Should be fairly easy to manually check the subarrays for this and see which one you're solving suboptimally.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Thanks a lot for this test case. I was literally scratching my head for 2 hours. I was only considering set bits for operations.

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

      You don't have to consider only set bits to perform operation on mask

      https://www.codechef.com/viewsolution/56343428 (replaced ss[k] with k from 0 to nn — 1)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You don't have to consider only set bits to perform operation on mask

        Oh yeah, I didn't realize he wasn't doing that, here is a simple case for anyone who wants.

        $$$[2^1, 2^3, 2^8, 2^{10}]$$$

        Choose $$$Y = 2^7$$$.

        $$$[2^1, 2^3, 2^1, 2^3]$$$

        Choose $$$Y = 2^1$$$.

        $$$[2^0, 2^3, 2^0, 2^3]$$$

        Choose $$$Y = 2^3$$$.

        $$$[2^0, 2^0, 2^0, 2^0]$$$.

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

        Thanks a lot for pointing out the bug

        → Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The problems were nice. But the statement of GOODBINTREE was ambiguous : \

I initially interpreted "Nodes at even levels have values strictly more than their parents' values" as even level nodes requiring greater values than the all parents' values in the previous level. I'd still consider this as a valid interpretation; the statement should have been something like:

'For each node on even levels, its value should be strictly more than its parent'.

The sad part is, both interpretations also conform the the single sample provided. I spent most of the contest trying to debug my code.

Either providing more than 1 sample or a single larger sample would have worked, even with the statement issue : (

Otherwise a nice set.

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

    I agree the statement could have been written better. Thanks for participating!

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

Thanks for the contest!

I managed to win the division 2 contest, solving all problems except MAKEODD (somehow I was able to get the only div2 solve of PRIMESETMUL)!

I've uploaded my solutions at https://www.youtube.com/watch?v=pLXLvKNAm_U , including the intuition I used to derive my solutions!

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I especially liked the problem PRIMESETMUL. Initially, I (incorrectly) guessed that the answer wouldn't be that big, and wrote a brute-force backtracking program which worked for $$$N = 10$$$. Then, applying meet in the middle was obvious. Beautiful problem!

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

MAKEODD was great! btw, does "school students" imply high school students, not university ones?

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

    It implies high school students, we apologize for the ambiguity.

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The editorials are out now!

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The smooth troll in GRIDXOR xD. Was a well-balanced contest. :D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's interesting that two of my unsuccessful RAINDROPS attempts got TLE failures on different sets of testcases:

  • 56338380 (AC for everything except test #4)
  • 56337536 (a few TLEs, but AC for test #4)

This in principle allowed a combined "frankensteiner" solution (two different code paths and a simple heuristics to make a choice between these two code paths, in such a way that TLE problems can be dodged). This is ugly, but provides a chance to score additional points if people manage to take advantage of it.

For comparison, Codeforces does not provide detailed information about failed testcases and I think that this is a good decision. Moreover, passing pretests during Codeforces contests does not guarantee anything. System tests are always a threat and this discourages implementing shoddy half-baked solutions. The existence of 12 hours hacking after educational rounds is another great Codeforces feature.

→ Reply