Hello, Codeforces!
max0000561, a.nasretdinov and I are glad to invite you to our Codeforces Round 907 (Div. 2), which will be held on Oct/30/2023 17:35 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100.
On behalf of our team, I want to thank:
- Coordinator 74TrAkToR for invaluable help in preparing the round.
- Testers maomao90, LeoPro, SomethingNew, maks_matiupatenko, max0000561, yaroslav_n, glebustim, Vash_nick, Murinho, Topperoo, Alarick, priyanshu.p, Greg908, buffering, ventilator13, medved, zwezdinv, Rodionno for high-quality testing of the round and useful feedbacks!
- medved for excellent translations of the problems into English.
- MikeMirzayanov for amazing Codeforces and Polygon platforms.
And special thanks to my friends who have made a huge contribution to this round: Amir a.nasretdinov Nasretdinov, Maksim max0000561 Krylykov and Tanya medved Medved. Also thank you for all four years of friendship:)
During the round you will need to solve 6 problems. You will have 2 hours to solve them.
Score distribution: $$$500-750-1000-1500-2000-2250$$$
Good luck and, please, read the statements of all problems!
UPD: Editorial is out.
UPD 2: Congratulations to the winners!
Div. 1:
Div. 2:
Can't believe that mine is the first comment!
Wow, So exciting to see this round, I hope it will be interesting.
I hope I can reach Specialist.
Same
Best of Luck✨
Congrats
As a tester, the problems are cool and interesting!
We'll see.
After the contest I agree with you <3..
Score distribution .... Whoa ......
Point distribution suggests all problems could be solved by average Div-2. But history suggests, Point distributions can be deceiving ... :D
Is there anything implied in this sentence?
I think they mean you should read all problems
I think you're right.
They mean, there is a chance, that you haven't been able to read through all problems before the match ends.
as a friend of the author of the round, I predict that round will be great!
Message Notification system in telegram is very pleasurable for me . I almost forgot about this contest but telegram notification alerted me timely . Thanks to codeforces management system.
Kudos to 74TrAkToR for his decision about placing problem F at Div. 2 F!
He is the only coordinator who will make such creative decision!
Yeah. Isn't 74 good at ds?
Are you sure E and F should be in that order?
Lol, they knew F was easier than E
What was the idea of setting $$$1$$$sec TL in $$$D$$$???
982 ms
Clutched it
Yes! I really don't understand why you should put a $$$1$$$ second limit, it makes it very hard to pass a python problem or a completely unoptimized $$$O(nlog(n))$$$ solution in $$$C$$$++. It's just an idiotic decision to put such a limit from the author! On the other hand the task is cool.
wait you solved in O(nlogn)?
That is probably because you are expected to precompute something?
In problem D, how to optimize it from q*60*60?
You can do $$$O(q*60)$$$ by storing each consecutive range with the same values, and iterating through this range vector for final computation.
For range [2^f, 2^f-1]. How are you recalculating g without iterating on all powers of f?
I guess you mean $$$[2^f, 2^{f+1}]$$$
In this range, there can almost be two such disjoint ranges, so I will binary search the point where the function changes.
Calculating the given function is $$$O(log n)$$$, just simulate finding max power for which $$$base^{y} \leq x$$$.
Btw I precompute these ranges, so each query is just $$$O(q * number-of-ranges)$$$
there can almost be two such disjoint ranges
Why?
Gwynbleidd_ answered that ig
He just stated the fact, but did not give explanation for this.
The given function is monotonic in the range because $$$floor(\log_2 x) = f$$$ now
I had this same logic, but i am getting WA on pretest 8.
Do we also need to be careful about bounds?
I'm not sure, I fixed most problems in my code with the sample cases.
f(x) ranges from 2 to 60 and for each f(x), g(x) is monotonic. Also for each f(x) if you check g(x) can have atmax 2 values. Precompute for all such ranges and answer it. tc: q*70 ig
Yeaa!
For each f(x), g(x) is monotonic. But how can we say that for each f(x), g(x) can have at max 2 values?
What i did was just printed the g(x) value for start and end point for each f(x), i.e. 2^i, 2^(i+1)-1 and it turned out the difference between them is atmax 1. and since it is monotonic u can find the point where it changes using binary search.
$$$x$$$ just almost doubles in this range
For the function to take more than 2 integral values, we need X to be multiplied by $$$floor(\log_2 x)$$$ which is more than 2
Hello sir . did u unnderstand why atmax only 2 values can be present. if so could u pls expalin sir
Consider the range $$$[2^x, 2^{x+1}-1]$$$.Let y = f(x) >= 2. For some k, $$$y^k$$$ is somewhere between $$$2^x$$$ and $$$2^{x+1}-1$$$. So, $$$y^k \ge 2^x$$$. Then $$$y^{k+1} = y(y^k) \ge y(2^x) \ge 2^{x+1}$$$
At first, I thought g(x) is monotonic on the whole range (not depend on f(x)), which give me wrong answer in the sample test case :((. Sad to be unable to solve D.
In my opinion, F is easier than C. I was stuck on C the whole contest, but figured out F 15 mins after seeing it.
Drop CM again :(
Was F using dynamic segment tree?
I used BIT, but I think segment tree works too.
I was thinking euler tour + seg tree. But how to take care of new nodes??
Start with the full tree and when a new node is added set it to 0
thanks
Build the tree and do euler tour first, then do the operations backwards, that way add nodes become delete nodes.
There is no need to worry about whether further queries will change the answer of the deleted node.
Did you use heavy-light decomposition like me?
nope.
I'm so confused. It seems that only I used it.
Another solution for $$$F$$$ without reversing queries!
When you add $$$x$$$ to all values in subtree of node $$$i$$$, just add $$$x$$$ to $$$val[i]$$$. The answer for every node $$$j$$$ is the sum of $$$val[k]$$$ such that $$$k$$$ is ancestor of $$$j$$$ (Call this sum as $$$S(j)$$$)
However, when you add node $$$t$$$ to the tree, then add node $$$t$$$ with $$$val[t]$$$ = $$$-S(t)$$$ in the current state of tree. This will "undo" the contribution of subtree sum addition due to queries performed before addition of node $$$t$$$.
But how can we calculate -S(t) fast before adding node?
Using a fenwick or segment tree. Adding $$$x$$$ to $$$val[i]$$$ means, add $$$x$$$ at $$$tree[tin[i]]$$$ and $$$-x$$$ at $$$tree[tout[i]]$$$. Note that $$$tin[i],tout[i]$$$ represent in-time and out-time of node $$$i$$$ respectively. Query sum of range $$$[1..tin[i]]$$$ to get $$$S(i)$$$.
Screencast with commentary
Thanks for the great round
2^Forces
I don't believe that task E can be simpler than F
Close your eyes then
(>_<)
Thanks for the round! I enjoyed the problems, but F is absurdly misplaced. I spent less time on it than on any problem after B, and if it had appeared in position D I would not have thought anything was out of the ordinary; indeed, F had nearly as many solves as problem D did. (I also think F is a bit on the standard end, but it's fine for a Div. 2 only round.)
FForces
This means you should look at the leaderboard to decide on which problem to work on.
What can so many people solve F! i couldn't get any valid ideas.
Euler Tour + Lazy Segment Tree in reversed order of query perhaps?
Lol2004 Oh, I got it!, how stupid i can, thanks bro!
it is a way easier)
wow system testing already ??
What is the 35th pretest?
For F I presume. It is that every query is adding a node and the graph will have q+1 nodes. This was perhaps missed and caused RTE.
I made this mistake but got AC. I hacked myself later. qwq
good contest
https://ac.nowcoder.com/acm/contest/27836/E?&headNav=acm It and F is simply the same.
Thank you for the beautiful round, loved it, although stuck on first problem till the end of time. Need some skills
D Problem, For 179 1000000000000000000 of sample testcase, I get 41949982 in my system and online IDEs, but I got 773751787 codeforces, What had gone wrong ? where should I look for ? my submission
I think overflow on signed integers is undefined behaviour, so that's why it's giving different results as your overflow check will not be correct. I don't know how to escape the overflow other than to tediously change everything to int_128 or do the code in python(risk of TLE).
Ohh thanks, I submitted in practice, It seems that was the issue, lesson learned :)
In F, the pretests were passed, but now I got MLE on test 16. The pretests were more than 16, so shouldn't it be tested in the pretests?
Like really bro? F is way too easy for being the last problem of this contest.
Why didn't you solve it then?
Isn't the range of unsigned long long till 2^128-1? In my local, it was overflowing on 2^70 only. Why?
unsigned long long only goes up to 2^64-1
Unsigned long long has a range of 0 to 2^64-1. There is int_128 which goes up to 2^128 but it is much more finnicky to use.
B can be cheesed, bad testcases i guess Link
230580209 can anyone try to help me finding bug in solution for D?
Take a look at Ticket 17121 from CF Stress for a counter example.
To help you debug, the testcase is constructed with $$$L = R = 2^{59}$$$. We have $$$f(2^{59}) = 59$$$, so we need to find the largest non-negative integer $$$z$$$ such that $$$59^z \leq 2^{59}$$$. It's easy to verify that $$$z = 10$$$ but your code produces $$$11$$$.
thanks, turns out I missed long overflow
230600697
Happens to the best of us :)
A round where everybody solved F.
B is kind of tricky, should some tricks.
UPD: solved it
How is it calculated? I used binary search but got different numbers.
We can check every [2^x, 2^(x+1)). If answers are (between Left and Right corner) different, we can easly find the border. If not, we now understand that all this numbers under one value
.
Just binary search and check for 9, 1e18 + 100. This will give you the relevant intervals from 9-1e18. For 1-8 you can find them out just by observing.
UPD: solved it
Thats exactly what I did but got wrong answers. Thank you anyway
I guess D is all about implementation
When do the ratings get updated? Thank you.
Why are today's editorials so late?
May I know why my 230532327 to B is skipped? 127.0.0.1
Only the last "passed pretest" submission would be run in system test.
it's because when you submit multiple correct solutions of a problem during contest, all the other accepted submissions (except the last one) of that particular porblem automatically get skipped.
My $$$O(Q*64)$$$ solution is doing TLE on test-case 10 https://mirror.codeforces.com/contest/1891/submission/230585018
my basic idea is between [2^q, 2^(q+1)], g(k) can only take atmost two possible values and I am combining them. Corner segments are handled separately.
Can I optimise it further or is it just too slow fundamentally, within the constraints I reckon it'd pass all the cases
230563485
Yes, if i have understand you correctly
At first you have ipow function, so it's $$$O(Q \log R * \text{(max ipow exp)})$$$. And you have too much $$$\% modm$$$, and time limit is too tough.
I think ur problem is correct but the result of ipow(lq,z+1) can overflow long long and became a negative number.
What is the deal with pretest 8 problem D? For 63 5153632, my code gives 20673255 whereas the answer is 20673256. I can't figure out how I'm missing the extra 1! Any ideas?
How to solve B?
after we add 2^x to a number it will never be divisible by any 2^y where y>=x. Using this fact we can remove all unnecessary elements from array q after which it's length will be at most 30 and we can bruteforce it
How like, if we take 4 and we add 2^1 to it multiple time, it may become 16, then it will divisible by 2^2
to add 2^1 the number must be divisible by 2^2. After you add 2^1 once it won't be divisible by 2^2 any more so you cannot add 2^1 again.
Thanks. I'm dumb!
Problems were really good!!
When will the editorial be? Or maybe I'm missing something? Thanks
why approach for F with euler tour + lazy prop is giving tle on tc 22. code- https://mirror.codeforces.com/contest/1891/submission/230589277
any help will be appreciated..
conragts to Gwynbleidd_ for finally reaching CM ( ME )
just wanted to see how this new color looks in comments
pretty cool ain't it?
magnificent!!
230598813
Hey, is it okay to check long long overflow using long double? I mean this :-
Does anyone have experience with this? Even if it is not precise, can you get away with it during contests?
I mean one scenario where this might come handy would be say you want to calculate
log(1e18, 60)using a for loop. You loop through1to10and it's all<= 1e18so you would want to check for11, but that is where it overflows. But the above trick works here ig.Oh so I found a better trick for that log case in https://mirror.codeforces.com/contest/1891/submission/230578519
Basically you decrease the power by 1 beforehand.
I don't think that ETO is an individual participant. The submissions from that account is suspicious.
Its code style in Problem A and Problem B matched. However, a new default source came up in Problem C and Problem D with different reading and multi-test handling method. The last two submissions are even more confusing.
Among these submissions, we can learn 4 ways to solve a multi-test problem, 3 ways to read a integer from stdin, 3 ways to set a constant value, which is shocking. It's easy to see that there are >1 members(possibly 4: AB+CD+E+F) so they should be unrated.
I believe I can beat the whole team if this contest is rated for me(they are too slow) but it's unfair to all Div.2 participants. plz unrated this account.
dx 1vs4
Why so many people solved F but only a few solved E?
Cause F is a problem that has appeared in Nowcoder Monthly Contest before.
Because it is not only too classical but also too easy.
Thanks，I reach master！！！I've waited a long time for this day
Thanks!I reach Candidate Master!
HI Bbicorz ET01orz user333orz
very nice contest! And I solve all problems!
Thanks a lot... I got my new best rating..
Congratulate