Codeforces Round #902 (Div. 1, Div. 2, based on COMPFEST 15 — Final Round)

Sugeng enjing, Codeforces! 🥰🥰🥰🥰

COMPFEST 15 is happy to invite you to participate in Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round) and Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round) on Sunday, October 8, 2023 at 09:05UTC. Both rounds will be rated. You will be given 2 hours and 30 minutes to solve 7 problems.

Note the unusual time of the round.

The problems are written by ArvinCiu, Pyqe, and nandonathaniel.

We would like to thank:

• KAN for helping to host the round;
• errorgorn and ScarletS for the based coordination;
• gansixeneh and nandonathaniel for helping with the problem preparation;
• ArvinCiu, CyberSleeper, and Edbert.H for providing alternate solutions in the early stages;
• Alexdat2000 for writing the Russian translations;
• Aaeria, AMnu, Berted, BucketPotato, buffering, Drew_, dorijanlendvaj, eggag32, Elben85, emorgan5289, faustaadp, ffao, fishy15, flamestorm, gamegame, hocky, Insta-x, jdurie, joelgun14, KerakTelor, Marky, Murinh0, nvmdava, nyab, Owmicron, prvocislo, PurpleCrayon, rama_pang, TakeMe, sahil_k, user202729_, Vladithur, WHCPP, and ZeroScar for testing the contest and providing us very useful feedback;
• Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
• MikeMirzayanov for the amazing Codeforces and Polygon platform!

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 hope you will enjoy and have fun in the contest. Muga-muga beja lan isa entuk biji apik!! 💪💪🔥🔥

UPD: Scoring distribution

• Div. 1: 500 — 1000 — 1250 — 1750 — 2250 — 2750 — 3250
• Div. 2: 500 — 1000 — 1500 — 2000 — 2500 — 2750 — 3000

UPD2: Contest is over!

Congratulations to our winners!

Congratulations for our first solvers:

We will try to post the editorials as soon as possible. Please stay tuned!

UPD3: Editorial

On behalf of the COMPFEST committees, we are glad that our Codeforces Round ran quite smoothly and we hope that you all enjoyed our problems. See you next year! 😍😍

• 3 months ago, # ^ | Thank you ScarletS for carrying

• 3 months ago, # ^ | rfpermen will win COMPFEST 15!

  • 3 months ago, # ^ | rfpermen will win COMPFEST 15!

    • 3 months ago, # ^ | rfpermen will win COMPFEST 15!

      • • 3 months ago, # ^ | How come you guys are so sure?

• 3 months ago, # ^ | Thank you Pyqe for carrying

  • 3 months ago, # ^ | Thank you Pyqe for carrying

    • 3 months ago, # ^ | Thank you Pyqe for carrying

      • 3 months ago, # ^ | Thank you Pyqe for carrying

        • 3 months ago, # ^ | ← Rev. 2 →   -15 Thank you Pyqe for carrying

          • 3 months ago, # ^ | Thank you Pyqe for crying

            • 3 months ago, # ^ | ← Rev. 2 →   0 Thank you Pyqe for carrying

              • 3 months ago, # ^ | Thanks for creating these ladders!

              • 3 months ago, # ^ | Thank you Pyqe for carrying

• 3 months ago, # ^ | The round is based. Actual answer

• 3 months ago, # ^ | It's Javanese (a local language in Indonesia) meaning "good luck and have a good score" :D

• 3 months ago, # ^ | Certainly I agree with your idea. The unusual time is unfriendly for both Chinese and Americans. For Americans, it seems harder to wake up so early. And for Chinese, there was a National Day holiday until 6th so we had to go to school or work. We are still studying or working at 17:05. However, I can accept the usual time, 22:35 because I am allowed to stay up late at my dormitory.

• 3 months ago, # ^ | "good luck and have a good score"

• 3 months ago, # ^ | Isn’t that the same thing?

• 3 months ago, # ^ | There is still some time left to reschedule the icc world cup, let them know.

• 3 months ago, # ^ | haha same

• 3 months ago, # ^ | ← Rev. 2 →   +1 Just iterate over every maximum value from to . Then, let's say = "count of indices that needs to be colored black to get a maximum of " and = "count of indices that when colored black gives a maximum value less than ". Then, the contribution for would be . Answer is the sum of over all .

  • 3 months ago, # ^ | isn't it Cg = 2^y*(2^x — 1) => 2^(x+y) — 2^y ???

    • 3 months ago, # ^ | Yeah, my bad.

• 3 months ago, # ^ | You can use the following formula . RHS means for given x, frequency of elements which are greater than or equal to x.

• 3 months ago, # ^ | It will be quite hard to explain. Wait for an editorial.

• 3 months ago, # ^ | ← Rev. 2 →   +9 If we select any index i to make it black we can replace arr[i] with the maximum value at any index j, such that i is a factor of j (because we would always be marking all such j green). Then we can sort the resulting array, and now for the maximum element to be Kth from this array, we have 2^(k-1)*arr[k] possibilities, we can just calculate this sum for all the elements from 1 to n in the sorted array and take the remainder which would give the ans.

• 3 months ago, # ^ | I'll explain my solution, maybe not most efficient. Basically, for each idx we go to the right with step idx to find the maximum value that this idx can lead to after coloring. It is similar to how we use of sieve of eratosthenes, although in our case we do it for every idx, not skipping already visited before. (Let's say idx == 2, we're going to check idxs 2, 4, 6, 8,... and store max value of them. For idx == 4 we're going to check 4, 8, 12,...) After that we create dictionary value -> amount of idxs (that lead to that value after coloring them with black) And starting with greates value to lowest, you have value: amount of idxs. Let's say v: k. And let's say amount of possible numbers to choose from is n (it's n in the beginning). Amount of subsequences which contain at least one of numbers from those k numbers is 2 ** n — 2 ** (n — k). (total — amount of subsequences that don't contain at least 1 of those numbers). You multiply it by value v and add it to result. Then you do n -= k, as we don't want to consider those anymore. MOD at the end

• 3 months ago, # ^ | ← Rev. 2 →   0 fact[now] / (fact[i] * fact[now - i]) Suspicion... I'd rather multiply by inverse of fact[i] * fact[now - i], because fact[now] not necessary dividable by fact[i] * fact[now - i]

• 3 months ago, # ^ | I couldn't debug within time, but my approach was: Consider the usual directed edges (i, A[i]). If in-deg of a vertex = 0, then it cannot be circled. And so it's out-child has to be circled. And if we know that if a vertex is circled, it cannot circle its out-child, so decrease in-degree of its out-child (and if its in-deg becomes 0, mark it as not-circled, and push into the process-queue). Keep repeating the above two points, until you end up with no vertex with in-deg = 0. So, in-deg of all 'active vertices' >= 1 and we already know that out-deg = 1 for all. So, in-deg = out-deg = 1 for all active vertices. So it's just a bunch of cycles. Iff all cycles are even, there's a soln.

  • 3 months ago, # ^ | Thanks, this is way simpler than mine.

• 3 months ago, # ^ | ← Rev. 2 →   +1 given graph is cycles with tentacles first — delete tentacles: if there is no edges to a[i] ("end of tentacle") — it shouldn't be chosen -> a[a[i]] should be chosen — remember, delete them, decrease in-edges count for a[a[a[i]]] do this while you can — you can keep vertices with 0 edges in the set and add them when some vertex becomes 0 in-edged ether everything is deleted or there is still untouched cycles if there is cycle with odd length — cout << "-1". You can understand this from a cycle of length 3 if each cycle has even length — color them 1 0 1 0 1 0

  • 3 months ago, # ^ | There is answer even if there are cycles of odd length. Consider 6 1 2 1 1 2 3

    • 3 months ago, # ^ | After the first phase, everything would be deleted in this case. So there is no odd cycle.

• 3 months ago, # ^ | ← Rev. 4 →   0 First of all we will try to identify what indices or elements are mandatory to come and what are mandatory to not to come. For this we can make a frequency array and if freq[x]==0 , x as an index can never come in p and because x can never come a[x] must come in uncircled elements and as an index too and a[a[x]] must not come as uncircled elements and so on .... considering all these facts, first of all we need to identify mandatory presence and absence. After this if there are any a[i]==i pairs or there are odd numberof indices left ans is -1 else an ans always exist.

  • 3 months ago, # ^ | ← Rev. 3 →   0 Counter? 6 3 1 2 6 4 5

    • 3 months ago, # ^ | yeah while traversing odd cycles must be removed ... in haste i just checked the parity of the remaining nodes instead of individual cycles. Thanks for pointing it out. AC Code

• 3 months ago, # ^ | Yes, that's basically the solution. The only additional thing is that cycles have to be handled carefully. Process each component of the functional graph individually, for each hanging tree, do subtree dp ( stores if its possible to not pick node after picking/not picking nodes from only its subtree and stores whether its possible to pick it). The transitions are the same as what you have written (its possible to not pick a node if all of its incoming edge nodes are picked, and possible to pick a node if atleast one of its incoming edge nodes are not picked). Now, we need to check if a valid set of choices for the nodes on a cycle exists. Pick any one node on the cycle to be the starting node. Fix the choice (not pick/pick) for this particular node, and go along the cycle, maintaining similar dp states (note that these dp states must take into account two things: the last node on the cycle, and the hanging subtree). The transitions are almost the same as when we find dp values for only hanging trees. Check whether there is a valid set of choices for both choices of the starting node. Finally, you can just store backlinks and find the unpicked nodes to get the final answer. Unfortunately, my implementation is cancerous and belongs on r/EyeBlech.

  • 3 months ago, # ^ | ← Rev. 2 →   0 I now watched the tutorial and realized that I'm soooooooooooooo stupid. I had the same logic of % of the editorial ;-;

• 3 months ago, # ^ | Nice profile photo.

  • 3 months ago, # ^ | Your profile photo nicer than him

• 3 months ago, # ^ | No answer for cheaters

  • • 3 months ago, # ^ | ← Rev. 2 →   0 Firstly, you cheated in round 899 div.2. Secondly, I have a legit prove that you tried to cheat during this round.

      • 3 months ago, # ^ | prove?

        • 3 months ago, # ^ | ← Rev. 2 →   +7 You shouldn't text people during the contest, asking them to exchange solutions for problems

• 3 months ago, # ^ | you can't have more than 3 distinct elements. for 1 distinct m=0. for 2 distinct all multiples of n and lesser than n {if(m<n) see the edge cases}. then for k==3 subtract all possible m-(k=1)-(k=2)

• 3 months ago, # ^ | if k > 3 answer always 0 if k = 1 answer always 1 and you have only to find what if k = 2 and k = 3

• 3 months ago, # ^ | if then

• 3 months ago, # ^ | answer <= 3

• 3 months ago, # ^ | Probably something like this

  • 3 months ago, # ^ | Thanks for the test case but it doesn't break my code. Any other ideas?

    • 3 months ago, # ^ | Spoiler

      • 3 months ago, # ^ | That was it! Thanks dude

• 3 months ago, # ^ | True, I had the same feeling.. thought either I am missing some simple observation or most of the submissions are copied.

• 3 months ago, # ^ | No, it was comparatively easier also today.

• 3 months ago, # ^ | initial ans should be p, cause you must to talk to someone with prize p and you have (n-1) people left to talk

• 3 months ago, # ^ | My solution was like this: If we could find sush uncircled elements such that: for every uncircled element with value x there is circled element with index x for every circled element with index i there is uncircled element with value i Then it would be easy to find a solution We can also see that this conditions are neccesary Now we just need to add our conditions to 2sat We will have 2n variables Variables i, 1 <= i <= n will be : 0 — if we doesnt circle element with index i 1 — if we circle element with index i Variables i, n < i <= 2 * n will be: 0 — if we circle all elements with value i 1 — if we doesnt circle all elements with value i We can see that adding clauses is easy now

  • 3 months ago, # ^ | How do you express 2. condition with 2-sat clauses?

    • 3 months ago, # ^ | ← Rev. 7 →   0 When i is 1 it implies i + n is 1(it means that not every element with value i is circled) For n < i <= 2 * n i is 0 implies j is 1 for all j such that a[j] = i (every element with value i is circled) For 1 <= i <= n i is 0 implies i + n is 1 (if i is not circled then not every element with value i is circled)

• 3 months ago, # ^ | Correct. Only after System tests.

  • 3 months ago, # ^ | thanks. Still only 74%...

• 3 months ago, # ^ | Yes you'll be able to submit after system testing is completed.

• 3 months ago, # ^ | Either in this blog or in the contest.

• 3 months ago, # ^ | What's QAQ ?

  • 3 months ago, # ^ | it means someone is crying .

  • 3 months ago, # ^ | i'm cryingQAQQQQQQQQQQQQQQ

    • 3 months ago, # ^ | Same here.. btw you've just started you'll get better don't worry..

• 3 months ago, # ^ | The 2 problems are very different though. There are plenty of problems with sum of max element of all subsets, just tat the condition for the subsets are different

  • 3 months ago, # ^ | ← Rev. 2 →   -46 Everything is relative, but I can't agree with very different It's obvious that selecting an index is not worse than selecting any of the subsequent indices, so for each we just update the value at that position with max of values on positions that are divisible by with time complexity (another way to notice this is to consider taking an index ). After this operation the problem is reduced to the one described in the article Personally for me the condition of the green and black elements felt more like a red herring

• 3 months ago, # ^ | 4 2 3 1 2 Your output: -1 Ans: 2 1 2

  • 3 months ago, # ^ | Did you test my output with my last sub? I realized that it was wrong during the contest but didn't correct it, However My other solution passed this testcase but still got WA on pre 4. Thank you for the test anyways. Any other ideas?

  • 3 months ago, # ^ | nvm, I found one

• 3 months ago, # ^ | You haven't taken modulo within your binary exponentiation function. It's causing an overflow.

• 3 months ago, # ^ | you have integer overflow in your binpow function since you aren't taking mod.

• 3 months ago, # ^ | Codeforces highlights your error with red line)) (need mod in binpow func)

• 3 months ago, # ^ | ohh thanks guys actually in contest also it was giving wrong of test 4 so i was just losing my cool that's why i didn't see the error message on top

• 3 months ago, # ^ | if(k==1){ System.out.println(1); }else if(k==2){ if(m<n){ System.out.println(m); } else{ System.out.println(n+m/n-1); } }else if(k==3){ if(m<n){ System.out.println(0); }else{ System.out.println(m-n-(m/n-1)); } }

  • 3 months ago, # ^ | Thank you

    • 3 months ago, # ^ | I made a table for B, maybe you can take a look std::map<int, int> mp; for(int i = m; i >= 0; i--){ std::set<int> st; int t = i; st.insert(t); for(int j = n; j > 0; --j){ st.insert(t % j); t %= j; } mp[(int)st.size()]++; if(st.size() == k){ std::cerr << i << '\n'; } } for(auto x: mp){ std::cout << x.first << " : " << x.second << '\n'; }

      • 3 months ago, # ^ | Oh, this is for C, I said it wrong :(

• 3 months ago, # ^ | ← Rev. 2 →   0 It depends on quantity and overall rating of participants. Also it depends on your current rating as well.

• 3 months ago, # ^ | You get less rating increase for separated Div 1 and Div 2 rounds because candidate masters have to choose the Div 1 category as opposed to normal Div2, Educational, or Div1+Div2 combined rounds

• 3 months ago, # ^ | Do you play Genshin impact bro.

  • 3 months ago, # ^ | Yes,I do.Genshin Impact is an open-world adventure RPG developed by miHoYo. Set forth on a journey across a fantasy world called Teyvat. In this vast world, explore seven nations, meet a diverse cast of characters with unique personalities and abilities and fight powerful enemies together with them, all on the way during your quest to find your lost sibling and the hidden secret of this land.