Hi!

On May/02/2021 17:35 (Moscow time), we will host Codeforces Global Round 14.

This is the second round of the 2021 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2021:

- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2021 supported the global rounds initiative!

All problems were written and prepared by me FieryPhoenix and dragonslayerintraining.

Huge thank you to everyone who made this round possible:

- adedalic for coordinating our round!
- frodakcin, Xylofo, awoo, prabowo, Shanks, Roundgod, thenymphsofdelphi, Nezzar, BledDest, PurpleCrayon, chctxdy68, nchn27, Aaeria, not_tehlka, namanbansal013, growup974, Saurabh_yadav, HIS_GRACE, Amazed, AlanTheMankey for testing and valuable feedback!
- MikeMirzayanov for Codeforces and Polygon platforms!
- You, for being you!

You will have **3 hours** to solve **9 problems**. Scientific studies have shown irrefutable evidence that upvoting this blog and participating in this round will lead to longevity and happiness. GLHF!

**UPD:** The scoring distribution is **500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3500 — 4250 — 5000**

**UPD:** **Editorial** is here!

**UPD:** Congratulations to the winners!!

Is it rated?

The rounds are open and rated for everybody.Mentioned in the second line ...

For anyone wondering what GLHF (in the last line) means — Good Luck, Have Fun!

ugh i cant make good meme : (

it will be a meme)

PurpleCrayon orz!

Codeforces: 20 T-shirts randomly distributed.

Me: Pretending to calculate the probability when I know answer is 0.

My first codeforces global round

Excited for this round.

rainboy ORZ !!!

Scientific studies have shown Global Round are usually hard, but I will participate for longevity and happiness.

But scientific studies also show that its_Atrap

As I tester of this round people are giving me downvotes.

Someone please upvote this poor guy!

As a tester, there's a reason this round is a Global Round (cf's flagship contest). The statements are natural and concise, the problems are elegant, and I hope you have a great round!

The statements are concise, sold itPurpleCrayon orz

PurpleCrayon Skittles orz

PurpleCrayon Skittles Lunchbox orz

PurpleCrayon skittles lunchbox izhang orz

PurpleCrayon skittles lunchbox Izhang moo. orz

I know a geniosity when I see one. PurpleCrayon orz!!!!!!!!!!!!!!!!

PurpleCrayon was only a tester to delay his inevitable LGM. orz

PurpleCrayon orzzzzzzz how so good

PurpleCrayon orz how so geniosity

purplecrayon hso

PurpleCrayon skittles lunchbox moo. TheYellowFlash orz

I hope to become

Purpleafter this round :)I vote only after contest.

XD

Hope I will remain a specialist after this contest.

If science says to upvote this blog, then i believe in flat earth.

sto PurpleCrayon orz

Relatable >_<original meme(≧▽≦)...

Very original meme

Woaahhh, Directly trying to defeat red coders. Nice MEME!!!

OK I guess global rounds are really hard this was my first codeforces contest I guess i shouldnt be demotivated because i didnt even submit a single thing right just got close on phoenix and puzzle(failed test 2 lol)

Can we expect to have subtask?

omg, a round prepared by the Americans with Chinese names

omg :O

With

aChinese name.Meanwhile Rotavirus doing background check of every american contest setter.

Global Rounds always provides a very good opportunity to boost up your rating... Excited!!!!

And a very good opportunity to boost it down, too =)

lol!

lol no. for the same performance you get much more rating in div2 than in global/div1. Not that it should matter but that's not the point here.

It may vary from individual to individual depending on the topics in the round for example.

However in general for the same performance you get the same rating. That's the whole point of ELO.

Nah

I can barely get any positive delta if I solve A,B,C in Div.1, whereas in Div.2 Solving up to E once made my rating go as high as 2255.

Nah

First, from your history, you never ever solved A-B-C in div.1 only rounds, so I don't quite get what you're talking about

Also when you got your 2255, you had rank 8, there were only seven "violets" who performed better. Just compare it to your performance in div.1 rounds

l agree with you

ELO system is not perfect. It makes very simplistic assumptions about the estimated probability of one player beating the other, based on just a single number (player's rating score). My understanding is that if rating scores of players are very far apart, then ELO based predictions become much less accurate. And isn't this the primary reason why division based restrictions exist?

Anyway, all of this can be probably confirmed or debunked by just re-calculating rating score updates of div.2 contests without filtering out the normally non-rated people with 2100+ rating. My guess is that it would be a bad news for the rating scores of weaker participants. But of course I may be wrong.

I have observed there's a lot more cheating in global rounds than normal rounds. Honest participants usually suffer in global rounds imo.

Most probably because it's of 3hrs and cheaters get sufficient time to cheat .

wow, it's been a long time since the last global round.

As a tester, unfortunately, I don't have any witty joke to write in this message.

as long as you include "As a tester" in your msg, its fine :)

No need for that as long as he is

BledDest.Can't we participate from m1.codeforces.com or m2 or m3? I couldn't find this contest on any of these versions of codeforces.

UPD: Its added. Thanks.

Nice

Omg 5000 points for a problem. Focus on the last problem, problem I with 5000 points, that's enough. :D

I like the strategy which has a possibility that we don't solve anything in the contest XD.

by the time I solve it, it would be worth a negative amount of points.

By the time I solve it, it will time for codeforces global round 100.

You guys are solving 5000 pts problem :(

All the best bro.

Contest time is really bad

Why aren't contests more late or earlier (for example 15:35 or 21:35)

Are the two contest authors related?

They're both americans with a chinese name, i guess

Please dm me the problems I promise to not tell anyone

What is ORZ, I've seen it in many comments.

orzA distressed guy?

Daily reminder that Google exists

Me, a football lover coder today

Same thing happening with me. But for IPL....

Postponed!

This round has extremely strong pretests.

First contest in isolation! I hope I have the energy to compete. #COVID_coders

Same here brother, me too suffering from covid, I can feel your pain. T_T :(

Same situation. Tested positive yesterday. Unlike others I am having a headache, so decided to take some rest.

If you are not well, I advise you to do the same.

Scientific studies have shown irrefutable evidence that upvoting this blog and participating in this round will lead to longevity and happiness1000 people : wow we will upvote!

Hmmm, I was imagining a closet full of segment trees, linked lists and a few queues. Never thought of the struct t_shirt. Hmmm..

So many down votes because if you meant a typename then you should have used shirt_t by cpp convention.

Hope this doesn't happen during the contest.

PurpleCrayon orz!!!!!!

wer retin chains ?

Is it only me who can't do anything for 1 hour before the contest and keep switching between different tabs until it starts?

Maybe you have to do the same thing after 2 hrs in this contest(considering the difficulty of global round).

true :(

There is a long queue, about 4 pages show only "running". Would that affect the round?

My first Global Round,nervous.

Can i even solve the 1st question huh...... i don't think so :(

After having 10 Wrong answer on pretest 2 for a and b. ORZ

My rating after this global round going down like Wheeeeeeeeee

I upvoted the blog and participated. I guess the scientific studies and their evidences for longevity and happiness are wrong :(

I wonder if D is that easy felt like a normal C

I worked like two hours on d but didnt get it :/

And I worked two hours on C

xD

it happens sometimes i can't solve an A problem even so more like 11000 solved it that's weird and I thought so hard and still didn't get it XD

Yeah man, your rating graph and game is truly inspirational! (y)

it will be better trust me I had a hard time and couldn't learn anything new for like 2 years and a half but now things really changed

I feel your pain in these comments. Whatever the hard time you had I am sorry for that. Your consistency is brilliant. I hope God gives you the power to battle these hard times and you learn new things and reach the master level or so.

Well here's what i did for pretests(don't know if it will pass or not)-

if $$$l==r$$$ then count how many numbers are same in both $$$l$$$ array and $$$r$$$ array call this count and answer would be $$$ans = r - count$$$

if $$$l!=r$$$ then we are sure we need to shift $$$abs(l-r)/2$$$ elements from larger array to smaller array to make size equal, add it into the ans and now before shifting we will first remove those numbers from both the arrays which are same (as shifting them would cost an additional money to change the color) after this we shift those elements from larger array first that are similar to each other so that 1 copy of that element stays in larger array and 1 copy in smaller array and we don't need to spend additional money to change the color, even after this if elements are not same we will change their color and add it into the answer.

consider this-

14 10 4

1 1 1 1 2 2 2 2 3 4

1 1 1 1

we will first remove all the ones as they are present both in $$$l$$$ and $$$r$$$ arrays, after this its better to remove two 2s from $$$l$$$ as it will prevent us from spending extra money on them by changing color now the arrays would become-

1 1 1 1 2 2 3 4

1 1 1 1 2 2

now we just shift either 3 and 4 and also change its color.

Thought of exact same idea but could not implement lol

D is not even close to 2000 score

lol, how to do well in global round? Weirdly I perform badly whenever I participate in global round(somewhat not bad in other Div. 1 + Div. 2 round).

Once again C was much tougher than D to me

How to solve E? I can only come up with $$$O(n^4)$$$ $$$dp[i][j] =$$$ ways to turn on $$$i$$$ computers with $$$j$$$ operations used

And it can pass the pretest.

Note that there cannot be more than one consecutive light that turns on automatically. So, our final answer will have some segments of $$$1$$$'s (lights that are turned on manually) separated by exactly one $$$0$$$ (lights that are turned on automatically). We need to find the number of ways to make such an arrangement.

Let's take this one step at a time.

In how many ways can we turn all the lights on manually?

You can only choose one starting light in a segment of n lights, then at each step you can either go left or go right. For better visualisation, consider n points coloured red. Pick a starting point and colour it blue. In each step, you can move from a blue point to an adjacent red point.

Number of ways to do this = $$$(L + R)! / (L! * R!)$$$ , where L is the number of steps to the left of the starting point that one can take, and similarly, R is to the right.

To meet the constraints, we will be precomputing these answers till $$$n$$$.

Now, coming to the main solution.

Let $$$dp[i][j]$$$ = number of ways we can arrange the first $$$i$$$ lights such that the $$$i$$$ $$$th$$$ light is manually turned on and a total of $$$j$$$ lights were turned on automatically among the first $$$i$$$ lights.

Let $$$k...i$$$ be the last segment of $$$1$$$'s. This means that at position $$$k-1$$$ we will have a $$$0$$$ and at position $$$k-2$$$ there will be a $$$1$$$. If there are exactly $$$j$$$ $$$zeros$$$ in the segment $$$1...i$$$ then there are exactly $$$j - 1$$$ $$$0$$$s in the segment $$$1...k-2$$$.

Let's define an operation, as we turning a light manually on (or placing a $$$1$$$). So in the segment $$$1...k-2$$$ we have to place $$$k - 2 - (j - 1)$$$ ones, and in the segment $$$k...i$$$ we have to place all $$$i - k + 1$$$ ones. This is similar to the question we answered above for placing all ones. We have to tell the number of permutations of $$$(L + R)$$$ items, in which the order of the $$$L$$$ items and $$$R$$$ items are fixed.

Therefore, the ans for $$$dp[i][j] = dp[k - 1][j - 1] * nCr((k - 2 - (j - 1)) + (i - k + 1), (i - k + 1)) * ways$$$ $$$to$$$ $$$arrange$$$ $$$(i - k + 1)$$$ $$$ones$$$

PS: I know it's a little too verbose. But hope you can understand the solution.

You can simply let computer $$$i$$$ in $$$dp[i][j]$$$ be turned on automatically.

so you just have to enumerate the last automatically turned on computer before computer $$$i$$$ for $$$dp[i][j]$$$

How to solve D?

Video Explanation for Problem D

How to solve B and C ?

For b check the if number is divisible of 2 or 4 and the remaining number should be a square number.

In C, keep assigning the block to the tower with minimum current height. Can be done using set <pair<int, int > >. Also the answer can never be NO,

How to justify this solution i.e how to prove that difference in height won't exceed x ?

Suppose we have formed m blocks(B1,B2...Bm) with some i(i<n) smallest height towers.

h[B1] < h[B2] < .... h[Bm] and h[Bm] — h[B1] <= x

now h[i+1] can at max be x, So, if we add it to B1 then abs(h[i+1]+h[B1]-h[Bm]) <= x. So our condition holds always.

Nice prove. thanks. Can you share your thought process for solving this ? Like how you approached this problem before coming to final solution ?

Initially i just tried random greedy strategies but got WA. Then i thought of somehow using the fact that each height < x and tried proving a greedy approach.

As every height is <=x as mentioned in the question and also we are filling blocks in sorted order of their heights, the maximum height between 2 stacks will always be

atmost1(because we are filling all the m stacks each with a block and start the next iteration).So, as the size difference between stacks is

atmost1. The difference between the stacks will always be the block which we are keeping at the top as it was mentioned each block is having height <=x filling this way will always give our answer.Hope this helps :) Please correct me if there are any mistakes.

For C, just sort by block lengths and assign to each stack.

For B, divide by 2 and 4, and see if number is a square.

B — If I don't FST, if dividing by 2 or 4 gives you a square (number) its a yes C — no idea I kept WAing

Assuming that I will not fail system tests.

Problem B:Notice that we can only form squares using 2 or 4 isosceles triangles. So just check if the given number of triangles is divisible by 2. If it is, then check if (n/2) is a perfect square. (We can form a square of size sqrt(n) considering 2 triangles as a single block). Now, if this fails then check if n is divisible by 4. If it is, then repeat the process above. The answer in any other case is NO.Problem C:I have done this greedily. Using a priority queue, I always select the tower with minimum height and add the blocks in decreasing order after sorting. After adding all the blocks, I check if the difference between the minimum and maximum height is smaller than or equal to x.Did the same for your C solution, let's hope we pass!

Best Explanation for Problem B

how to solve problem D?

My Approach : (Got All Clear) At first cancell all the matches on left and right basket. then in left basket if you have 2 socks of same colour you can move it to right baket to make pair, so remove the same colour socks and increment counter. do the same to right basket. At the end print(count+ max(remaining_leftBasket , remaining_rightBasket)

Used HashTable (Python 3)

Remove all the already matching pairs as they do not affect the overall answer.

Now, check if number of left socks = number of right socks, then the answer is simply the number of left socks (this happens because we have already removed matching socks and hence we can just change the color of socks from any one leg to match it with the other leg)

Now, we know that we have to transfer some socks from one leg to the other.

Observation:It is always better to transfer socks which form a pair.Example:Consider we have Left: 2 2 1 3 Right: 4 5 Now, we know that we have to transfer one sock from Left to Right, and it will be best if we transfer sock 2 from left to right, as it then forms a pair with the one sock 2 which would remain in left.Now, after transferring greedily, we again remove the matching pairs of socks in left and right. Now, if the remaining number of socks in left and right are same, then the answer is simply number of transfers we made + number of left socks (we change the color to match the right socks as we already have removed the pairs). If the number of socks are still not the same, then we can simply transfer any socks from the pile having greater number of socks to the other and then change the colour of the remaining socks. In this case, the answer becomes the number of transfers we made earlier(greedily) + greater pile size.

Explanation for Problem D

How to solve E ???

Lets hope the pretests for F are strong :)

Could you give me an insight to your approach? I would really love to understand how to approach such a problem.

Video Tutorial A:https://www.youtube.com/watch?v=1-6DoXfjc1I

how to solve problem no D?

Just a few couple thousands...

lol....I wrote that by mistake.Edited later on.Can you please share the approach of problem D?

Explanation for Problem D

How to solve F orz... I try to merge two nodes $$$u$$$ and $$$v$$$ which $$$a[u] + a[v]$$$ is maximum.

As long as initially $$$\sum_i a[i] \geq (n-1) x$$$ and the graph is connected, there is always a road you can build, no matter which roads you build and in which order. This means you can discard all edges but some $$$n-1$$$ that form a tree.

Then, start doing arbitrary possible operations. Maintain in every component the values $$$a[j]$$$ for the components $$$j$$$ of children of the component, and in a priority queue the maximum current value $$$a[i] + a[j]$$$ over pairs (component $$$i$$$, component of child of $$$i$$$).

Complexity is $$$\mathcal{O}(n \log^2 n)$$$ with small-to-large merges.

Did anyone get an FFT solution to pass for E? I'm having a rough time getting my code faster than 5 seconds sadly...

what is the FFT solution?

So we're going to work with ranges of computers that are off. Let $$$dp[k, t, end]$$$ be the number of ways to turn on a segment of length $$$k$$$ when toggling exactly $$$t$$$ computers, with $$$end = 1$$$ if the left end of the segment is the end of the whole array and $$$0$$$ otherwise (the only time both ends are the ends of the array is when $$$k = n$$$, which we case out). We assume that the right end of the segment is always adjacent to a computer that is already on Then our transition is

Basically, we are choosing to toggle the $$$i+1$$$th computer, splitting our segment into two. The lengths of these segments are $$$i$$$ and $$$k - 1 - i$$$ respectively, and we allocate these segments $$$j$$$ and $$$t - 1 - j$$$ toggles respectively. Then, for the remaining $$$t - 1$$$ toggles that we have, we choose $$$j$$$ of them to use on the left size, and $$$t - 1 - j$$$ of them on the right side. We can rewrite this as

which we can optimize to a convolution as follows: let $$$dp[k, end]$$$ be a polynomial in $$$x$$$, where the coefficient of $$$x^t$$$ is the value of $$$\displaystyle \frac{dp[k, t, end]}{t!}$$$ (our old DP). Let's fix some $$$k$$$ and $$$end$$$. Let $$$p(i)$$$ be the polynomial

and let $p(i)[t]$ denote the coefficient of $$$x^t$$$ in $$$p(i)$$$. Then, we make a new polynomial $$$q(i)$$$ (I know my naming is getting egregious), with

i.e. we multiply the coefficient of $$$x^t$$$ in $$$p$$$ by $$$t!$$$. Then, we let $$$r$$$ be the polynomial

Then, the coefficient of $$$x^t$$$ in $$$dp[k, end]$$$ is exactly

The overall runtime is $$$O(n^3 \log n)$$$. I think there's a way to further optimize this by doing some 2D convolution, but I don't really know how to do anything like that (or if it's even possible). The idea for all of this is based on generating functions, but I'm not very well versed with those either, so maybe some trick from those can be useful here.

Here's my code: 114957402. It runs in about $$$5.5s$$$ locally, and with some annoying optimizations I've gotten it a bit further down, but not by much.

update: I got it to pass (114970160) with some optimizations + pragmas

No need for FFT. You work with segments of manually toggled computers, with single automatically toggled ones in between. Then DP states are (first $$$i$$$ computers toggled, the last one is automatic or right endpoint of a segment, number of manually toggled computers up to computer $$$i$$$), and there are just $$$O(N^3)$$$ state transitions.

Can you explain the transitions? i might not solve it on my own.

If the $$$r$$$-th computer is the right end of a segment (so $$$r+1$$$ would be automatically toggled or $$$r=N$$$) and the $$$l$$$-th is its left endpoint, then $$$dp_{l-1,k} \rightarrow dp_{r,k+r-l+1}$$$ for each $$$k$$$ (number of manually toggled computers before $$$l$$$).

You can solve this task without FFT.

We can see on array as blocks set of consecutive computers.

Let write the 1st DP f[len][cnt] — answer for on first len computers, where cnt computers we turned on themselves. Calculating DP looks like f[len + bs + 1][cnt + bs] += f[len][cnt] * fullblock[bs] * C[cnt + bs][bs], where fullblock[bs] — number of permutations for turned on by hand bs computers among bs computers.

For fullblock[bs] we need in the 2nd DP. dp[len][last_pos][flag] — number of permutations with len computers, there is computer with index len stay in position last_pos, flag = 0 when position of index len — 1 stay to the left of last_pos

Phoenix Played with all of us

My usual tactics have failed me D:

lol same :D

shitiest ABCD. also the scoring distribution was bullshit. 2000 fucking points for D :\

damn, you have crazy expectations for problems..

No,u just set them very poor and there is no wrong in accepting that. Problem D is not supposed to be solved by 4.5k people. Thats just dumb problem

Then why did you spend almost 2 hours on it and get it done only from a 7th try?

The first comparison criteria among the participants is the number of problems they solve, second is the time they spend on each problem and the amount of penalty they receive, easier problems may fade the impact of the first criteria but the second still stands and that's what makes you one of the worst second division participants of this contest.

It was a good contest dont let them tell u otherwise!![user:FieryPhoenix]

Very shit contest for div2 participaants indeed (seeing most of them usually do upto D). Stupid problems, just stupid

I wonder that if there is a contest without graph theory problems......

hmm how F checker works?

It uses union-find to track connected components of the graph, augmented with the amount of asphalt in each component (stored at the roots of the union-find data structure).

How to solve E ?

I used dp to find all the possible combinations of switches that we manually turn on. For example, X_XXXX_XX_X, XX_X_X are some valid sequences. The gaps represent switches that automatically are on. It is easy to see that the size on contiguos gaps will be atmost 1.

Now, for each such combination we've to find the number of permutations to fill the X's. To do that I used 2 more states, {position, continuos X's till pos, number of skips}. I use skips to calculate how many were manually ONed before the contiguos Xs until pos.

Now another important thing to note is that, The number of permutations to arrange r numbers such that theres no gap between them is 2^(r-1). (Try to prove it)

After that we just have to use some more combinatorics to combine 2 contiguous segments of X's in our dp. There will only be 2 transitions, pos->pos+1 and pos->pos+2 (skip->skip+1). Rest of the details should be clear in my code

Submission

I am getting Memory Limit Exceeded using multisets in problem D. Please have a look at my code: https://codeforces.com/contest/1515/submission/114956539

Why using map instead of multiset do not give this error?

This may be helpful

Never ever gonna use multiset

mgmggmgm greedies and observations go brr

WA on pretest 3 on problem D again and again.

Pending System Testing for everyone?

Passed samples of problem E just before the end of the contest, submitted it and got a

`MEMORY_LIMIT_EXCEEDED on test 1`

. And there's not enough time to fix it. :(The retribution of bad habits comes.

rainboy orz.

There is something called greedy algorithms, Problem D was based on ultra greedy Algorithm.

No it was based on mega ultra shit algorithm

Here I see a blue coder complaining that D's solution is shit and tried 7 times to get AC.

It felt like programming some robot to jump, move, etc in a game using too many if else statements.

I checked my solution to D, found only two if statements,

That's because you used for loops instead and took 30 minutes to optimize if else.

Is using loops against the rules ? I think algo-police would be on their way to catch everyone using loops.

A to D seemed doable but still I was only able to get A correct, looking forward to editorials to understand the missing cases.

Idea for E?

The setters wanted to emphasize "Problem C uses constructive algorithms" (Some other problems also have two same tags)

Seems like someone is trolling

EDIT: Ah, seems like a bug lol

This is not the first time I think this is a bug

A-D weren't very pretty problems but weren't too bad either. I liked E though.

In case you're curious about B: it should be obvious that since the sides of triangles are $$$1$$$ and $$$\sqrt{2}$$$, the side of the resulting square has to be $$$a+\sqrt{2}b$$$. Then, the area is $$$N/2 = a^2+2b^2+\sqrt{8}ab$$$, but since $$$a,b$$$ are rational, $$$\sqrt{8}ab$$$ can be a rational number only if $$$ab = 0$$$. That means $$$N/2 = a^2$$$ or $$$N/2 = 2b^2$$$.

Thank you setters for a very shitty round. Enjoyed every inch of it. Please dont make such shit problems in the future

Stop bullshitting everywhere. Contest was good, maybe your ass got burned with D. So keep your shitty opinions to yourself, ultrashitposter.

Ok, I agree that its my rage but I dont get how a person who didnt even do the contest live is giving feedback.

I wrote from my other account and solved A-D.(I just created that a week ago to see how I performed if I started anew). You can verify in the discord server if youdoubt me, I already discussed it there.https://discord.gg/5DCnEpbB

Well, first of all alting is against the rules, better wish mike doesnt read it message lol.

Your account seems alt also,why don't you have your name, country name in your account. So go on and sue me .

Hope this might helpStop bullshitting everywhere. Keep your shitty opinions to yourself, ultrashitposter.

Yeah, glad I was able to help you, keep extending that help to others.

Wow, such a balanced contest

link to solution.

Can someone tell me why this code is failing even for the first pretest for problem C. It is running fine in my local.

Any help would be very very much appreciated. Thanks in advance.

This was a good contest for me

I'm in love with my solution to I, so I'll share it in case it's different from the model solution:

Ofc. let's sort the diamonds by the order we we'll pick them, the leftmost item is the first to pick. Let's define $$$f(x)$$$ as the maximum integer $$$k$$$, such that $$$2^k \leq x$$$.

Let's build the segment tree on the sequence of diamonds and for each query of the third type let's run dfs on it. Ofc. in leaves we can normally consider the diamonds, but it would be too slow, so we are looking for a speedup. Let's split into two smaller segments each time when $$$f(size~of~our~backpack)$$$ will decrease somewhere in it. If it won't change, then let's do something smart to skip the whole segment in $$$O(1)$$$.

When will it decrease? It'll happen for sure if in the segment that we currently are is some diamond with weight $$$w$$$, such that $$$f(w) = f(size~of~our~backpack)$$$ and $$$w \leq size~of~our~backpack$$$. It will happen also if the sum of the weights of all diamonds with $$$f(weight) < f(size~of~our~backpack)$$$ is at least $$$size~of~our~backpack$$$. In these two cases let's just solve the segments recursively. If neither of the conditions hold, we know that we'll simply take all the diamonds with $$$f(weight) < f(size~of~our~backpack)$$$.

Final observation: $$$f(size~of~our~backpack)$$$ will decrease at most $$$\log$$$ times and for each time it decreases we we'll do only $$$O(\log(n))$$$ splits, so the complexity for each query will be $$$O(\log^2)$$$. Let's then build $$$O(\log)$$$ segment trees. Each of them will keep the minimum weight of a diamond with $$$f(weight) = id~of~tree$$$ and the sum of weights and values of diamonds with $$$f(weight) \leq id~of~tree$$$. We can modify these values in $$$O(\log^2)$$$ per query and the query about finding the score also can be done in $$$O(\log^2)$$$ then.

Thanks for the contest! The problems I read were all pretty nice. I'm a bit salty that I failed E and didn't think of working on F instead but that's part of the CP experience :)

WTH is wrong with this solution for B??? Input can't exceed 1e9, what am I missing and why does it fail test 5?

codeEDIT: Fuck me, I'm dumb.

Isn't it because your set

`s`

will contain numbers up to only $$$10^6$$$ instead of $$$10^9$$$?fuck u motherfuckers, it was the most bullshit global contest ever. please dont let this son of the bitches make contest, MIKE.

fuck u motherfuckers, it was the most bullshit global contest ever. please dont let this son of the bitches make contest, MIKE.

Update: This was a poor attempt at starting a copypasta designed to make fun of the original comment. I didn't even participate in the contest and I liked the problems.

Ok then why don't you become master and show everyone how to set contests ಠ_ʖಠ

(╥﹏╥)

Can someone tell , in problem D, test case 3 what is test 164. Thanks in advance.

When you fix the bug(1 char bug)in your code 15 seconds before the contest end and then your internet decides to load the page very slowly and you miss submitting the problem by 1 second.(It turns out it took me less than a minute to ac in upsolving :( now I will lose rating instead of becoming IGM)The bug was that I used variable xx instead of x at place

Yup, worst feeling ever :/

next time for sure kingSounds like yet another reason for giving variables a meaningful names :)

Omg, I feel so sorry for you! ;((

no brain me solving question A by shuffling the array multiple times codeforces: we wont let u cry this time, Accepted

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

a few hours

tfw OEIS doesn't work

might be the reasonI coded up a brute force solution and generated the answer for N up to 20. Plugged that into OEIS. Nope lol.

I have no idea why I even tried. Great job problem authors! It's your win this time :D

Why system testing is happening again?

Today's global was the coolest of all that I handed in. Thank you very much FieryPhoenix ! I will wait for more competitions from you

Great contest! (and thanks for the IGM)

orz

https://codeforces.com/contest/1515/submission/114966463 why does this give tle on b problem? plz explain its sqrt(n) only.

sqrt(n) can be found in O(logn). You have written O($$$\sqrt{n}$$$) logic

Editorial has mentioned sqrtn solution also..

It has mentioned that it is possible to write an O($$$\sqrt{n}$$$) solution, not that it will be AC. For $$${10^4}$$$ test cases with $$$\sqrt{10^9}$$$ complexity, your solution won't pass the time limit.

EDIT: I don't get why the comment is getting downvotes. I still stand by my statement, O($$${10^{8.5}}$$$) should not get an AC.

People have ac with square root solutions also.. Plz see that as well.. They have the same function as I have written

Can you share those solutions?

https://codeforces.com/contest/1515/submission/114909506 You can look at this After the constest I used fast io in my code aand submit it again but tle only...so fast io is not problem here ...

https://codeforces.com/contest/1515/submission/115008964

This passed. I just updated the way you were checking if a number is a perfect square or not. Though I'd advise against writing O($$${10^{8.5}}$$$) complexity as then it depends a lot on the constant factor of your code as is in this case.

But this is not right ..what diff does it make ..??I should get ac in that..

The diff is that you're performing 2 divisions (modulo is division) for something that can be done in one multiplication. The constant factor is less in the latter.

it hardly makes any diff at all

It makes a lot of difference when you write something of O($$${10^{8.5}}$$$). The most expensive operation in your code is sqrt and this change decreases the number of operations required to half of what it was. Therefore, avoid writing something that could be TLE'd because of constant factor.

Sometimes constant optimization really matters.

The problem is the line

`#define int long long int`

. Computation and I/O is more costly for long long integers and so, often the overhead in such cases causes a TLE.I just commented out that line and it got accepted.

114980681

somebody please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.com/contest/1515/submission/114967116

You might be missing some key points. Link to Explanation

114951091 Don't know why getting Wrong Answer. Can somebody find a testcase which gives wrong answer to the code.

How the answer in following test case is 3 and not 4

10 6 4

4 5 3 5 8 5 5 10 10 4

With initial socks $$$[4, 5, 3, 5, 8, 5]$$$ and $$$[5, 10, 10, 4]$$$,

thanks:)

can anyone kindly explain why greedily adding the 2 smallest values in the array not work in c.

like if we have [2,4,7,9,10] and if we want 3 block just add the smallest 2 and replace, by this we get [6,7,9,10] and then again do the same thing, thus getting [13,9,10] the max difference is 4 which is okay, if we were to do any further operation we would have done that to 9,10

but this gives WA, can anyone suggest a counter example

Here's a test case that fails your code:

The towers produced by your code have heights $$$4$$$, $$$2$$$, and $$$2$$$.

wow thanks, couldn`t figure out why the above algo didnt worked and hence struggled in the contest too. is there any way to find countertest to your algorithm or just you have to think about it for long

I just tested with many tests until I found one that is not correct. Since your idea seems correct, I suspected that it was probably wrong on some kind of special cases.

someone please explain why i am getting wrong answer in test 4 in D . my submission: 114958100

Commenting this again because did not get any response in the previous comment.

Solution

Can someone explain why this solution for problem C is failing even for the first pretest. It works fine in my local machine.

you're not iterating through the whole vector, missing i = m. So, one value you're getting is just garbage value.

Also, you might have to sort it in descending to work.

Please help in Problem D, I cant understand where it's going wrong. My code

Got this message from System

Attention!

Your solution 114875501 for the problem 1515B significantly coincides with solutions

nmp/114873698, calabashgirl/114875308, bnkalya1502/114875501, sleeping_samurai/114904548. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.First of all , I do not even know who the above mentioned people are , neither did I used any online compiler . Although I agree that the above codes are similar but this is probably a coincidence because for an easy problem like this (given that there were 10K+ participants) , there are a limited types of implementations possible .

False Accusation of cheating in Codeforces Global Round 14. Got this message today. MikeMirzayanov

My Submission: 114904088 ......His Submission: 114880136 Problem B was quiet straight forward, and there are not much ways you can write the code for this problem if you try the same approach. In this case, me and shart23 happened to use same approach for this problem. This is just a mere coincidence, and is quiet shocking for me becasue my solution has never been skipped or hacked before. Will this be rectified or I have to lose +43 for this contest ?. PS — I had a doubt, why am I the only one between the two of us who is penalized.

Both of these codes are line by line the same except variable names.

Yeah, I know. And that's mere coincidence. For such simple problems, the probablity of people writing similar codes is much higher.

System

I have to talk to you about that i have got a message for the "System" of codeforces that my solution is same as the solution of JB-James-Brown-/114935692, acktron/114935957.

and for this as well 114894526, acktron/114894659.

I want you to tell that those were just problem A and C which were same. There code was small so this is a coincidence that our codes are same please leave as we will not do this again. Sorry if i did some thing wrong pls forget it.

I am is having a coincidence that my solution is same acktron for A.

[user:system]this is the coincidence.

Congratulations to tshirt winners!

who are you

its_Atrap

my address is 420 frozen wasteland, canada. my credit card number is 97280396319932. when can i get my tshirt???

Congratulations to actual tshirt winners!

fake news again?

the random thing is kinda sus XD

but one of my friends names is in the list so i hope its true : ))

No, this time 100% authentic. Congratulations!!!!!!!!!!!

Hmm, this table seems to be almost the same as the list below.

So when will the real list come out?

My code is not running since I have proper network connecton

When will t-shirt winners be announced?

I have made a list,according to this code:

T-shirt winners:

Spoiler1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 57 90 95 102 124 131 169 186 195 223 228 255 260 262 311 322 323 337 362 479

What seed did you use?

Usually,seed is the score of rank 1.

But isn't it the score of rank 1 in the contest after the round?

What is "contest after the round"?