Hi, Codeforces!

We are pleased to invite you to EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2), which will be held on 30.06.2024 17:35 (Московское время). You will be given **8 problems**, two of which are divided into two subtasks, and you will have **3 hours** to solve them. The round will be rated for **everyone**.

At least one of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

We would like to thank:

- errorgorn for coordinating the round.
- Geothermal, turmax, noimi, SomethingNew, feecIe6418, Endagorion, glebustim, zeliboba, thanhchauns2, zengminghao, mwen, cristi_tanase, milind0110, CSQ31, Evirir, AkiLotus, htetgm, TrendBattles, GreatEagle, chromate00, Valenz, Vamperox, priyanshu.p, DOCUTEE, Tran_Thi_Thanh_Van, and tibinyte for testing the round and providing useful feedback.
- MikeMirzayanov for Codeforces and Polygon.

We hope you'll like the problemset!

**UPD: The score distribution is 250 — 750 — 1000 — 1500 — 1750 — (2000 — 500) — (3000 — 2000) — 5000**

**UPD2**: Editorial

**UPD3**: Congratulations to the winners!

And now, a few words from today's sponsor!

### About EPIC Institute of Technology

EPIC Institute of Technology is an innovative educational project, driven by the Deltix team under the EPAM Systems umbrella. As part of EPIC — EPAM Product Innovation Center, we aim to cultivate the brightest minds and prepare them for a future in cutting-edge technology projects.

### Why EPIC:

EPIC Institute of Technology is an accelerator for the best talents. Our students will acquire hands-on experience in one of the selected major programs, all of which are highly demanded right now on top projects, together with the fundamental knowledge, so indispensable for real professionals. Successful graduates will have a unique chance to jumpstart their career on the most challenging and interesting EPAM projects worldwide. You will join the community of intelligent and driven individuals and have an honor to work with and learn from them.

### Here are the answers to the most common questions:

#### How much does education cost?

EPIC Institute of Technology is completely free. There are no fees to register for exams, tuition fees or any other hidden liabilities. The only restriction for getting into EPIC Institute of Technology is age. You must be older than 18 years old to become a student.

#### How is the educational process organized?

Each program lasts exactly one year. The academic year consists of two semesters. Courses in the first semester are the same for all programs. Courses in the second semester depend on the selected major program.

During the semester, students complete homework assignments and take 2 exams—a midterm and a final. The final grade a student gets for each training course depends on the quality of completed assignments and participation in practical classes.

#### How will the classes be held?

Lectures will be pre-recorded and available for self-study. Practical classes will be held at the specified time according to the provided schedule. Also, students will have an access to a Discord server, where they can discuss topics of academic interest with teachers and other students.

#### In what language will I study?

All programs are in English.

#### How can I apply?

The admissions process is as follows:

Fill out the form on the website.

Take part in one of the entrance exams that will be held in our Codeforces group. You can also find past exam breakdowns there, which may help you in your preparation. Exam dates will be announced later, so stay tuned to the announcement channel and our LinkedIn group.

If you successfully pass the exam, you will receive an invitation email.

#### What will happen after graduation?

All EPIC Institute of Technology graduates will get a diploma and the best students will be offered to join, either as an intern or a full-time position, one of the hot EPAM projects where skills acquired at EPIC Institute of Technology will be demanded.

Please visit our website to learn more about EPIC Institute of Technology and the available programs. If you have any questions, you can quickly ask them in our chat.

As a tester, I was blue at the time I tested.

I'm hungry

As a tester, I was green at the time I tested.

As a tester, I had 0 contribution at the time I tested.

As a tester, I was orange while testing and then going roller-coaster to blue and then purple today.

As a tester, I was cooking my brain in blue.

As a tester, did I even test this?

why your profile have negative rating?

because he's really bad at cp

no, i don't think so, he has authored contests in past.. i am curious how

I'm hungry

EPIC site has really unique design

As I wasn't a tester, I don't know why I'm doing this...

Sir, I didn't find any section about authors

As a

participant, I hope my color will also change after participation :)+121? :o (btw i wanna get back to specialist after this contest, or at least stay at P)

look at my profile :)

As a tester, when did I test this?

As a participant, I hope to reach blue this round.

Your already a blue.

233 point to

CM, I can't wait1665 points to LGM, i can't wait :clown:

i don't mean that i will reach CM in this round but i'm exiting to be CM as soon as possible

-331 points to CM, i can't wait

Hopes should be realistic bro

All the best bro

wtf epic games hosting cf round?!11!

Very few words indeed :)

As a participant, I want to know how many problems there are, and whether there are any interactive problems.

How many problems and what will be the score distribution of these problems in this round?

As a participant, I hope my color will be different after contest.

Even the number of colors you have may change! (By becoming lgm)

As a participant, I hope my color will be change after the contest.

As a participant, I hope to get my purple name back xD

Hello smart people, I wander through comments below posts to ask for helping with my problem.

I can`t solve problem, can you help me, please? I thank everyone in advance.

Thanks, anymore I don`t need your help, I have solved it

I assume that you weren`t be able to open this task because it is private, if it is true, accept my apologies.

what is rating distribution for this round??

The score distribution will be published later.As not a tester, how to be a tester actually?

Very good Question actually. Someone please answer this.

If someone setting a round knows you and trusts you they might contact you to be a tester. It doesn't really have any requirements it's just up to the setters

Can anyone join in the CF group?

As a bored random person surfing Codeforces, I smiled reading other comments on this.

hope to become CM again

Plz approve the request to join the EPIC Institute of Technology group on Codeforces!

I'm new to Codeforces so I don't know much about this but is this round affect my Codeforces rating or it will be unrated??

Read the statement.

Oh got it:) I though its not Codeforces one so it might be rated

Vladithur is back )

i hope i become purple after this round :)

same

same

Are the problems in div1+2 harder than standard div2 problems?

from experience, they are aaround the same in difficulty. Div1+2A ~ Div2A.

Is it Rated?

yes

How many problems will be there?

i hope i can reach 1750 in the next two rounds QAQ

that means i have to rank about 1000 a little bit tricky..

Wait no score distribution?

Please publish the score distribution

I am also waiting for it

as a tester, i wish you good luck, problems are good

Do you think I can be an expert today?

You can do it.

your hopes should be realistic

Take a look now, it was close and not impossible

It's not about what others think it's about what you think.

Baradar English sohbat mikone

Hope to solve 5 problems this contest

Maybe it will be my last div.1 contest before NOI2024.

Good luck to everyone.

What does (2000 — 500) mean in the score distribution? Why are there parentheses?

It means Problem 6 is divided into two subtasks, where first one is worth 2000 points and second one 500 points. Second one is worth less because if you solve the first one, second one may be a bit easy after the knowledge you gain from the first. OR you may start second one directly as solving it will solve both of them at the same time.

I see, so basically two problems but the second one is the harder version of it?

I have braced myself for turning green again. But let's hope it doesn't come to that :)

contest is not over yet, but i cant anymore. i thought i would at least solve 2 but ended up with one. anyways, good contest i guess

The pain of watching your rank go down for ~2hrs, minute by minute, as more cheaters submit the +1th(D) problem correctly. :(

375 pretests in H? What?

nice round) A in 2 mins, staring at B 1 hours, staring at C 0.5 hour, staring at D one hour

any hint for $$$D$$$?

Some observations I made:

Alice's strategy should be greedy

Bob must take all of the occurrences of a cake for his actions to be useful

Can we memoize based on position/turns?

I tried to implement a strategy where I count the number of elements of tastiness x > (greatest tastiness Alice has eaten) and then erase one of the elements from whichever element has the fewest identical elements, but I couldn't figure out how to implement it in time. I also don't know if it works.

I also tried assigning cakes to bob greedily(minimum frequency first) but I got wa2

Yeah I started with greedy too. The correct approach requires dp. The tutorial is out now.

solved using memoization (dp) ,logic is if bob has to remove any number than he remove all occurences of the number, calculate frequency of all element then store in a vector and do o(n^2) memoization (knapsack) you can see the memoization dp solution 268191223

The contest was nice, but am I the only one who feels that the problems were slightly on the standard side?

D was a cool problem, here's how I solved it:

Alice's strategy is obviously greedy, so she should always take the minimum available cake. Then we can memoize based on the position in the array and the number of turns taken. Let Bob gain 1 turn every time Alice eats a cake, and have the choice to remove a cake from the game for freq[cake] turns. We can simulate this using DP in O(N^2).

CodeI had the same idea but it failed on pretest 2 :(

What could be the problem? 268218168

What was D?

Don't know what to do in CP, just try DP.

newbiew's who only know greedy :-<

Alice will eat one of each cake tastiness in ascending order except for those tastiness values where Bob can eat all the cakes before Alice reaches it.

So for Bob the strategy is simple, he wants to pick the maximum number of tastiness values $$$t_1, t_2, ... t_k$$$ such that he can eat all of their cakes

BEFOREAlice reaches the corresponding tastiness values.Since it is only optimal for Alice to eat them in ascending order, we can sort the tastienss values in ascending order and do a knapsack like dp on their counts. Let $$$dp_{i, j}$$$ mean that Alice has managed to eat $$$j$$$ of the $$$i$$$ smallest cakes and Bob has $$$dp_{i, j}$$$ remaining turns for which we haven't decided what cake he ate. Then the transititions just become:

$$$1$$$. Alice eats a cake of the current tastiness and Bob gains another turn — $$$dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)$$$

$$$2$$$. We use Bob's remaining previous turns to eat the remaining cakes (if possible) — $$$dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - cakecnt[i])$$$ (iff $$$dp[i][j] >= cnts[i]$$$).

Then the maximum $$$j$$$ for which $$$dp[n][j]$$$ is $$$\geq 0$$$ is clearly the answer.

ahh got it, thanks

wouldn't it be the minimum $$$j$$$?

yes, it would be

Is problem D just a greedy simulation with priority queue?

Edit: Nevermind, you can just do a linear iteration over possible Bob moves for each greedy Alice move and get $$$O(n^2)$$$

I thought D felt similar to a priority queue simulation problem like this one, https://mirror.codeforces.com/contest/1974/problem/G , but I found doing take-not-take DP to be an easier approach

After some dirty optimization, I passed the pretest test of problem E (hoping I could pass the systest by luck). Can anyone tell me how to do it correctly?

If $$$a_v \gt \sum a_{child}$$$, then we clearly need to increment $$$a_{child}$$$ for some child.

Notice that incrementing a node $$$v$$$ by $$$1$$$ means that we will need to increment some chain of nodes $$$x_1, x_2, \cdots x_k$$$ where $$$x_1 = v$$$, $$$x_i$$$ is a child of $$$x_{i - 1}$$$ and one of the following conditions is satisfied for $$$x_k$$$:

Also observe that a given node can be used as $$$x_k$$$ by the first condition at most $$$\sum a_{child} - a_{x_K}$$$ times, while a leaf node can be used an unlimited number of times.

Moreover, such a chain results in a cost of $$$k$$$. So at any instant, we want to pick the shortest chain possible, i.e, pick a node

least depthfirst among nodes in the subtree of $$$v$$$ which satisfy the above condition.So we can just store the number of possible contributions at each depth for the subtree of each $$$v$$$ while iterating using dfs and use the above approach to fix cases where $$$a_v \gt \sum a_{child}$$$.

Code — 268172990

Oh, I understand now. Thank you for your explanation and the clean code.

Hey, bro does that depth_cnt[i][j] means vertex i which is at depth j and can be used depth_cnt[i][j] no of times.

Can you confirm. Pls

Hi, may I know why this approach failed when the operation started from the root (not from the leaf)?

When I do iterate from node $$$1$$$ to $$$n$$$, it failed. Else, it correct.

Same things happens when you reverse the order of the official solution to [0, n-1].

Great contest, the problems are very clear to understand.

enjoyed the contest, really nice problems.

The samples are a little bit weak, especially for F and G1 :(

Couldn't debug G1 in time :(

Though my predictor says I have positive delta :)

Hope to be CM the first time after the system testing.

congratulations in advance

Congrats!!! DuongForeverAlone, But u were always the "Master"! and Best of Luck! for System Testing.

Great job, congrats

In problem D, was anyone else getting the right answers for the sample test when the code run locally but got WA on pretest 1 when uploaded to codeforces?

What should I do the next time this happens to me?

try debugging it on custom invocation

For about half an hour I was wrestling with MLE on problem E, but I still have very little idea what was really causing it in the first place: first submission that passed pretests 268214003, resubmission without clearing vectors by hand 268217966 (by the looks of it switching from pbds to a map solved the problem). Did I fall victim to some funny memory allocation shenanigans with vectors, or are pbds just that evil when it comes to memory consumption?

I feel the problemset is a bit too unbalanced because ABDEFG are optimization problems, considering the major classification between optimization and counting.

I liked D and especially F, though. Thanks for preparing the round!

constraints of D are just to trick?

Maybe. Although I used O(n^2) approach, there possibly has an O(n) IMO.

first attempt -> O(n^2 * log(n)) -> TLE

second attempt -> fast IO -> MLE

third attempt -> O(n * log(n)) -> pretest pass hope no FST

really enjoyed the contest :)

does this approach work for problem

?Devery turn, Alice will choose the minimum cake that she didn't eat yet

then, Bob will take the maximum cake with the lowest frequency which Alice didn't eat, and he didn't eat all of them (every turn, Bob will reduce the frequency by one until there are no more cakes left with that number)

what did I miss ?

Assume there's an array {t[1], t[2], ..., t[r]} and Bob need to let Alice can't eat cakes with tastiness t[i]. Then for each tastiness t of cakes, let f[t]=1 is Alice can eat it, f[t]=-cnt[t] if Alice can't eat it, then every prefix sum of f[t] must be non-negative. You need to find the maximum array size by DP.

Lets take frequency array F = {4, 4, 4, 3, 5, 5, 2}

Now, according to your approach :

1}3, 4, 3, 5, 5, 1}0}3, 3, 5, 5, 0}now no matter what Bob does, Alice can choose 3 more cakes. So total 6 cakes. But, if Bob started with 4th cake type then he can also complete last cake type before Alice reach there. So, Alice only can take 5 cakes.

How to solve c?

Simulate the process.

The constraints are too high for simulation right?

You could simulate it in O(n) actually.

How? Please explain.

dp[n]=h[n], dp[i]=max(h[i], dp[i+1]+1)

It's so strong, I simulated it for more than two hours to make it, and you can write this dp in a few minutes

Traverse $$$a$$$ in reverse order. It is easy to see that the whole process will be terminated when $$$a_1 = 0$$$. Then, we only need to care about some positions $$$i$$$ such that $$$a_{i - 1} <= a_i$$$ because it will cause the process "delay". We will add $$$a_{i - 1} - a_i + 1$$$ to our result in this case because it is the required time to make $$$a_{i - 1} > a_i$$$. In the case that $$$a_{i - 1} > a_i$$$, we need to subtract $$$a_{i - 1}$$$ with the time that has passed, i.e our current result. The answer will be result added by the current $$$a_1$$$.

Submission: 268158682

if

`a[i]>a[i+1]`

then i^{th}will take a[i] amount of time to reach 0 but if`a[i]<=a[i+1]`

then it will take some extra time which will be equal to the time`a[i+1]`

takes to reach`a[i]-1`

so simulate this time taken by each tree from right to left and the time taken by the leftmost tree will be the answeri thought about finding increasing order from backward(N , N-1...) and currTime will the index where this break + 1( if there if atleast 1 more value than maxValue of sequence) and making this segments and taking maximum time

Try to find how the answer increase from [i+1....n] to [i....n].

If a_i is smaller than a_i+1, it means there must be some point where a_i equals a_i+1, and when a_i+1 becomes 0, the work is done between[i+1....n], and more importantly a_i is now 1.so ans++. If equal, ans++.

If bigger, it depends on what the current answer is. If current answer is bigger or equal than a_i, it still means there must be some point where a_i equals a_i+1, thus ans++. And if current answer is less, ans+=a_i-ans,which i guessed out.

Since h>0, it is enough with:

for (int j=0;j<n;j++) m=max(m,h[j]+j);

(find the height which is the most costly)

is E slopetrick? if so i'd be depressed cuz i've been solving slopetrick problems.

I just bashed it with brute force until it passed pretests (still can FST tho). I also considered small-to-large merging, but at the time I thought it was not going to work.

merge what?

And what is FST

thank you so much

FST — fail system tests (apparently pretests were actual system tests xdd)

In short in my solution I was pulling negative sum nodes to their ancestors

seems i wasn't even close to the proper solutions.

and thx.

I did use small to large merging

Although couldn't ac E because of a stupid silly mistake (Forgot to clear the global priority queues) -_-

But it turns out that the setters allowed O(n^2 log(n)) solution to pass.

yes (at least the way I solved it)

Saw D and E and realised its way out of my paygrade so just watched the Euros instead. Still is surprising seeing so many AC on D and E. Can anyone explain them? I am really dumb

solved D using simple memoization (just think if bob has to remove any element then he should have to remove all occurrences of that element and just do dp[submission:268191223]

For D:

Observation 1: Order does not matter, so move things around however we want

Observation 2: It is always optimal for Alice to eat the smallest cake, so we should sort the cakes

Observation 3: Bob should only eat a cake if he intends to eat all of those cakes of that level of tastiness

So with that, we can reduce this problem down to: for each type of cake (so we aggregate into tastiness, frequency pairs) in sorted order of tastiness, will Bob eat all of this type of cake or will Alice eat one of the cakes?

Let's think about the consequences of each action

Alice eats the cake: +1 to Alice's score, but Bob can eat 1 more cake

Bob eats the cake: Bob can eat $$$count[cake]$$$ fewer cakes, but Alice's score does not change.

Let $$$dp[i, j]$$$ represent the minimum number of cakes Alice can eat, starting with the $$$i^{th}$$$ least tastiest cake with Bob being able to eat $$$j$$$ cakes.

This leads to recurrences:

Although The first 2 points are straight forward

but can you explain me 3rd point " Bob should only eat a cake if he intends to eat all of those cakes of that level of tastiness"

isn't it optimal for bob to pick " largest unique values " because no matter what the frequency is alice can only eat once for each element ?

its important to remove all cakes of same level of taste cause if bob eat some amount of that a certain level and leave the other then alice will eat the remaining and still be gaining points

Place your bets, gentlemens: will my F1 randomized solution with time cutoff FST or not?

FST

Not FST

SpoilerPretests = systests in this problem, so probably not)

I have a solution for problem D with a complexity of $$$O(nlogn)$$$ 268173518. It's observed that Alice always picks the cake with the lowest tastiness from those remaining, and Bob will use some of his turns to take all cakes with the same tastiness. Therefore, we can solve this problem greedily. Specifically, when considering cakes sorted in increasing order of tastiness, if Bob can take all cakes with the same tastiness as the current cake being considered, we let Bob take them all. Otherwise, Bob will discard the maximum number of cakes he would have taken before and replace them with the current cake's value (provided there are fewer cakes of that value than the previous ones). Therefore, it's straightforward to use a priority queue to solve it.

Was C really easy or am I just stupid?

many problems are easy... once you know the solution

Another Cheatforces round...thank u indian students...submissions on C is crazy(bcoz code is small and easy to copy)

I once read somewhere..`Indians would rather die as a newbie but won't live as a cheater`

What are u reading ? Please don't

Thanks for the contest! Problems were quite good! Enjoyed today!

Problems are clean and organized overall, but the samples are a bit weak, especially for problem F. Literally any code could pass it (even if the dp was completely nonsense).

BTW, E could be solved easily in $$$O(n\log n)$$$ with small to large merging, just curious why was the constraint $$$5000$$$?

I suspect its to prevent irritating issues with overflows. Like, you need a leaf to contribute at least $$$n \cdot \max(a)$$$, but a node can sum to upto $$$n \cdot n \cdot max(a)$$$ which will overflow int64 for $$$n = 2 \cdot 10^5$$$ and $$$a_i \leq 10^9$$$. This is fairly easy to fix by capping the sum to $$$n \cdot \max(a)$$$ but its also irritating for no real reason.

Also, I personally feel that adding small to large merging doesn't make the problem any better, its a bog standard implementation of it.

The second reason is correct, I didn't feel like it added much to the problem)

I liked this problem (and contest) but this type of setter takes are so dumb. Optimizing to a completely new complexity class always adds more to a problem...

Isn't the cool part seeing what's the limit possible?

"adds more to a problem" not necessarily in a good way, and here i agree

there is literally no difference between the 2 except for harder implementation and knowledge of the technique ofc

Afterall it's problem E not A or B, so since making $$$n\le 2\times 10^5$$$ isn't actually a big increase in the difficulty (most people who can solve to this problem should know small to large merging, and it had appeared in div2 contests before), why not make it like that?

Setting the constraint to $$$5000$$$ would make people like me who are used to this technique doubt why the constraint was so small, and I had to look back really carefully just to make sure that I hadn't misread anything.

ExplodingFreeze Isn't the answer at nost $$$n\cdot \max(a)$$$ because you can just increase everything to be equal to $$$\max(a)$$$?

Random stress tester for F save me from penalty for F1 (Wrong greedy (take from back if possible) passes all quite small cases, so I should try larger tests, but happily in random case the number of possible state is not so large)

I actually was convinced the greedy idea was wrong but it passed ~500 rounds / 2 mins of stress testing at $$$N = 16$$$ so I submitted the code, only for it to find a countercase 2 seconds after submission T_T

Sorry this might be dumb but what is random stress tester, is it different from stress testing we do?

What is the counterexample for that? I wasn't able to come up with or generate a counterexample and I still don't know why it isn't working :P

1,9,5,4,5,2,3,3,5

Greedy: 5-2, 4-3, 1-9

Correct: 4-5, 1-9, 3-3, 2-5

Everybody at cloudflare needs to be locked up

I'm a little confused why G2 is separated from G1, the feeling of having to add many cases and pre-calculations into the code is really frustrating. (And I failed to debug it in time)

Using G1 only will make the problem more clean. Discard G1 and use G2 only will make the thinking process less interrupted and will prevent coding from being tedious in my opinion.

Anyway, the problems are good.

also curious if it is possible to implement G2 quickly and clean

For me, the number of cases was the same for G1 and G2. For G2 all I needed to add was if statements before some of the cases from the G1 solution.

In this contest, I definitely reached the expert and at the end of the competition I decided to resubmit problem D with optimization (just like that, I understood that my first solution worked). But I didn’t know that only the last attempt is counted, where is it even said about this? And why some people have multiple parcels tested (in system tests). Because of this stupid rule, I will not reach the expert, thanks for this, any desire for programming is gone.

When a contestant realizes there is a bug in their submission, and have not yet locked it, they should be able to resubmit. Naturally, the last such attempt will be tested.

If you want to submit an optimized version that shouldn't affect the standings, you can do it after the contest.

Why can't system tests just test solutions in order?

Because it will be abused by solutions which pass with certain probability?

Still, it is assumed that the pretests are good enough

Random algorithms are random no matter the test.

So one could submit several random solutions and the chance of all of them failing would be significantly smaller.

lol

orz

First Solves

A: sstrong

B: tourist

C: gamegame

D: Benq

E: tourist

F1: tourist

F2: tourist

G1: tourist

G2: ecnerwala

H: Radewoosh

I'm not first solve for A, sstrong submitted 2 seconds earlier: https://mirror.codeforces.com/contest/1987/standings/participant/185369380#p185369380

Found them by sorting by submission time.

Thank you for letting me know, I've corrected it.

Thank you for the contest!

In particular, most of the problems get away from the common pattern of "solve me much faster than O(input^2)", which is nice and refreshing.

started 50 min late,great contest tho

can anyone plz tell what is wrong with my logic for B. here is my code-268197602

for _ in range(int(input())): n=int(input()) l=list(map(int,input().split())) op=0 def f(l,op): t=False

can someone please explain me why this is incorrect?

Is there a reason for the lower problems to have 256 MB limit? Especially for problem D and E, it's easy to come up with various solutions that use $$$\mathcal{O}(n^2)$$$ memory, and a single

`long long`

array with size $$$5000 \times 5000$$$ already uses near 200 MB. Furthermore, it's super hard for heavier languages (for example, Python) to optimize it to fit in this tight ML.Apparently, in problem E, it seems like an overlook that many solutions that use $$$\mathcal{O}(n^2)$$$ memory with very high constant passed, including mine. It's kinda lucky for me that the tests didn't have this simple test with a straight tree with no operations required. I knew that my solution can easily fail on this test, but I just believed that the tests are weak :) There are dozens of uphacks already (https://mirror.codeforces.com/contest/1987/hacks?verdictName=CHALLENGE_SUCCESSFUL ), but there could be more of them that can be hacked with other patterns.

I personally see no reason to use a tight ML like 256 MB nowadays, unless there is a solution that has to fail with that exact limit and not any more lenient.

I was struggling greatly with ML in E, but once I switched from a pbds

`gp_hash_table`

to a`std::map`

I passed the tests with flying colors. Any ides why that could be the case? Here's exactly the same code that passed, but it's using gp_hash_table instead of a regular map and it gets MLE 268234524.UPD: I realized that by looking up different depths in a loop I was implicitly adding more and more keys to my hashmaps, leading to MLE. Also even my in-contest solution gets TLE now, well played.

If author solutions have better O complexity of memory, why should they have to help worse complexity pass? You can still get lucky but I don't get why memory should be treated as so variable and only time complexity is more strict.

Except that it didn't actually prevent most of those worse complexity solutions from passing, and it only made a vague boundary between lower and higher constant solutions.

Authors should not only consider their own solution but also whether they would want to allow worse solutions to pass or not, and try to block them if they don't want them to pass. If they didn't want $$$\mathcal{O}(N^2)$$$ memory solutions to pass, then a viable option would be setting $$$N \le 10000$$$ and maybe a bit more TL (and 128 or 64 MB ML is also an option). They should still be fast enough with any $$$\mathcal{O}(N)$$$ memory solution because of high cache hit rate and small I/O. If they had no intention to block $$$\mathcal{O}(N^2)$$$ memory solutions, then the ML should just be higher.

It's like setting an $$$\mathcal{O}(N)$$$ problem with $$$N \le 30000$$$ with 1 second TL. If they don't want $$$\mathcal{O}(N^2)$$$ solutions to pass, they should increase the upper limit of $$$N$$$. It's a very poor preparation of a problem if they just go with "we have a $$$\mathcal{O}(N)$$$ solution, so it's up to you if you're gonna try $$$\mathcal{O}(N^2)$$$ solution or not".

this contest was literal nightmare for me.

slow solve ABC + unable to solve D (too incompetent)

feel worthless.

i dunno bad tasks today or i'm dumb, but i'm able solve only A, somehow have 1300 on another acc. Div2 always roulette

div1+2 is generally harmful for low division < +1900, it's not my opinion but statistics.

DP Forces

Please explain the approach for D in little detail??? saw other comments but they seemed kinda vague, ppl have just given the transitions they used in dp without any/proper explanation...

First, create an array $$$\{c_n\}$$$ that contains the count of each value of $$$a_i$$$, in the order of increasing $$$a_i$$$. For example, if $$$a = \{ 3, 2, 2, 2, 5, 5, 5, 5 \}$$$, then $$$c = \{ 3, 1, 4\}$$$ (the count of $$$2$$$ is $$$3$$$, the count of $$$3$$$ is $$$1$$$, and the count of $$$5$$$ is $$$4$$$). Let's say the length of $$$c$$$ is $$$m$$$. We forget $$$a$$$ for the rest of the tutorial, and we call cakes with the same value of $$$a$$$ using the index of $$$c$$$ (the cakes $$$i$$$ ($$$i = 0, 1, \ldots, m - 1$$$) implies the $$$c_i$$$ cakes with $$$(i+1)$$$-th smallest value of $$$a$$$). Note we use the $$$0$$$-based index for $$$c$$$ below.

Alice's optimal strategy is simple: it's always optimal for her to take the smallest index (in terms of $$$c$$$) that's available to her. For Bob, he chooses a set of indices $$$x_1, x_2, \cdots, x_k$$$ ($$$1 \le x_p \le m$$$, $$$1 \le p \le k$$$) and try to eat all of the cakes $$$x_p$$$ before Alice can eat any of them, and he wants to maximize $$$k$$$ (the size of $$$x$$$).

Here we want to consider when Bob can take the cakes $$$i$$$. Obviously, he doesn't want to take cakes $$$0$$$ (because Alice takes one of them in her first turn, and it doesn't make sense for him to eat the rest if any). He can take cakes $$$1$$$ if and only if $$$c_1 = 1$$$ (if $$$c_1 \ge 2$$$, then Alice can eat one of cakes $$$1$$$ in her second turn). Similarly, he can take cakes $$$2$$$ if $$$c_2 \le 2$$$, and so on.

So we can think of the following algorithm: Bob has $$$0$$$

allowanceinitially. We look at each $$$i$$$ in the increasing order, and assign Alice or Bob to each index. If Alice takes the index $$$i$$$, Bob gains $$$1$$$ allowance. Let's say Bob has $$$j$$$ allowances so far. Then he can take the index $$$i$$$ if $$$j \ge c_i$$$, and by doing so he loses $$$c_i$$$ allowances.At this point it's relatively straightforward to build a DP. Let's define $$$\mathtt{dp}[i][j]$$$ as the maximum possible number of indices Bob took so far, where $$$i$$$ is the index of cakes we're going to look at next, and $$$j$$$ represents Bob's allowances. The state transition is:

The final answer (the number of Alice's indices) is $$$\displaystyle m - \max_{0 \le j \le m} \mathtt{dp}[m][j]$$$. The table size is $$$(m + 1)^2$$$, and it takes $$$O(1)$$$-time to calculate each cell of $$$\texttt{dp}$$$, so the algorithm requires $$$O(m^2) = O(n^2)$$$ memory and time. Note that the memory limit 256MB is a bit tight for the $$$5001^2$$$ element table, so you might want to avoid allocating the whole table and calculate each row incrementally.

Thank youu so much for the reply! there is one thing i still dont understand tho, when you say "If Alice takes the index i, Bob gains 1 allowance."

what exactly do you mean by this?

The "allowance" is defined as the number of moves that Bob hasn't taken yet. If Alice takes the index $$$i$$$, Alice moved but Bob hasn't, so Bob now has an extra move. This means that his "allowance" is increased by $$$1$$$. It's a really abstract idea to me and I personally didn't solve it in the contest (womp womp to me).

Your explanation is exactly correct. Essentially it's accumulated turns Bob can use to take several indices, so he can block Alice from taking them.

The term "allowance" may not really make sense, and if so I'm sorry about that. It's abstract concept (kind of), and I wasn't really sure the right term for it.

It means, Bob can complete his step 1 (allowance) before Alice can take her next step.

Thank you so much for this detailed explanation for the dp approach. Finally understood it.

Thanks a lot. Amazing explanation. I have been searching everywhere and found this that finally helped me gain the required perspective for solving the problem.

man the rating change in this round is so harsh :(

How does the rating even work here? My prev rating was 1019, and my friend's was 1035, We both solved 2 problems, A and B, but I did it faster and got a better rank than him, still I got a -5 and my friend got a +51 rating, why is that tho? Both of our solutions got accepted, The screenshots are evident of it, Anyone can explain? this doesn't make any sense

Because he is a new account. In his fifth round, he will have extra +100 rating. So it seems like he got +51, but actually he got -49.

Still doesn't make any sense, my other friend has an old account, his prev rating was 1048, he got a rank of 10667 and -36 rating only, So you wanna say that at better rank with lower previous rating you will get -49 and at worse rank and higher prev rating you will get only -36? Where's the logic in this.

Ratings will be calculated differently for new users for the first 6 contests,read this blog for detailed process- https://mirror.codeforces.com/blog/entry/77890

Hello everyone, I am a newbie in competitive programming. I am looking for a friend ranked preferably higher than me to ask doubts and discuss problems. If anyone can help me out that would be great

hello

Great

I wonder if the rating changes will get temporarily rolled back and I get to pupil after :')

Same, need a +2 :))

in case someone gets WA on test 2 in E and so you don't spend an hour to find the test:

Testcase 580 in Test-2 in E Wonderful Tree:

I was using set, and at some point I had to keep two states with depth 2 and delta 1, but set obviously only kept one copy.. so, use multiset. :)

I still don't know why there are so many Accepted solutions in the problem D, the dynamic programming is not that so easy, it make my head blow up and many of my candidate master friends didn't solve it. However, according to the clist.by, it is only a 1600 rating problem, I thought it should be at least 1900.

You could solve the problem with a greedy: https://mirror.codeforces.com/contest/1987/submission/268268604

I imagine that is why the rating is not as high as you thought.

I feel upset that I find G1 is easy for me now .... qwq

It happens....

.

Why am I getting mail for Copy code? I have not copied from anyone. Still I got the email and my problems are skipped.

What's the Matter? Can anyone please explain?

I've recently got a mail regarding the similarity between my and others' B solution. What should I do about it?How can I get it resolved?

I've not copied from anyone. Neither given it to anyone.

Regarding the alleged coincidences in the solutions 268180337 and 268200502:

I am the author of the first solution. The resemblance between these two codes is due to the fact that my friends and I had upsolved a recent Div.3 contest completely. In that contest, there was a problem titled "Money Buys Less Happiness Now," which had a similar logic (using a multiset greedily) to this D problem. Since we discussed and solved that question together, our approaches in these submissions were also similar. Therefore, I

strongly requestthat I should not be held accountable for plagiarism in this contest.Thank you for your understanding.

Nor I have copied the solution from somewhere nor I have shared my solution with someone else by my own wish. I don't know how it matched. I have a self made template. Last contest I submitted only one solution. This time I solved 3. No. of solution was never a problem. I think someone shared my code in such a large scale then they deserve punishment. Orelse I don't see so much coincidence. I solved using an online complier. I couldn't submit it early because website was not verifying me as a human. My solution was submitted by another friend whom I myself shared my code and I am sure he won't share with anyone. Please don't delete my contest. I accept to lose points rather than getting tag of a cheater. The online complier was normal complier so I don't see any chance of getting my answer leak there. The only way of getting my answer leak is codeforces website. I may be wrong but thats what I feel.

The similarity between my solution and another is due to a recent Div.3 contest problem with similar logic. I discussed and solved "Money Buys Less Happiness Now" together, leading to similar approaches. Please reconsider the plagiarism allegation.

Thank you, Yug

I have got a message regarding copying the solutions for b and c, and there is one person whose solution coincides with mine, why that happen i have not even shared any solution to anyone and besides those questions have simple equation based solution any one can derive those equations rest snippet is common too, it is really a coincidence that my solution mathched with any unknow, my submissions are: 268190821 268208107, at last i want to say that it is a coincidence that solutions matches as equation were simple.

I kindly request you to put some light into this problem and take appropriate action.I was recently informed that my code for Problem B significantly coincides with other 50+ participants submissions. I have participated in 72 contests on Codeforces with honesty. I have never engaged in any form of code copying or cheating. My consistent progress and previous submissions on this platform are a testament to my integrity (please review my entire CP journey). My submission was made in 13 mins and except 268144921,268147109 and mine, all of the similar submissions are submitted after 18 mins. Many of the similar solutions have been submitted just around 20 mins mark. Either my submission was stolen via hacking phase or it's a complete coincidence (as the code is quiet small).

I'm one of those 50+ participants. I'm surprised that this is the first problem where my code coincided with others' so much that I got suspected of cheating because it wasn't as trivial as some other Div2A/B problems (I've written 200+ contests with a standard coding syntax/style). Maybe there were some recent changes in plagiarism checking?

Of course, I didn't cheat (there's also zero chance of my solution leaking other than being copied from the hacking phase). Hopefully, the accusation will be revoked for both of us.

Wish you luck on your journey!

I am at the same point as you. I have even explained a lot of codes to my batchmates as well. Hoping that both of our accusation will get revoked.

We are both been accused for the same problem. For me CP rating doesn't even matter. I just do it for fun.

I think they should take some action

Dear Contest Organizers,

I recently received a warning regarding my solution for Problem 1987D in the contest. My solution significantly coincided with other solution, which is noted as a rules violation. I want to clarify that this was unintentional. I did not share my code or use public platforms with default settings.I think it may occur due to hacking phase I apologize for any inconvenience this may have caused and assure you that I will be more careful in the future. Please let me know if there are any further steps I should take or additional information you require from my side.

Thank you for your understanding.

A simple greedy solution for problem D (with comments for better understanding)

Don't know why so many people did DP on D.

I was recently informed that my code for Problem D significantly coincides with other 30+ participants submissions. I solved the problem D in just 30 mins, and my code style is consistent with all other submissions of mine. I don't know any of these 30+ accounts, and didn't sent my solution to any others. I only use local editor, and it is not possible that the code is leaked due to my fault. I've participated in 30+ contests and have never engaged in any form of code copying or cheating. I guess my submission was stolen, because others may get my code through hacking. To be added I can also provide the screen recording of participating this round. I kindly request my account not be alleged plagiarism. Thank you.

Regarding the similarity in the solutions 268200502 and 268180337

The similarity between my solution and another is due to a recent Div.3 contest problem with similar logic of using multisets greedily. I discussed and solved "Money Buys Less Happiness Now" together with my friends, leading to similar approaches. So, I request you to please reconsider the plagiarism allegation. Thanks, Parth Agrawal

// Oh ALLAH, teach us what will benefit us, benefit us with what you taught us, and increase our knowledge

ameen

good contest.

Why did nothing happen to the cheater of the EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) contest and their rating? MikeMirzayanov & Vladithur