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, apeiya, xay5421, NemanjaSo2005, applese, bxhnb, fr200110217102, Sulfox, DF_3Mz 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 MagicalFlower 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
...
and it has indeed changed
Finally a div1+2 round after half month.
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
fandlare connected in chrome, so it uses bfs to fill letters!Hope I will solve A anh B @@ As a participants, hope everyone have the best work!!
I will AK it using Genshin Impact:)
（
.
Gigafrog
Frogachad
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"?
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!!!
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?
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.
jiangly! best of the best
I'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
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.
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.me/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.
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 = 1e9will solve the overflow issue? BTW I don't think overflow is the problem, because I have submitted the code with a value ofrightless 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 = 1e9is also bad, for example, whena=2,b=1, h = 1e15Same 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
1e18which may lead to overflow. Thanks!https://codeforces.me/contest/1810/submission/200007256
Why did I get WA?
Can anybody Tell me why my code fail in Problem C
https://codeforces.me/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.me/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
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!
Can you explain the merging part of your solution for E please?
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
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.me/contest/1810/submission/199982867
Any help is appreciated.
Oops never mind. Just integer pool/boxing in Java.
https://codeforces.me/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
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 .
@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.
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
I was notified the my solution for the contest match with some other solution in problem A. When this round took place I was not aware about how to address this issue so I am commenting now. Your solution 199973419 for the problem 1810A significantly coincides with solutions shreyansh_125/199969542, Mr.Roamer/199973419. Look at the solutions , I am shocked that the plag checker also checked Problem A , as it's code is so simple everyone can write it's code similar to mine. It's just a coincidence that we used same variable names (which are also common names). Pls check both solutions I did not copied any code.