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 Oct/08/2023 12:05 (Moscow time). 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, emorgan, faustaadp, ffao, fishy15, flamestorm, gamegame, hocky, Insta-x, jdurie, joelgun14, KerakTelor, Marky, Murinh0, nvmdava, yz_, 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!

**Div. 1**

**Div. 2**

Congratulations for our first solvers:

**Div. 1**

**Div. 2**

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! 😍😍

Thank you errorgorn for carrying

Thank you ScarletS for carrying

rfpermen will win COMPFEST 15!

rfpermen will win COMPFEST 15!

rfpermen will win COMPFEST 15!

rfpermen will win COMPFEST 15!

cnnfls_csy will win COMPFEST 15

How come you guys are so sure?

Thank you Pyqe for carrying

Thank you Pyqe for carrying

Thank you Pyqe for carrying

Thank you Pyqe for carrying

Thank you Pyqe for carrying

Thank you Pyqe for carrying

Thank you Pyqe for crying

Thank you Pyqe for carrying

Thanks for creating these ladders!

Thank you Pyqe for carrying

orz errorgorn coordination twice in a row

can anyone explain what does "based on COMPFEST" means ?

The round is based.

Actual answerCOMPFEST 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. The Codeforces round will be happening parallel to the onsite round with a similar problemset.

As a tester, I am forbidden from commenting on the announcement post with any opinion.

What is the meaning of Muga-muga beja lan isa entuk biji apik!!

It's Javanese (a local language in Indonesia) meaning "good luck and have a good score" :D

As a tester I can assure you the problems are very **********************************.

The starting time was really weird but i guess it will be held on sunday after all

Finally a new round after 8 days :)

Contest, finally.

Not Every Country in the whole world observe a holiday on Sunday. In my country, Friday and Saturday are the two off-days in the week. And Sunday often is the busiest day of our schedule as it is the beginning of a new weekend. IF YOU COULD HOLD THAT CONTEST ON SATURDAY IN SUCH AN UNUSUAL TIME, then no people in the world would have had any problem as Saturday is the intersection of two traits of holidays.(friday-saturday based holiday like my country and Saturday-Sunday based on the majority of the country).

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.

Hope i have a good luck

Good luck everyone, Remember, you don't lose when you fail, you lose when you give up.

what will be the score distribution system?

Tomorrow I will fall 100 rating in CF first and then fall to blue in ARC.

Hope I have good luck.

Waiting.....................................

what will be if you win ?

Please note the unusual timing of the roundare COMPFEST div 2 problems harder than normal div 2 problems?

Muga-muga beja lan isa entuk biji apik!! Sound interesting, What's that mean?

"good luck and have a good score"Please announce the score distribution system.

As a participant I hope to get 1200+ rating or even better, Pupil****Isn’t that the same thing?

Good luck everyone.

Thankyou

Thanks for bringing this time to the game!

Why are there so many problems(like 7 problems) in recent Div1 contests? It's hard to adapt.

Hey King 👑 you dropped "score distribution"

best wishes

clashing with icc world cup

There is still some time left to reschedule the icc world cup, let them know.

Who wants the cantest to start at 14:35 UTC?

Finally, Chinese Oiers don't need to hold up to 1:05 evening. :D

Pyqe mlbb?

good luck to everyone

265 forces

The Scoring distribution is opposite in the announcement, swap div1 with div2.

It seems D1 = 500 1000 1250 1750 2250 2750 3250, does it correct?

i see that was found extra register so where is it

Completed A-D in 40 minutes ,then nothing for 2 hrs. E>>>>>D.

haha same

How to solve D

Just iterate over every maximum value $$$g$$$ from $$$1$$$ to $$$10^5$$$. Then, let's say $$$x$$$ = "count of indices that needs to be colored black to get a maximum of $$$g$$$" and $$$y$$$ = "count of indices that when colored black gives a maximum value less than $$$g$$$". Then, the contribution for $$$g$$$ would be $$$c_g = 2^{x + y} - 2^y$$$. Answer is the sum of $$$c_g \cdot g$$$ over all $$$g$$$.

isn't it Cg = 2^y*(2^x — 1) => 2^(x+y) — 2^y ???

Yeah, my bad.

You can use the following formula $$$\sum x*freq[x] = \sum freq[>=x] $$$. RHS means for given x, frequency of elements which are greater than or equal to x.

Can anyone please help me understand the solution for DIV2 Problem D Thanks in advance :)

It will be quite hard to explain. Wait for an editorial.

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.

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

Duck problem F

WTF with D's nowadays

What a great Contest

I'm honestly really annoyed at this, can someone see what's wrong with my code because I've been trying to debug this for the last 20 minutes.

Submission

`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]`

Is my solution correct for D1C?

For each of the directed subgraph, we need to find cycles and then there are 3 cases on some pair of adjacent nodes (pick both, pick first, pick second). For each case, apply dp and find the maximum count of nodes we can pick. Then backtrack to get all the picked nodes.

Also, is there any simpler solution than this?

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.

Thanks, this is way simpler than mine.

How to solve D1C?

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

There is answer even if there are cycles of odd length. Consider

After the first phase, everything would be deleted in this case. So there is no odd cycle.

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.

Counter?

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

In problem D the word

indicesshould've been highlighted.. I wasted the entire time thinking that elements multiples of black elements will be colored green.SpoilerHow to solve Div 1 C? I knew that it can be reduced to coloring nodes in a directed graph (in which outdegree of every node is at most $$$1$$$) such that for every node $$$i$$$, if its color is $$$0$$$, then, it must have outdegree $$$1$$$ and its outgoing node must have color $$$1$$$, otherwise, if its color is $$$1$$$, then at least $$$1$$$ incoming node must exist that have color $$$0$$$.

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 ($$$dp_{u, 0}$$$ stores if its possible to not pick node $$$u$$$ after picking/not picking nodes from only its subtree and $$$dp_{u, 1}$$$ 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.

I now watched the tutorial and realized that I'm soooooooooooooo stupid. I had the same logic of $$$99$$$% of the editorial ;-;

When can I see others's code?I want to know the solve of Problem D...

Nice profile photo.

Your profile photo nicer than him

Weak samples are OK for ICPC problems, but absolutely disaster for CF.

When will the editorial be posted?

.

div2 C is there any trick?

No answer for cheaters

?

Firstly, you cheated in round 899 div.2. Secondly, I have a legit prove that you tried to cheat during this round.

prove?

You shouldn't text people during the contest, asking them to exchange solutions for problems

lol

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)

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

if $$$i != n$$$ then $$$a[i] < a[i+1]$$$

answer <= 3

What is test 7 in Div 1 D :(

Probably something like thisThanks for the test case but it doesn't break my code. Any other ideas?

SpoilerThat was it! Thanks dude

After solving Div2 D, I have a strong feeling that D can't be solved by 2000 people itself in Div2, maybe heavy cheating is going on i Think

True, I had the same feeling.. thought either I am missing some simple observation or most of the submissions are copied.

No, it was comparatively easier also today.

Is there a randomized solution for D1C? I was choosing an index that was not circled in the answer, the probability of an index X to be that index is >=1/2 so with about 20 chooses I fill find such index. Then I was trying to make an answer for it greedily.

Interesting, but strange solutions for D1CD

Can someone help me find out, what is wrong with this submission? Div 2B/ 1A: https://codeforces.com/contest/1877/submission/227185346

initial ans should be p, cause you must to talk to someone with prize p and you have (n-1) people left to talk

Was dvi2E doable with 2sat or am i trolling?

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

How do you express 2. condition with 2-sat clauses?

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)

Div. 1 C was a strange one, I couldn't find the edge case on which I failed...

Why can't I submit a contest problem now? Is it always like this during system testing? I never tried before. I really want to submit 1E.

Correct. Only after System tests.

thanks. Still only 74%...

Yes you'll be able to submit after system testing is completed.

It seems that the score distribution of Div. 1 and Div. 2 are accidentally reversed.

Either in this blog or in the contest.

The sample is too weak :(

aaa QAQ,i'm firstly loser!!!QAQQQQQQQQQQQQQQQQQQ

What's QAQ ?

it means someone is crying .

i'm cryingQAQQQQQQQQQQQQQQ

Same here.. btw you've just started you'll get better don't worry..

Totally not today's D.

Also it seems like that GfG post is only 3 weeks old lol (nvm, more like it's 6 years old)

If this problem actually appeared in the

`largest student-run IT event in Indonesia`

— that seems curious at the very least.I am not saying that someone from the writers stole a problem, I'm wondering how nobody from the round organizers or the testers tried to google something like

Sum of maximum elements of all subsets, that's literally the first search answerThe 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

Everything is relative, but I can't agree with

very differentIt's obvious that selecting an index $$$k$$$ is not worse than selecting any of the subsequent $$$kth$$$ indices, so for each $$$k$$$ we just update the value at that position with max of values on positions that are divisible by $$$k$$$ with $$$O(nlogn)$$$ time complexity (another way to notice this is to consider taking an index $$$1$$$).

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

them bu l qua

Can anyone please give a hack? I get WA on pretest 4 on problem 1C/2E

Edit: ignore my last sub please, try this

Your output: -1 Ans: 2 1 2

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?

nvm, I found one

Any one can elaborate there E approach like will it is related to functional graph kind of think?

why the name effects of anti-pimples for problem D??

I was not able to submit solution for D while the contest was going on, It showed some error and then it started showing that "same code already has been submitted" So, I thought it will be considered but its not been considered in final standings and the solution was correct when I tried it after system testing.

What can be done about this ?

can anyone tell me what is wrong with my solution of the d problem in div 2 , 227195204

You haven't taken modulo within your binary exponentiation function. It's causing an overflow.

you have integer overflow in your binpow function since you aren't taking mod.

Codeforces highlights your error with red line)) (need mod in binpow func)

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

Failed to Notice $$$0\le a_i$$$ in D2D, I let $$$a_i=0$$$ if $$$i\mid j$$$ and $$$a_j\ge a_i$$$, which is wrong as I couldn't count the correct number of indices. However, I passed pretest successfully. Why not make pretest stronger?

For Div2 C how to visualize and find formula for k = 2 and k = 3

Thank you

I made a table for B, maybe you can take a look

Oh, this is for C, I said it wrong :(

Video editorial for div2 — A, B, C and D with Code Walkthrough Youtube Video Link

is it just me or does anyone feel like Codeforces is giving less rating points than previously for the same ranks

It depends on quantity and overall rating of participants. Also it depends on your current rating as well.

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

I didn't participated during the competition, so I participated in the Virtual Participation.

But I wonder why the number "265" appears so many times in the examples.

Waiting for the editorial!!!!!!

As for the problem B in div2, my code got Pretests passed during the competition and got ac after the competition, But why does it show that I did not pass problem B ? Is there anything going wrong with the system?

Thank all of you,this is a great contest!

I really like the problemset for this contest :). Thanks a lot to the authors, only complaint is maybe d1b is a little bit boring, but it's still fun. I think my favorite is d1c.

I think div2's E is like a shit, not only without useful examples, but also with a misleading example

Do you play Genshin impact bro.

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.

you can find number 265 in 1A's 1B's and 1D's test.

It was a good contest and I have learnt a lot of it and especially b and c were good problems

Attention! Your solution 227183020 for the problem 1877C significantly coincides with solutions 8vod/227158830, YuvrajSinghCharavande/227183020. Such a coincidence is a clear rules violation. i received this mail but the question is case based for 3 cases k=1,2,3 and greater i wrote it in the sequence k>3 for 0 ways and then outputs for the rest. i checked the codes submitted by others as well but i don’t see the complete resemblance also those accounts are far newer then mine. Also i would like to know why problems 1 and b are skipped as well.

how to approach the problem 3 in division 2 of this round??please help

Tuk edisi tahun ini Anda akan dihubungi kalau sudah ada info lengkap