nishit.sharma's blog

Invitation to InfInITy 2k21 (Rated For Div 2 & Div 3)
By nishit.sharma, history, 3 years ago, In English

Hello Codeforces !!

I, on behalf of the InfInITy Team, would like to invite you to take part in the 5th edition of IIIT Pune's flagship coding event InfInITy 2k21, a rated contest hosted by CodeChef IIITP Chapter, which will take place on Wednesday, December 22, 2021, at 20:00 ISTUTC+5.5. It is a 3 hr long contest.

The contest is Rated for Div. 2 and Div. 3 on Codechef, but Div. 1 coders are encouraged to participate unofficially as there are prizes for top participants in combined(Div. 1 + Div. 2) ranklist. We'd be offering you 8 problems in Div 2 and 7 problems in Div 3 with varying difficulties.

CASH PRIZES  :

  • Top 3 performers  (Div1 + Div 2 combined)  will be awarded cash prize of INR 10000, 7000 & 3000 respectively. Top performer of Div3 will be awarded INR 2000.
  • Top 2 Indian participants will be rewarded INR 4000 & 2000 respectively(for Div1 + Div2 participants).
  • Prizes worth INR 10000 specially for IIIT Pune students.

Contest Link : www.codechef.com/INFI2021
Contest Timing : 20:00 to 23:00 IST
Registration For Prizes : Infinity Website or Google Form

I would really like to thank:

For any queries contact: [email protected]
Editorials for all the questions will be posted shortly after the contest ends!.

Past problem sets for the event: 2020, 2019

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below, after the contest.

UPD: Congratulations to the winners.

Div 1 + 2:

  1. tourist

  2. Geothermal

  3. kal013

Div 3:

  1. hit6646

  2. taoran_chen

  3. piccacu

All editorials have been published on codechef discuss.

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

Comments Comments (41)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How do prizes for top 3 in "div1+2" work if the divisions have separate contests on CodeChef? Will the problems be identical so you can manually merge the rankings?

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

    Yes, div1 and div2 will have the same problems and the winners will be decided after merging the rank lists

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

what is meant by the top 2 Indian participants in : "Top 2 Indian participants will be rewarded INR 4000 & 2000 respectively."? because the questions will be different for div1/div2 from div3..

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

    The only prize for div 3 participants is the overall Div 3 winner. All other prizes are for Div1 + Div2 participants. Updated the blog as well. Apologies for the confusion.

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

Reminder: The contest begins in 10 minutes. Join Here

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

Cheating has been started, just look how fast number of successful submission is increasing for "Marbles" problem in div.3. Please do something about it.

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

    This part of the MARBLE problem statement was likely intended as a joke, but there's a grain of truth in every joke:

    "Sang-Woo is the more intelligent one between them, and he plans to win the game by cheating."

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

Nice problems. Thanks for the contest. :)

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

Too Hard For me to solve even B

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

5 seconds late to figure out the frustrating edge case of Ddakji. :(

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

    I think the solution to this problem has to have a greedy approach, and lots of things to do with GCD. or, Maybe I'm completely wrong.

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

      You are right. If there are only 1 positive or negative number, it would've made things a little trickier since they can't be reduced.

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

For problem hopscotch, it makes no sense why the answer for the first testcase of the sample is $$$0$$$. Do you think that $$$(0!)=0$$$? We can literally count $$$1$$$ way in the problem to assign things.

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

    I am sorry, I should have taken care of this. I made an error.

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

When will problems be available for practice?I need to check my code to the last problem which I missed submitting by a few seconds

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

It was a nice contest. But I really hated solving Dalgona Treat

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

I felt this contest to be on the tougher side. It would have been a very good Div1.5 round.

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

What will be the answer for Ddakji for the case {1, 2, -3}? Accepted codes show 2 which I cant seem to get to :(

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

    {1,2,-3} -> {1,1,-3} -> {1,0,-3} -> {1,-1,-3} -> {1,-1,-2} -> {1,-1,-1} -> {1,-1,0}

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

      I totally forgot zeroes could be used as i lol :(

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

That was a really nice problems.

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

Found the problems pretty interesting. I was only able to solve Marbles and Tug of War. Could you guys please discuss your solutions for Dalgona treat, Hopscotch and Ddakji?

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

    Hopscotch :

    Hint

    Dalgona Treat :

    Hint

    Ddakji :

    Cant solve, but basic idea
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For hopscotch, u can use inclusion-exclusion. First find out the the common elements between the indices that are 0 and indices that are assigned. Now we want to calculate number of ways to permute such that exactly 0 elements match their positions.

    Now find the number of ways such that at least 0 elements match their positions. Then subtract the number of ways such that at least 1 element match their positions. Now the number of ways such that at least two elements match has been subtracted twice. So you add it. Similarily we just have to add for even numbers and subtract for odd numbers. Code

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

    I found Hopscotch problem to be very similar to E — Rook Path from the recent AtCoder ABC contest and this helped. Both problems are counting the number of ways to do something and both can be solved by a recursive DP.

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

I solved the problem Hopscotch using dp. If anyone is interested, you can refer to my submission:- Link:- https://www.codechef.com/viewsolution/55287667

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

    Please explain your approach

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

      What I did was that I separated the elements into two groups. Group 1:- contains those elements which don't have their mannequins and they are also not part of someone else's mannequin. Group 2:- Contains those elements which don't have their mannequins but are part of someone else's mannequin.

      For example for this testcase:- 3 6 1 0 0 0 Grp 1:-
      4 5(mannequin)
      4 5(element)

      Grp2:- 2(mannequin) 6(element)

      Now, let's say there are i elements in total who don't have their mannequins. And same elemets which belong to grp 1 and diff(i-same) elements which belong to group 2.->refer to my code .

      le's define dp[i][same]->answer in which there are i elements who dont have mannequins out of which same elements belong to grp1. now,we can make transitions like dp[i][same]=dp[i-1][same-2]*(same-1)(case in which an element of grp 1 is paired with an element of grp1 only)+dp[i-1[same-1]*(diff or (i-same))(case in which an element of grp 1 is paired with an element of grp2). There are some minor implementation details(for handling edge cases). You can refer to gfg blog finding derrangements using dp for better understanding. Link:- https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/

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

I enjoyed the contest and problems, other than the prizes were not for top5. :'(

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

    Thats great to hear. With each passing year he contest is growing a lot. We will try to get in more sponsors, to offer even better range of prizes for our participants :)

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

I don't see rating changes for me, but there are other people in the rank list whose ratings are changed basically I see there are few people who are 3 stars but then rating on the right side is 2 stars.

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

    It happens when they are updating the ratings. Check after 40-50 minutes, everything will be correct.

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

Time limit for TUG OF WAR (TOW) was very tight. My solution without using decreasing stack didn't pass as it had vectors and maps even though my solution was correct, but when I optimized it with stack and removed a vector which kept track of removed elements of b and the suffix max vector, it passed.
I think Authors should have kept $$$ N,M <= 5e5 $$$ so that such solution's can easily pass
Tle
AC with decreasing stack

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

    I think the lesson here is more about unordered_maps being sometimes slower than sorting. Yes O(n) is better than O(n*log(n)) but there are big constants. And look at quick solutions ~0.30sec. They just sorted array of B. Even python solution with sorting B are getting accepted in 0.8sec

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

      I used unordered_map mentioned by neal in this blog which is optimized in case of many collisions
      And I never faced any issue of TLE when using this unordered_map as they are better than ordinary map

      And my point is that the main overhead was because of vectors that I used for keeping track of suffix maximum and the arr2 which stored the removed elements. And generally for a div2 problem C it should not be forced to use only one vector, they should allow to pass different implementations
      I maybe wrong but that's what I have observed from the time I started CP

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

Auto comment: topic has been updated by nishit.sharma (previous revision, new revision, compare).

→ Reply