Hello, Codeforces!

I'm very glad to invite you to participate in CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Mar/31/2023 17:35 (Moscow time).You will be given **8 problems** and **2 hours** to solve them. The round will be rated for everyone.

I'd like to give my sincere thanks to:

74TrAkToR for the wonderful coordination!

Sulfox for the help with the statements.

Suika_predator, SSerxhs, LLL_2820, xay5421, NemanjaSo2005, applese, bxhnb, fr200110217102, Sulfox, CCSU_DZX PaperCloud, CedeaT0, Kath1031, jcccc, dyxg, tzc_wk, xiaoziya, qiqi20021026, Pointy, HorizonWind, ilyakrasnovv, ShmilyTY, njupt_lyy, rsj,hzr, p_b_p_b, ak2006, flakes24, Milesian, pb0207, _Vanilla_, Lavine, alwyn and flowerletter for testing the round.

MikeMirzayanov for the great codeforces and polygon platform.

**You**for take part in the round.

Hope everyone can enjoy the round!

**UPD**: The tutorial is here.

And here is the information from our title sponsor:

*Hello, Codeforces!*

*We, the TON Foundation team, are pleased to support CodeTON Round 4.*

*The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.*

*Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.*

*The winners of CodeTON Round 4 will receive valuable prizes.*

*The first 1,023 participants will receive prizes in TON cryptocurrency:*

*1st place: 1,024 TON**2–3 places: 512 TON each**4–7 places: 256 TON each**8–15 places: 128 TON each**…**512–1,023 places: 2 TON each*

*We wish you good luck at CodeTON Round 4 and hope you enjoy the contest!*

Auto comment: topic has been updated by RDDCCD (previous revision, new revision, compare).As a tester, give me 2147483647 TON.

Unfortunately, they only award prizes that are powers of 2.

As a tester, give me TON.

only upvote here.

As a tester, give me TON.

As a tester, give me TON.

As a member, I want to take from 1 to 1023 places and get TON.

As a !tester, give me NOT.

As a tester, problems are great, recommend everyone to participate!

Please don't downvote.I apologize for my comment.

flakes24 ORZ

no u

May this will be my color change contest

Spoiler...

and it has indeed changed

Finally a div1+2 round after half month.

But tomorrow is April Fools!

But the provincial team selection contest will be held in tomorrow morning. I'm going to miss this round :(

Isn't this usual nowadays ?

Hope I can bounce back from my horrendous performance last time.

bruhh so like me

Gl. Hope you dont fail system testing again. (:

Thanks ;)

Nostalgia hit me.

My first div1...ready to face the challenge

so excited !As a tester, problems are educational and wonderful, hope everyone can enjoy

TON is about 2.10$, Thank me later :)

hope to be Expert

You are already Expert bro . What are you talking about? This time you will reach it . I will try not to blunder this time.

As a tester, give me TON.

How are the first two letters of your nickname black (at least in chrome mobile)

Ligature

Ultra legendary grandmaster

`f`

and`l`

are connected in chrome, so it uses bfs to fill letters!Hope there will be some good problems and a positive delta.

Hope I will solve A anh B @@ As a participants, hope everyone have the best work!!

I will AK it using Genshin Impact:)

（

as a newbie give me TON

Gigafrog

Frogachad

Lucky

Where will these ton tokens be transferred? I mean we haven't filled a wallet address whole registration neither is there a link to put our wallet address on website or any other place.

in past times, the wallet was asked after only those who won something

you can put your ton wallet address in your account settings

Can anyone explain why we can read many times ".... give me a TON"?

if you win, sell quickly... i have seen so many of these ponzis collapse

As a tester, I think this contest is very worthwhile to participate in. I hope everyone who join this contest can get satisfactory results.:)

We need a TON of positive delta rating!

I hope to reach 2100, and I wish everyone all the best!!

Will try to cross 1500 this time. Looking forward to solve upto 4 problems.(atleast 3).

facing long in queue problem!!

Will a scoring distribution be announced?

I'm jiangly fan,jiangly is No.1!!!

Wow!Chinese round!

I really wanna reach 1900 today. The mark has been psyching me out for so long now. I dont wanna care about my rating!!!! I wish me and you all the best!! (I just wish it a tiny bit more for myself :D)

Definitely, you can. Best Wishes.

Where's

score distribution?Where's score distribution?

Hoping to solve at least 1 problem this time.

What Happened to tourist ?

No worries. Anything can happen. As I'm a tourist fan, I believe that tourist will beat No.1 next time.

Yeah i think tourist uses rainboy technique else he is no one until d problem

jiangly! best of the bestI'm very excited to see editorial for task H!

Good round! Sadly I ran out of time for D and I think I would have been able to solve with ~10 more minutes.

hard round.

Problems were great overall, but needing to use Fibonacci Heap for E in Java to not TLE was obnoxious.

standard heap runs fine in pypy

you're back to doing it with java again ?

What exactly was your solution, you should be able to use bucket sort since values are in $$$[0, n]$$$.

Small to big with a disjoint set, where you merge the smaller priority queue of edges into the bigger priority queue every time you need to merge two nodes.

Very convoluted. Suppose you add all vertices with $$$a_i = X$$$ to the graph with all $$$a_i \leq X-1$$$. If you can defeat $$$X$$$, you can defeat the component. If you can defeat $$$X$$$ now, you could have defeated $$$X-1$$$ before, which means you were able to defeat the component. You can maintain if the whole component is defeatable together with its size in DSU.

Good round!!

Problem B is the same problem as one of the problem in Constructor Open Cup Contest yesterday

Ah... An interesting coincidence :( The two contests are so close.

Actually there was a small difference: solution was guaranteed in Constructor Open Cup, and today there was a -1 option.

The time of which of the submissions counts to the result on codeforces? The first or last?

Historic Submission: https://codeforces.com/contest/1810/submission/200000000

nightcrawler0112 Orz

had it been AC ;) But yeah great achievement!!

B is almost absolutely the same as a problem in Constructor Open Contest 2023 which was yesterday

Submited D in last second but system didnt register it, also B is harder than C or D

I just drew a binary tree from 1 and got the greedy idea, and I found B quite easier than C (just my opinion) Didn't even get time to look at D

Problem E is solvable using "Kruskal Reconstruction Tree" technique. The weight of edge (u, v) is max(a[u], a[v]). After we built the tree, we climb from leaves with a[u] = 0 and check if we can climb up to the root in the reconstruction tree.

It's also solvable with Boruvka's algorithm + BFS

I solved it with DSU and merging sets

Also solvable by shuffling all zeroes and performing BFS from each of them. The only optimization is to start only from zeroes which we had never reached before.

Wow, that is smart. What is the expected complexity of your solution?

I would like to know that too.

Edit: Even without shuffling, this algorithm will visit each node at most $$$\log(n)$$$ times. So the upper bound complexity is $$$O(m \log^2 n)$$$. Maybe with shuffling we can get smth better.

I did this too: I think it's $$$O(m\log n)$$$ since the expected number of 0s you start from is $$$O(\log n)$$$ and each time you can explore almost all the edges in the graph?

Could you explain how the expected number of 0s we start from are $$$O(log n)$$$ ?

Correct me if I'm wrong, I think you don't need to shuffle the zeroes as the worst case will only visit all N nodes at most log(N) times.

Yeah, got it, you are right. So we don't need to shuffle and the overall complexity is at most $$$O(m \log^2 n)$$$ using priority queue inside BFS.

why are we visiting each node at most $$$logn$$$ times ?

This complexity analysis is so hard. I came up with the solution immediately but didn't dare code it because I though it was $$$O(n^2)$$$. Now I play around some linked-list cases and can see that it is indeed impossible to reach $$$O(n^2)$$$, but can you please elaborate on how to prove $$$O(mlog^2n)$$$?

Edit: it was in the editorial.

I did the same thing. Here is my solution. 200012713

I upsolved the prob using a similar strategy, But I didn't realize that that optimization would be enough, so after performing each BFS, I combined all visited nodes into a "super-node" to make sure that i didn't iterate over each node too many times. The core logic is super similar tho.

All this time I prepared to solve C. Now I managed to solve it but still getting a negative delta lol. Gonna upsolve D

Any hints for D?

try to keep the minimum and maximum possible length of the tree after each query

thanks, was very close to this just made some calculation mistakes

How to do E?

In question D, I was trying to find number of days taken by snail to reach height h, given a and b using Binary search. Is something wrong in my approach as I am getting WA in TC5.

probably overflow on

`(a-b)*(mid-1LL)`

So, taking

`long long right = 1e9`

will solve the overflow issue? BTW I don't think overflow is the problem, because I have submitted the code with a value of`right`

less than 1e9. And still I got WA in TC5.IDK, I did

`long long right = 2 * 1e18 / (a-b)`

to avoid this issueThanks man! Overflow was problem. Got it Accepted.

I think setting

`right = 1e9`

is also bad, for example, when`a=2,b=1, h = 1e15`

Same problem with me! But why BS doesn't work here??????????????

It is equivalent to the direct math formula, both calculate the same.

It is working well. You just have to be careful of the overflow.

I was already careful! My binary search limits is 0 and 2e9 Submission: 200007394

Update:The problem is that we need the limit to be upto`1e18`

which may lead to overflow. Thanks!https://codeforces.com/contest/1810/submission/200007256

Why did I get WA?

Can anybody Tell me why my code fail in Problem C

https://codeforces.com/contest/1810/submission/200015122

Firstly,You haven't considered all possible start mex values(according to your code you have checked for 1 and 2) and even after this,all possible combinations of insertions and deletions that are possible are not considered (try looking at the editorial or look into my submission for a better understanding of it) Happy Codeing:)

Any ideas why this D is failing pre-tests? I spent 1 hour debugging and could not find the bug:

https://codeforces.com/contest/1810/submission/199997167

I think the tree height can be more than

`2e9`

(for example if a snail has $$$a = 10^{9}, b = 1$$$ and $$$n = 10^9$$$)thank u !!

I got 7 WAs on D trying to use binary search before realizing it was just math...

is Div2D solvable with just math?

Yes

Determining whether a node is good (you can start from the node and reach the entire graph) is just implementation.

The solution of E is quite straightforward when you observe that if a node is not good, the nodes it can reach are also not good.

Edit: Systest accepted, but not sure if there is an test case that will TLE this

Nice div1+div2 contest. Solved A-E. My solution of F passed pretest but it's very likely to get TLE on system test.

A: We just to need check if there's any i where a[i]<=i.

B: We can only get odd number by operation, so if n%2==0 there's no solution. Otherwise, we can represent (n-1)/2 in binary, and add 1 to all digits (for example: 17 -> (17-1)/2=8 -> 8=1000(2) -> answer is 2 1 1 1).

C: First we can remove all numbers and add single 1, which costs n*c+d. Otherwise, assume the size of the final permutation we get is k (and k>1), and there are m missing numbers in range [1, k] in the initial array. Then we need to add m numbers and remove (n-(k-m)) numbers, the cost is c*(n-(k-m))+d*m = c*n + (c+d)*m — c*k. If we let k+=1 and m+=1 (which means, k+1 is a missing number in the initial array), the cost will increase by d, so in any optimal answer, k must be a number in the initial array. So we can iterate for every possible option of k and get the answer.

D: Implementation problem. We just need to maintain the upperbound and lowerbound of h for each type-1 query, and for type-2 query we need to check if the answer for (h_max, a, b) and (h_min, a, b) are the same. Be careful for case a>=h.

E: DSU. We sort edges (u, v) by the value of max(a[u], a[v]) and add them by this order. First mark all nodes with a[u]==0 as good. WLOG assume a[u]>=a[v]. When mergeing (u, v), if v is good and the size of component of v is not greater than a[u], we mark all nodes in the component of (u, v) good. To defeat all monsters, we need the graph to be connected and all nodes are good.

F: The answer is ceil(log_m(sum(m^a[i]))). We need to maintain the base-m representation of sum(m^a[i])) by a segment tree, and update it by binary search.

Update: Upsolved F with atcoder library: 200024728

Amazing performance today! (despite FST!)

FST((

Anyways congratulations with almost becoming red!

gratz! Great performance anyway, amazing result of your constant upsolving

I was so close to your C's intuition, But I didn't think of starting from first element I thought of starting from last element, Oh God! It's demotivating to get really really close to the solution and still not get the answer, I think I need to practice a lot as I am not consistent, so I need self discipline to achieve more. I do hope I become Pupil next month. Today I solved both A and B in under 32 minutes, So I think I can improve.

Can you please explain logic behind (n-1)/2 in B?

Let f(x)=(x-1)/2 and see how operations affect f(x):

Operation 1: x --> 2*x-1

f(x)=(x-1)/2 f(2*x-1)=x-1

which is: f(x) --> 2*f(x) (put a 0 after a binary number)

Operation 2: x --> 2*x+1

f(x)=(x-1)/2 f(2*x+1)=x

which is: f(x) --> 2*f(x)+1 (put a 1 after a binary number)

For problem B, I didn't get this point "Otherwise, we can represent (n-1)/2 ". Can you explain a little bit more?

Yeah i dont get it too lol

I think he is trying to say that since number is always odd as we progress from 1 to our desired number n, that we can go from n downwards in this fahsion:

we could get to n etiher by number (n-1)/2 or by number (n+1)/2, whichever of them is odd(other one always isnt) is the number from which we came to n

Could you (or someone else) please elaborate the logic behind your algorithm for E? I don't seem to understand it at all. Thanks!

Although managed to solve D and probably will get positive delta, still problem D was awful in my opinion. There was nothing interesting about it. It just required being extra careful, which is very annoying.

A was ok, B and C were nice.

I don't understand problem D, anyone help me:((

Me too

Problem D is really orz

As a contestant who won 4TONs, please give me TONs

Jiangly!!!

May I know why my problem A's submission is still in pretest passed stage?

weak pretests on E? I passed pretests in 295 ms and seemed to have failed systests :(. Hurts more since I was going to reach CM.

Looks like this is on me. My solution is the same as edi's except I set visited as 0 for all nodes each time I bfs instead of setting visited as 0 only for nodes visited in the last bfs which significantly worsens complexity.

Still sad how the pretests didn't catch this.

A round with a 200000000 parcel?

Congratulate nightcrawler0112 for submitting the 2e8-th solution 200000000 in this contest!

wish it was an AC

Did you figure out the test case which it fails?

yeah. if c,d >int_max as i initialized ans=int_max

Due to a network failure, I accidentally submitted my solution to problem D twice (see 199967726 and 199967904) and got a resubmission penalty. Is there a way to get my score back?

Also, hats off to everyone who prepared this fantastic contest, and I'm excited to finally become red after 5.25 years of cp!

congrats more to see from you

Orz

Awesome contest (at least problems A-D)!

However I have a question regarding the problem D. This is what some test case (second test case in Example) can look like:

The answer is

Why is the second number $$$-1$$$, and not $$$3$$$?

From the first event we can get that $$$h=6$$$. That is the only possible solution for $$$h$$$. We have $$$h$$$ and in the second event we are given $$$a$$$ and $$$b$$$. We can now calculate $$$n$$$ with formula $$$n=$$$ $$$\lceil \frac{h-b}{a-b} \rceil$$$ and that equals $$$3$$$.

from the first event you can get that 1<=h<=6

can you please explain 2nd event also? It will be helpful for us.

from the first event you know that 1<=h<=6 in the second event if h=4 for exampe it needs 2 days to reach the top but if h=6 it needs 3 days to get to the top thats why you can't know how many days it needs.

Thank you very much, now I got AC.

Anyone knows why my C fails?

https://codeforces.com/contest/1810/submission/199982867

Any help is appreciated.

Oops never mind. Just integer pool/boxing in Java.

https://codeforces.com/contest/1810/submission/200032316

Is it suspicious if someone submits D and E with 8 mins gap and there's different style of giving brackets in all the submission (submissions of D and B don't have extra space before curly braces while E, C and A have)

How do we receive TON, if we ranked below 1024? Did we have to fill some form or will we automatically receive mail for the same?

Isnt the test case 5 of C wrong, the min cost comes out to be 22, not 20.

Dropping a duplicate 4: 2

Inserting 1,2: 2*8 = 16

Dropping 7,8: 2*2 = 4

Total = 2+16+4 = 22

while the answer is given to be 20. Can someone help me with this, if I am wrong? Thanks

delete all the elements then insert 1. it costs 20.

Ok Yeah, thanks !

It is also an option to delete all elements and add a $$$1$$$.

Finally turned purple with this contest. Thanks for the Amazing round!

D was undoubtedly unclear problem statement. Much more clarification was needed

Can somebody point out a case in problem D where I get WA :((( Pardon me for my bad english :((( 200059851

How and when do we recieve toncoin prizes

Can someone please help me with my submission of problem D submission Thank You

Try avoiding ceil() function. ceil() has some precision issues for large numbers. That's why your answer is wrong for large input. Use below, it will get accepted.

void tim(ll up,ll dw){

if(l==-1){

cout<<"-1 ";

}

else{

ll lb=1+((l-up)+(up-dw-1))/(up-dw);

if(l<up)lb=1;

ll ub=1+((r-up)+(up-dw-1))/(up-dw);

if(r<up)ub=1;

if(ub!=lb)cout<<"-1 ";

else cout<<ub<<" ";

}

}

Thank you so much I will remember it .

My D solution has been giving an error for 887th test in test case 2. I haven't seen the tutorial yet. Can someone give me a testcase for which it is giving a wrong answer ? This is the submission ID 20011391 : — https://codeforces.com/contest/1810/submission/200113916

@RDDCCD

RDDCCD

EDITORIAL IS NOT ACCESSIBLE.I had written one comment on yesterday's editorial. After which I had received some downvotes. Is that why I am banned from seeing an editorial page...

i dont think so, i cannot see it either :3

Edit : editorial is open again

Ah, that's maybe because I was wrting the editorial of H at that time. I don't know it will make the editorial unaccessible :(.

Anyway, editorial for H is finished now.

Can anyone please tell me why I am getting WA in the following solution for E? Problem E

For E, how can m > 0, if n = 1?

Can anyone explain why my code fails for E? 201160823 . I have tried to implement the editorial.

Has anyone received TON coins? When will it be released?

Do I need to do anything other than add my ton wallet to codeforces?

Not yet (TON't)

Edit: I just received it, thank you!

Am I the only one who didn't receive the ton prize?

It's been over a month now.

I have also not received it

Edit: received it now