Good Day Codeforces!
Me, Wansur and Chalishkan are happy to invite you to take part in Codeforces Round 973 (Div. 2), which starts on 20.09.2024 17:35 (Московское время) You will be given 6 problems and 2 hours to solve them. One problem was divided into two subtasks.
The round will be rated for all participants with a rating lower than 2100.
The problems were authored by me, Wansur and Chalishkan to solve and alter them.
We would like to thank:
- FairyWinx for wonderful coordination.
- triple__a, sevlll777, bashkort, sstrong for red testing.
- Tima, dope, hopele555, Aldk, NaughtyMorzh, Issa, ahyeon, Nuris, Gamicrab for orange testing.
- NewLul, vsinitsynav, for purple tesing.
- xikvwl, Teeleu, Away_in_the_heavens, Quinx, Tangirkul, sabyr for blue testing.
- selenite, Shadibay for green testing.
- MikeMirzayanov for the great platforms.
- Vinton Cerf, and Robert Kahn for inventing the internet.
- You for participating!
Score Distribution: 500 — 750 — 1250 — 2000 — 2500 — (2000 + 2000)
UPD1: Congrats to the winners!
div. 2:
div. 1 + div. 2:
UPD2: The Editorial is out!
It is our team on EJOI 2024 4-th from left is me, 5-th from left is Wansur
We are also very glad that ICPC 2024 will be in Astana, and we wish all participants a good tour!
Auto comment: topic has been updated by soullless (previous revision, new revision, compare).
GLHF:)
the Score Distribution shows only 1 problem divided into subtasks
Thanks
When does the contest Editorial will publish?
GLHF
as a tester, can say that problems are interesting.GL for all participants
worst c for me rather then preparing for tommorows exam wasted more then 1 and half hours on c
For the first time, I solved three problems in div2. All that work was finally worth it!
im happy for u. bro
АЛҒА ҚАЗАҚСТАН!!!
As a tester…
finally, can say it
I hope all participate honestly without ChatGPT. Good luck to all!
orz
orz
orz
I think there should be someone specially for AI Testing and he/she should be mentioned in the blog :)
I hope AI is not able to solve any of the problems
FBI FBI your avatar is sus
Do u still love Diar Narumov? I remember u had a dp of a girl with few texts XD
Did she also breaked ur heart like Mike broked mine?
Do u still love Diar Narumov? I remember u having dp of a girl with some texts.. XD
Diar Narumov is a boy ._.
he is actually gay
We would like to thank:
.. wait to list more
Kazakh contest cannot disappoint
rip cyan testing
As a tester, this round is awesome, and I wish y'all good luck
Alga Kazakhstan
Hope that would be a lucky round for me.
soullless the best
As a tester, i wish you a merry cristmas!
hope to get good +ve in this round. Last round problem A destroyed my confidence :(
Nah I’d win. Ура мой первый казахский контест!
Wansur will win ioi
As a participant, soullless and Wansur orz.
Hope I'll not lose my rating again QwQ
As someone who not a tester, wishing everyone best of luck !
I hope the problems are thoroughly tested to be non standard. Thanks for making the round!
soullless orz. Hope to get + on this round
orz
something's wrong here...
Miscalculated, but where...
Чисто казахский контест будет)))
soullless orz
А я тоже хотел быть тестером ...
Удачи всем на раунде!
Ема легенда!
As a setter, I wish good luck to participants.
Nice hair bro. Gll to all the participants.
As an EJOI participant, I can confrim that Wansur and soullless are cool
hope pupil will accept me in this round
it is required to thank the creators of the internet now
everyone and their mother is creator of the internet these days
Оу да ,Кз Раунд 998batrr покажи как надо писать раунды
Return Specialist?
us ?
DONE !
KAZAKHSTAAAAAAAAAAAN
KAZAKHSTAAAAAAAAAAAN
KAZAKHSTAAAAAAAAAN
KAZAKHSTAAAAAAAAN
gl
АЛҒА ҚАЗАҚСТАН!!!
How to become pupil in a month?
How to become pupil in a month?
Don't ask silly questions which have already been answered several times.. That's how
No proper thanks to Alan Turing for inventing computers :[
is it rated?
Wow, it`s 奶龙大头.
Wow, this is the big head of the milk dragon.
Good luck everyone!
expecting a good problemset
I wish D is not GPT solvable
Technoblade never dies
Technoblade never dies
i hope i will be lucky.
I actually believe that we are not completely powerless in addressing the issues with AI. For example, the following approach could probably work (though, of course, it requires cooperation from OpenAI and cannot completely prevent cheating with AI, but at least it offers an approximate direction): Before a particular contest, CodeForces provides the statements (possibly with editorials) of contest problems to OpenAI. As a result during the contest period, ChatGPT could forcibly reject any requests related to the problems if detected. Through this way, normal AI usage wouldn't be affected, while cheating with AI during the contest could be prevented to some extent. Of course, determining whether a user’s request is related to the problems (to clearly identify where the boundary is, without ambiguous judgement) would still be a challenging issue that needs further exploration, but given the current advancements in AI technology, it is obviously achievable through proper training.
What is the need to provide problems WITH EDITORIAL ?? Why not just problems??
If handled properly, only ChatGPT would be able to access the editorial, which means it would just terminate the conversation as long as it encounters something related to algorithms or logics appeared in the editorial. But as what I've said before, the specific boundary between related or not should be carefully restricted.
No more than 2n operations, but its WA if Im doing exactly 2n operations.
Please, can you give me link of submission?
i also believe my first submission(which got WA) made 2n queries at most, but i could be wrong
Link
link
actually nvm, it seems i got an actual WA, not too many queries, sorry
I wrote a code, which I thought would find the answer in 2n queries, but it was actually giving in 2n+1 queries, I guess you could be doing the same mistake...
why not reminding that there are some interactive problems? I guess you forgot it
question 3 is extremely confusing. I dont even get how to take the inputs.
I hate interactive problem
I hate interactive problem.
One of my worst contests, carrot predicts -52 rating loss.
C was pretty annoying, I probably could have solved D if I spent all my time on it, but I ended up splitting my time after A and B on D and C which was a mistake.
:(
I'm having the same mistake, I guess it's -6x for me and soon going back to newbie in a few contests...
D solution, please
First, you should have a function $$$f(x, y)$$$ which determines if its possible to have an array $$$a$$$ such that $$$\min(a_1, a_2, \dots, a_n) = x$$$, and $$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n) = y$$$.
If you look at $$$f(x, y)$$$ for all values of $$$x, y$$$ from one of the sample, you will have this pattern:
Now, you can binary search on the maximum value of $$$\min(a_1, a_2, \dots, a_n)$$$ by querying $$$f(i, 10^{12})$$$.
Lastly, you binary search on the minimum value of $$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)$$$ by querying $$$f(\text{min val}, i)$$$.
The double binary search is so ingenious but just too hard to observe, may I ask if there are some similar problems as advice?
I think n time is possible for finding min and max
For minimum, iterate from start to end while taking sum Min = min(Min,average till that point)
Same for max only starting from the end to start
Max = max(Max,average till given point)
And then answer is max-min
I will attempt my solution once system testing in done
https://mirror.codeforces.com/contest/2013/submission/282108743
Insane, how does this logic even work and how did you come up with it ? Would you explain please ?
The idea is pretty simple, you have to minimize the value of ~~~~~ max(a1,a2,…,an)−min(a1,a2,…,an) ~~~~~ The obvious way to do this is, you select the maximum value to be as small as possible and the minimum value to be as large as possible. This will reduce the gap between max and min value and that would be the required solution. Now comes the part where you minimize the value of max, you can do a binary search on answer. Assume you hold a max value, now iterate over the array a, and check if you can achieve this max value in the array. The checking process goes as: if a[i] < (our assumption of max) then just continue as it is already smaller. But if a[i] > (our assumption) then you can simply reduce (a[i] — our assumption) from that and add this value to a[i + 1], and at last if you check a[n] and find it to be less than or equal to our assumption then return true, or else go for a larger assumption. Similar for the case of finding minimium.
You can check my solution 282139332
How can you guarantee that the case the maximum value to be as small as possible and the case minimum value to be as large as possible happen simultaneously?
The max and min value will always be an element of the array a. I guess you have no confusion regarding this line. Now for an array (a), the max value will always be greater than or equal to the min value. And by any method if we can find the max value then you can obviously find the min value without affecting the max value. Because max and min values are independent of each other.
I don't understand how we can guarantee that the min value do not affect the max value that we can minimize. Like, exist a proof on that? A proof that guarantee that if we modify the array values for reach a maximum minimum, do not affect the minimum maximum.
I don't think it is necessarily true, that max and min will always be the elements of the array, Consider an array [12, 8], Here max and min will come out to be 10, neither one of them is in the array.
Your solution is very interesting. But like others pointed out, I also find it a little unintuitive that the operations you perform to attain the maximum element never worsen the minimum element you can achieve. Does anyone have a proof for this? Alternatively, consider the other solution which has two parameters that control both the max and min and prove the monotonicity of this (as dartvolley did above).
Hey, I think I might have found a small mistake in your comment. $$$f(x,y)$$$ follows the pattern you described if you define $$$x$$$ as $$$\min(a)$$$ and $$$y$$$ as $$$\max(a)$$$, not $$$\max(a)-\min(a)$$$.
For those interested, here's a proof for the monotonicity of $$$f(x,y)$$$.
Going by the above definition, $$$f(x,y)$$$ is $$$1$$$ when it is possible to transform $$$a$$$ to satisfy $$$x \le a_i \le y$$$ $$$\forall 1 \le i \le n$$$.
I make the following two claims:
If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x+1,y)$$$ is also $$$0$$$. If any $$$a_i$$$ was $$$ \gt y$$$, then both outputs would be $$$0$$$. So assume that $$$a_i \le y$$$, then $$$\min(a) \lt x$$$ directly implies that $$$\min(a) \lt x + 1$$$.
If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x,y-1)$$$ is also $$$0$$$. The proof for this is symmetric.
for people who got ac after wrong answers: what's a corner case test case for F1?
I am not sure what others did,
I did something like BFS from both nodes simultaneously (with node 1 being first) Then if the longest chain that bob can reach is of length greater than or equal to that of alice, I print 'Alice', else 'Bob'. But this fails this test case
In this test case, Bob would win, but my code outputs Alice.
Alice moves to 4, Bob is forced to 7, Alice moves to 6, Bob is stuck -> Alice can win
Sorry, I made a typo, can you check the testcase now.. (changed the edge 7-8 to 6-8)
In this test case, Bob would win, but my code outputs Alice.
Indeed, in this case Bob wins
funny problem C. I really feel dumb actually
Did only one question, feeling demotivated, again.
I could only come up with a solution to solve C with 2n + 1 queries ugh. Couldn't come up with a way to get it to 2n in contest time. https://mirror.codeforces.com/contest/2013/submission/282098849
I have another approach that would still generate 2n + 1 queries in worst case scenario. If you construct the correct suffix by taking up to 2 queries, then you figure out it is the end by 2 queries failing so it takes 2 * length_of_suffix + 2, then can solve for prefix in length_of_prefix queries, and it is required that 2 * length_of_suffix + 2 + length_of_prefix <= 2 * N. But if N = 5, and length_of_suffix = 4, and length_of_prefix = 1, then 4 * 2 + 2 + 1 = 11. Unless this is wrong somehow.
it cannot happen i guess. for something like that to happen we may suppose that we're querying 1 first and 0 later. so in order to get 8 queries to get the suffix and then 2 to check if the suffix is done or not the suffix has to be nothing but $$$ 0000 $$$. and then the first character has to be 1 to get to 11 queries according to you. but since we're asking 1 first, we will start from $$$ i = 0 $$$ and not $$$ i = 1 $$$
One query is sufficient for the first character because if "1" is not a substring, you don't need to check "0" — the string must be only "0"'s.
Wow thanks I didn't see that, yeah that get's accepted with 2*n queries at most cause now it is 1 + 2 * (suffix_length — 1) + 2 + prefix_length = 3 + 2 * suffix_length — 2 + prefix_length = 2 * suffix_length + prefix_length + 1 <= 2 * N, even in the scenario that prefix_length = 1. If prefix_length = 0, then suffix_length = N and 2 * (N — 1) + 1 = 2 * N — 1 <= 2 * N https://mirror.codeforces.com/contest/2013/submission/282136094 I just had to add this line of code to get accepted for adding first character. if (ask(s + '0')) { s += '0'; } else { s += '1'; }
Was D really that easy?
no, a lot of cheaters that's it
it was an average D imo
Buffed versions of problem C: here and here.
Thanks for posting
I would love to learn the intuition behind problem C. I tried to build a solution based on previous guess information but it became confusing to combine all this information into an educated guesses.
first check if there is a '0' in the string. if there isnt, then its obviously just n 1s. so lets assume there is a 0. then we can just start guessing what is to the left of the zero and what is to the right of the zero. check out my submission for details, i think its pretty straightforward
Good contest, expecting to reach Pupil.
You've done 5 contests. In the first four you managed to solve only problem A. In this contest you managed to "solve" four questions and rank in the top 1000...
You guys only observed that I solved just one problem in my last four contests, but you didn't notice that the time difference between this contest and the previous one is approximately a year. During that period, I solved around 1,000 problems.
You guys didn't mentioned for interactive why :(
Its my fault also I should have solved B from my first thought only I fcked it up due to overthinking
Was E intended to be greedy (pick the smallest number first, then repeatedly pick the next number which will minimise prefix GCD until prefix GCD = array GCD)? Or is that solution hackable?
Than correct :(
I also solved it that way.
I wrote a DP solution in order to avoid greedy solutions which can not be proved. Here is my submission.
Hi, I have tried reading your submission, but I am not able to fully understand what is happening here. Can you please explain the approach for this solution?
I also did that without proving XD
This is correct.
For example, let the optimal solution be b1, b2, ..., bi, ..., bn where bi is the minimum. Then consider bi, b1, b2, ..., b_(i-1), b_(i+1), ..., bn. Note that gcd after b_(i+1) is the same so we can ignore the sum of that part. Then if b1 > bi, then we have gcd(bi, b1) <= b1 — bi since gcd(bi, b1)=gcd(bi, b1-bi). Hence in our modified solution, the gcd sequence look like bi, <= b1 — bi, <= gcd(b1, b2), <= gcd(b1, b2, b3), ... and the original look like b1, gcd(b1, b2), gcd(b1, b2, b3) It is clear that sum of our modified sequence is better so taking minimum as first is optimal.
For the recursive part we simply reduce the problem by taking gcd(bi, -) with the rest of the numbers. It is clear that this correspond to the subproblem of the sum of the rest of the gcd sequence and the sum is the same.
how to solve D or why my code D Runtime Error ? Thank 282102762
Runtime error may be caused by division by zero，if nn is 2
Could solve only 1 in my 1st contest. But still, eagerly waiting for the editorial.
Problem C is nice, I faced the same problem at OII 2022 but 2*n queries were enough to get only 40 points. (https://training.olinfo.it/#/task/oii_dna/statement)
Is there something wrong with my logic for problem D:
Lets use ternary search for lower bound t1 to find minimum (t2-t1) where t2 is optimal upper bound for given t1. It's not hard to show that declared function is convex.
For each t1 lets use binary search to find minimal t2 so that you can readjust array between t2 and t1
For each (t1,t2) we can check if we can fit array into [t1, t2] going right to left one time.
Complexity should be O(log(Max)^2*ArraySize) which should be ok for given values. But for some reason I got Time Limit Exception. Is there flaw in the logic, or I just make a mess with terrible constant? Submission
i just used a simple stack algo for D lmao
In fact, it can be proved that ternary search for lower_bound is unnecessary. Only binary search or O(n) algorithm is OK for finding lower_bound. I can prove that as the lower_bound increases, the optimal upper_bound does not increase. So let sum[i] be the partial sum of a[i], then the lower_bound SHOULD be min(sum[i] / i). After that, we can binary search for upper_bound and it works.
Same approach. I don't know why this fails, Let me know if you encounter a test case where your solution failed.
what's edge case in pretest 2 for F1
finally for the first time i am into 5000 ranks....... long way to go
same
is some special knowledge required for problem d?
How to solve B?
(sum of the first n-2 elements) + (the n-th element) — (the n-1st element)
Why last second element os goven so much importance?
well you know that the second to last element has to fight the last element. and you also know that the last element will be the last one standing. so your goal is to reduce the 2nd to last element as much as possible before they fight. you do that by making him fight all the ones before him
Upvoted!
Thank you for the explanation.Understood!
Saw my first ever interactive problem, panicked, but eventually did it when around 3 minutes were left. Feels good.
accumulate(a.begin(), a.end(), 0L) - 2 * a[n - 2]why this not working for BIt should be 0LL for long long
thanks bro, crazy how using java at work changed my reflexes from 0LL to 0L
For D, I tried to find the minimum and find the maximum using binary search on difference. Looking at others' solutions, many have computed min and used same idea to compute max by going in reverse. However, I got WA upon doing this. This is the relevant of calculating the min in the array. What am I missing:
I suppose the mistake I made was not using up
excesswhena[i] + excessis not enough to get tomn. I'll just try to resubmit once the task is available for practice.I got D in the last 5 minutes :D, specialist woohoo!
It's interesting that most of the people seem to have used binary search for D. I actually solved it by realizing that the optimal array in the end can be made non-decreasing and this way the min_val in the end is just the minimum over all floor(sum[0..i]/i) and max_val is the maximum over all ceil(sum[n-i..n]/i). https://mirror.codeforces.com/contest/2013/submission/282089570.
Not sure if this was intended or I will get a WA in system tests
Same but I can't prove if both the minima and maxima can occur simultaneously. Hoping not to get FST.
Yeah, I think my idea was similar to try to make array non-decreasing. I think
floor(sum[0..I]/i)is certainly elegant and I saw this in other solutions too. I tried to do this more mechanically as I could not convince myself that the simple version will work.I had a similar idea for the minimum, but I could not work out quite what it would equate to for the maximum. I ended up finding the minimum in a similar way to that, and then binary searching for the maximum after that. Good find on your solution.
Seems correct to me. I used same logic for max, and binary searched min. Feeling my binary search is essentially the same to your min calculation.
we can calculate the min and max separately. but can we prove that both such max and min can occur at once?
the min will in some prefix and max will be a disjoint suffix (since you can always move values backwards), so shouldn't be any conflicts between the min and max
What exactly does it mean that you can always move values backwards?
I understand why it is guaranteed min_val <= min(floor(sum[0..i]/i)), but why must they be equal at optimal(max-min)? What if this value of min_val makes us have some bad max_val?
skip PC and doing PD then failed :(
How to prove the greedy solution of E?
Let $$$A$$$ be the smallest possible gcd with the current prefix gcd, and let $$$B$$$ be the optimal one, with $$$A \lt B$$$. Then, if we take $$$A$$$, then $$$B$$$ and continue in the same way as in the optimal case, the result will not be worse, since $$$A + gcd(A, B) \le B$$$.
Just in case it's not obvious where $$$A + \gcd(A,B) \leqslant B$$$ comes from, note that $$$\gcd(A,B) \mid A$$$ and $$$\gcd(A,B) \mid B$$$ which means $$$\gcd(A,B) \mid (B-A)$$$ since we have $$$A \lt B$$$ and a divisor of a positive integer must necessarily be $$$\leqslant$$$ than that integer, so we have $$$\gcd(A,B) \leqslant B-A \implies A + \gcd(A,B) \leqslant B$$$.
Brilliant proof btw!
im really confused can u please help me with this, wtf is A and B, and why do the gcd(A,B) it seems totally unrelated, is do A and B share the same sequence (for gcd) or are they fundamentally different?
Just a request:
Please mention beforehand whether there is an interactive problem. Newbies like me will benefit a lot.
I would have opted out of the contest because I did inevitably lose time in my futile effort on the interaction rather than the algo crux. I would have not registered had I known beforehand of the presence of interactive problem(s).
Is there an issue with AtCoder's Library's lazy segment tree? Or did I improperly use it. I would appreciate any advice anyone can give. Because I tried using ACL's lazy segtree in problem D and got WA. The exact same code but with AI.Cash's lazy segment tree (from here) passed the pretests.
I was able to stress test and find out a test case that the code with ACL's lazy segtree failed on.
1
4
5 1 3 2
Expected Output (in my opinion): 1
Submission that passed pretests: 282094170
My WA submission: 282066742
Cleaned code (without debugging lines and comments):
Pretests passed code
WA code
Can anyone explain the logic of problem C?
Sure, ill explain my approach (this is rushed so no fancy LaTeX sadly)
essentially, this problem, if youve ever seen ioi 2018 d1 p1 (combo), is a lot like that, even in its statement it bears heavy resemblence. But in addition to that, this one is a binary string
Now if we think of a naive greedy approach, we can notice that
We can go through each index greedily adding through a string if 1, once were at the end, we then turn backwards and repeatedly append to beginning, this is fine because n^2 complexity is allowed making 100*100*100 = 1e6
How do we figure out when its the end?
If both s+'0' and s+'1' return 0, then we are at end, we can mark with a boolean to go backwards from here on forth.
Ok this is fine, but the worse case here would be 2n+2 operations due to the two operations to do what I said above. Similar to the IOI problem, we can look at the beginning and figure out a way to save two operations for later. And this is when you realise if n>=2
n can be 01, 00, 10, and 11, if n is not 01 and 10, that means it must all be 0 or 1 which can be solved on its own
if it is 01 or 10, we have now saved two operations taking 2 operations for generating s of length 2 instead of 4 otherwise. With this now we can use the 2 at the end and send the greedy to always have 2n operations at worst.
Finally, we check for 1 which is simply one check, if its 1 for "1" then we return 1 else 0.
Very fun problem, if you haven't done IOI 2018 d1 p1 (combo) please do try it with this idea as that is also a fun problem.
greedy can be optimized easily to get $$$ \lt = 2n $$$ queries. You realize that once we reach the end of the string, elements on left have to be either 1 or 0. So we don't we need to ask two times. We can only ask if its $$$ 1 + suffix $$$ or not. if it is then the suffix increases by 1 on left otherwise increases by 0 automatically
Good problems, binary search idea in D was pretty good, tried something similar for the first time
is E basically this? https://mirror.codeforces.com/problemset/problem/1614/D2
bruh exact same
funny part is, I have solved above qs already, but messed up in today contest
No, but I also thought the same during the contest. For E you need minimum, not maximum
good problemset
is it just me who felt this contest was significantly easier than the last one? i only solved A in the last contest but i was able to solve AB and got the logic for C very quickly (couldn't solve C because i had never solved interactive problems before, so i struggled with converting the logic to code)
same for me, A-B2 vs A-E
What a greedy round.
C my first interactive problem and damn how I hate interactive problems now. Anyway anyone got solution of D. My code was like this:
It is pretty straight forward as can be seen but obviously it is wrong and more obviously it did not work. So anybody can tell me what could be the correct approach and how to avoid this infinite loop problem will be much appreciated. peace
just an advice so you don't get downvoted. put the code in spoiler tag. people don't like long comments and they may downvote you
In Problem A, In the input statement, the meaning of x and y was switched, which caused me one wrong answer. Please review.
could anyone provide edge cases for F1? i am pretty confident my soluton is right, but i am still getting WA even after debugging. link
nvm, found the edge case
Hey, what's the edge case?
Am I the only person who used prefix sums for D?
How did you solve it using prefix?
Minimum element = min(P[i]/i) where P[x] is sum of first x elements.
Maximum element = max(ceil(R[i]/i)) where R[x] is sum of last x elements.
Can you please explain why this works and the intuition behind it? I thought of doing something something similar after realizing that the overall sum of the array doesn't change after operations but couldn't get the actual solution.
It is because we if you think you can actually shift a +1 from the left to right and -1 from right to left,
lets just say we have
[3,1,1,10,10,10]
so like this at any given index we can find the minimum like this by traversing the array from left to right and taking always the minimum og the average till there.
and same we can iterate a from right to left to find maximum
great intuition, but how were you sure this would work like when i was trying to figure that out I couldnt really get why this works
I was not able to come up with this in the contest I got it after reading this comment
so how would this work for [1,3]? if i understood correctly, this approach would say that the minimum is 2, while it is actually 1, since the 3 cant be reduced. sorry if i misunderstood the explanation
ya that what i said at any current index you are calculating the minimum by just looking at the average till that index
for [1,3]
note we cannot back propagate a +1 so at any current index we can either make the average decrease by 1 or make it same and we have to decrease maximum and increase minimum for our optimal answer we will just calculate the minimum till that index.
similarly you can calculate the maximum by either traversing from last or reversing the array,
i understood right after writing the comment xD, thank you for the explanation anyways. this seems very intuitive, i shouldve probably focused on this problem instead of F1 :(
Just try to equalize all elements in array.
For any two elements i,j where i < j and a_i > a_j. Simply imagine pushing one from a_i to a_j (Do one operation of all k where i <= k < j). Repeat until array is sorted. The Psum method is the efficient way to calculate min/max.
The proof that psum works is through induction.
Obviously, we can equalize any singular. element of the array, by doing no operations, and we can near-equalize(max-min = 1) a subarray of elements that are a a a b b b where a>b, by simply decreasing each a and increase each b.
Now lets assume we have equalized the first k elements where p[k]/k = a, and the exists a l where p[l]/l = b and b<a. We can equalize the next l-k elements, through the inductive structure we are building. So, this results in the subarray aaabbb, which we have proven we can equalize.
The proof for the max remains an exercise to the reader, but is VERY similar to the min.
Hey, Can you please once look at this code of E and try to find why it's failing for a hidden case -> 282135524
Logic -> I will get the minimum gcd possible in every iteration
For maximising the minima, I tried to greedily increase each element without lowering the current maximum minima till the ith index by trying to make it equal to the average till now (only possible if avg was higher than element at i) doing so may result in increasing the minima but never lower it. We dont make it more than the avg since it risks decreasing the global minima till now without ever increasing the global minima. We also dont leave it lower than the average since we always can make it equal to the average guaranteed to not reduce the global minima. If the avg was however smaller than element, then then we would leave it as is and take care of it in future iterations as the elements which gets decreased when an element is increased to its avg. I did it separately for the maxima and subtracted the and to my surprise it was AC lol.
I did the same thing
omg what a great solution, i was so close to this did the exact same for the minimum but was not able to come up that we can do the same for maximum.
Did exactly this and got AC
https://mirror.codeforces.com/contest/2013/submission/282078787
I used prefix sum too. The first thing that came to mind was binary search on looking at the constraints.
fair
I get burned by i32's every time :(
why this code is not giving TLE
A B C Tutorial in Bangla
How did you solve E?
I don't know why "the sum of $$$\max(a_1, a_2, \ldots, a_n)$$$ over all test cases does not exceed $$$10^5$$$" at all.
My solution is very sample. This is my code: https://mirror.codeforces.com/contest/2013/submission/282110416
E can also be solved using dp. Let A = max(a[1],...,a[n]). dp[i][j] denotes minimum gcd(a[1])+...+gcd(a[1],...,a[i]), gcd(a[1],...,a[i]) = j. We should only consider i <= log2(A), since it is optimal if gcd decreases at the beginning and it can decrease at most log2(A) times. j <= A. Transitions are as follows : dp[i][j] = dp[i-1][j*k]+j if there exists some a[l], such that gcd(a[l],j*k) = j, k is some constant 1 <= k <= floor(A/j).
"if there exists some a[l], such that gcd(a[l],j*k) = j." How do you check this quick enough?
gcd(a[l],j*k) = j => gcd(a[l]/j,k) = 1. Let's maintain cnt[i][j] meaning number of numbers x, such that x is divisible by i and x/i is divisible by j. Now, a[l] such that gcd(a[l],j*k) = j exists IFF M(d1)*cnt[i][d1]+M(d2)*cnt[i][d2] +...+M(dm)*cnt[i][dm] > 0. M denotes Möbius function. d1,d2...,dm are all divisors of k. We can calculate cnt in O(nlog^2(n)).
In problem F1, can someone explain why the answer for this test case is Bob:
My logic is that Alice can go 2 -> 1, then Bob can only move to 8, then Alice moves 1 -> 7, and Bob can't make a move so Alice wins.
Alice starts from 1 and Bob starts from 2.
Alice goes from 1 to (one of 3, 4, 5, 6, 7), can't go to 2 because Bob is there.
Bob goes to 8 from 2.
Alice is one of 3, 4, 5, 6, 7. In any case can't go anywhere
Bob Wins
Oh thank you, I misread the problem and thought that both Alice and Bob start from the same node $$$u = v$$$.
Could someone help me proving the TC of this solution in Problem D?
Every iteration I convert all the decreasing subarrays to their almost-equal values with the same sum.
I keep doing this until no operation changes the current array. I can't think of proper upper bound for this solution.
Great contest :)
Can Someone Please Help me with solution of problem C, which causes TLE 282128399 Thankyou
Actually it should gives you WA, but because you don't assert whether you were given $$$-1$$$ or not, so your solution run limitless without terminating.
Here is your submission with assertion to avoid TLE
Hey friends! Does anyone know why I am getting TLE on test 1? 282130372 I know my approach is incorrect, but I'm just trying to figure out the TLE. If you cast ans.length() into a long long it works, but I'm not sure why it doesn't otherwise.
As I mentioned in the comment above. TLE is in fact a WA verdict. Because you are given $$$-1$$$ as a response and the program should terminate after. So, treat TLE here as WA or you could just assert that $$$n$$$ is not $$$-1$$$ before proceeding into your logic
Ah I see, so n could be -1 as well, that makes a lot of sense. Thanks for your help!
If you make an incorrect attempt or exceed the limit of 2n attempts, you will receive −1 instead of an answer and get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts
Honestly, It's my first time facing such issue in interactive problems. But it's good to learn :)
First time solved an interactive problem in a contest..feeling good
Rating Prediction
A — 800
B — 900
C — 1500
D — 1800
E — 2100
F1 — 2600
F2 — 3100
Never thought I would be in the leaderboard of a contest ever! Thanks a lot
6k people solve C? That's imposible. People are cheating in current contests.
Looks still no editorial yet. This is my unofficial editorial.
~~~~~ ~~~~~
The answer is $$$\frac{n + \min(x, y) - 1}{\min(x, y)}$$$.
Looks still no editorial yet. This is my unofficial editorial. The answer is $$$a[n] - (a[n-1] - a[n-2] - \dots - a[1])$$$.
We can see $$$a[n-1]$$$ cannot be positive, because it will not lose until meeting $$$a[n]$$$.
Extend the string to the left and right.
If you start from “? 0” or “? 1” it may cost $$$ \gt 2n$$$ operations. To avoid this, start with “? 00” or “? 01” and check the case of $$$n=1$$$ and $$$s=$$$ “1 $$$\ldots$$$ 1”.
The minimum is always $$$a[1]$$$. If $$$a[1] \gt a[i]$$$, we can always swap $$$a[1]$$$ and $$$a[i]$$$.
If $$$a[i] \gt a[i+1]$$$, we can swap $$$a[i]$$$ and $$$a[i+1]$$$.
So the final array $$$a$$$ is non-decreasing.
Consider a greedy process: try to move numbers as little and as right as possible, such as $$$1\ 3\ 4\ 1 \rightarrow 1\ 3\ 3\ 2 \rightarrow 1\ 2\ 3\ 3$$$.
How to implement it?
Consider $$$a[i] \gt a[i+1]$$$:
Binary search for $$$j$$$;
Let $$$X$$$ be the final value of $$$a[j]$$$;
$$$a[i+1] + \sum_{j}^{i} a[j] - (i - j + 1) X \geq X$$$;
$$$X \leq \frac{a[i+1] + \sum_{j}^{i} a[j]}{i - j + 2}$$$;
$$$X \geq a[j-1]$$$;
Still, we need to do $$$a[i+1] -= D$$$, $$$a[i-D+1,\ldots,i]++$$$ (where $$$D = a[i+1] - X - 1$$$).
This can be solved by a segment tree.
It can be proven that $$$a[1]$$$ is the minimum of the array.
Then, we can set $$$a[i] = \gcd(a[1], a[i])$$$ for all $$$2 \leq i \leq n$$$. There are $$$m$$$ (the total number of divisors of $$$a[i]$$$) different numbers in the array.
After that, we can run an $$$O(m^2)$$$ greedy algorithm:
Use brute force to find the number that causes the fastest decrease in the GCD. If there are no such numbers, we would have obtained all the answers.
How to prove $$$a[1]$$$ is the minimum of the array?
Consider $$$a[i] \lt a[1]$$$. We compare these two arrays:
$$$a[1], a[2], \dots, a[i], \dots$$$
The answer is $$$a[1] + \gcd(a[1], a[2]) + \gcd(a[1], a[2], a[3]) + \dots$$$
$$$a[i], a[1], a[2], \dots, a[i-1], \dots$$$
The answer is $$$a[i] + \gcd(a[i], a[1]) + \gcd(a[i], a[1], a[2]) + \dots$$$
We have $$$a[i] + \gcd(a[i], a[1]) = a[i] + \gcd(a[1] - a[i], a[1]) \leq a[i] + a[1] - a[i] = a[1]$$$, and $$$\gcd(a[i], a[1], a[2]) \leq \gcd(a[1], a[2]), \gcd(a[i], a[1], a[2], a[3]) \leq \gcd(a[1], a[2], a[3]), \dots$$$
So $$$a[i], a[1], a[2], \dots, a[i-1], \dots$$$ is better.
Why is it optimal to find the number that causes the fastest decrease in GCD?
Similarly to above, after choosing $$$a[1]$$$, we want to choose the "smallest" number (but $$$a[i] = \gcd(a[i], a[1])$$$ has been done) of the remaining elements to be $$$a[2]$$$.
This is the number that causes the fastest decrease in GCD. Then, we choose $$$a[3], a[4], \dots$$$ using the same logic.
Looks still no editorial yet. This is my unofficial editorial.
The answer is $$$\frac{n+\min(x,y)-1}{\min(x,y)}$$$.
The answer is
we can see $$$a[n-1]$$$ can not be positive, because it will not lose until meeting $$$a[n]$$$.
Extend the string to the left and right.
If you start from “? 0” or "? 1" it may costs $$$ \gt 2n$$$ operations, to avoid it start with "? 00" or "? 01", and check the case of $$$n=1$$$ and $$$s=$$$"1...1".
The min is always $$$a[1]$$$, if $$$a[1] \gt a[i]$$$, we can always swap $$$a[1]$$$ and $$$a[i]$$$;
If $$$a[i] \gt a[i+1]$$$, we can swap $$$a[i]$$$ and $$$a[i+1]$$$.
So the final array $$$a$$$ is non-decreasing.
Consider a greedy greedy process-try to move numbers as little and right as possible, such as $$$1\ 3\ 4\ 1 \rightarrow\ 1\ 3\ 3\ 2 \rightarrow\ 1\ 2\ 3\ 3$$$.
How to implementation?
Consider $$$a[i] \gt a[i+1]$$$:
Binary search for $$$j$$$;
$$$X$$$ is the fial value of $$$a[j]$$$;
$$$a[i+1]+sum[j,i]-(i-j+1)X \gt =X$$$;
$$$X \lt =\frac{a[i+1]+Sum[j,i]}{i-j+2}$$$;
$$$X \gt =a[j-1]$$$;
Still need to do $$$a[i+1]-=D$$$, $$$a[i-D+1,...,i]++(D=a[i+1]-X-1)$$$.
This can be solved by segment tree.
It can be proven that $$$a[1]$$$ is the minimum of the array. Then, we can set $$$a[i] = \gcd(a[1], a[i])$$$ for all $$$2 \leq i \leq n$$$. There are $$$m$$$ (the total number of divisors of $$$a[i]$$$) different numbers in the array.
After that, we can run an $$$O(m^2)$$$ greedy algorithm:
Use brute force to find the number that causes the fastest decrease in the GCD. If there are no such numbers, we would have obtained all the answers.
How to prove $$$a[1]$$$ is the minimum of the array?
Consider $$$a[i] \lt a[1]$$$. We compare these two arrays:
$$$a[1], a[2], \dots, a[i], \dots$$$
The answer is $$$a[1] + \gcd(a[1], a[2]) + \gcd(a[1], a[2], a[3]) + \dots$$$
$$$a[i], a[1], a[2], \dots, a[i-1], \dots$$$
The answer is $$$a[i] + \gcd(a[i], a[1]) + \gcd(a[i], a[1], a[2]) + \dots$$$
We have $$$a[i] + \gcd(a[i], a[1]) = a[i] + \gcd(a[1] - a[i], a[1]) \leq a[i] + a[1] - a[i] = a[1]$$$, and $$$\gcd(a[i], a[1], a[2]) \leq \gcd(a[1], a[2]), \gcd(a[i], a[1], a[2], a[3]) \leq \gcd(a[1], a[2], a[3]), \dots$$$
So $$$a[i], a[1], a[2], \dots, a[i-1], \dots$$$ is better.
Why is it optimal to find the number that causes the fastest decrease in GCD?
Similarly to above, after choosing $$$a[1]$$$, we want to choose the "smallest" number (but $$$a[i] = \gcd(a[i], a[1])$$$ has been done) of the remaining elements to be $$$a[2]$$$.
This is the number that causes the fastest decrease in GCD. Then, we choose $$$a[3], a[4], \dots$$$ using the same logic.
My submission: 282147053
Can someone please explain why the following approach works for C-Password Cracking?
Start with an empty string
query = "".Finding the longest suffix:
1s. Guess
query + '0'. Yes -> {goto 1s} No -> {goto 2s}2s. Guess
query + '1'. Yes -> {goto 1s} No -> {longest suffix found; goto 1p}Finding remaining prefix
1p. Guess
'0' + query. Yes -> {goto 1p} No -> {goto 2p}2p. Guess
'1' + query. Yes -> {goto 1p} No -> {queryis the password}Up to this point, I know that this approach may take $$$2n + 4$$$ queries at max ($$$2*n$$$ for each character, 2 when the longest suffix is found and we query by appending '0'/'1', and 2 for the prefix similarly.
Improved approach: I maintained two vectors of strings
yesandno. Each time I get 1 as a response, I putqueryinsideyes, else intono. Before querying, I put the following checks:query.size() <= nevery substring in
yesmust be a substringno substring in
noshould be a substringIn this case, I can see that the extra 2 queries for prefix will be cut off leaving $$$2*n + 2$$$ at max. However, this approach has passed all test cases, so queries are reduced to $$$2*n$$$ at max. How?
When you change from suffix to prefix, you can actually be sure the next character that is added to the start of the string is not the same as the first character as you current string. For example:
0:100:1000:0001:10010:00011:0Here, because
000is not a substring, the longest contiguous substring with all0is only of length $$$2$$$, so guessing0001is not needed at it has three consecutive0. When you check if thenosubstrings are actually not in your queries, you saved the wasted query of0001in the above example, which means this lowered the queries by $$$1$$$, as now you only need $$$1$$$ query for the first time checking prefix).Also, in the query of size $$$1$$$ strings, you either get
1when you query0(which means the first character only take $$$1$$$ query, cutting another query from the total), or you get0for0and1for1(which means the string is all1and ended with $$$n+1$$$ queries)Just now I solved D by guessing, but I couldn't prove my solution. Can someone tell me why the following approach works?
Find the highest possible min using the operations, find the lowest possible max using the operations, then the answer is just
lowest_max - highest_min.Intuitively, it makes sense to me the fact that when using the operations to maximize
highest_minyou don't violate the operations used to minimizelowest_max, but I can't definitively prove it. Link to my submission.what did this row k = max(0, k — diff)?
Well that is just implementation detail. Basically the operation can be rewritten to "choose
iandjand move any amount fromarr[i]toarr[j]" andkis amount of operations we've done to get allarr[i]so far to becomemx(ormnin the case ofcheckmn), but haven't picked the indexjto move it to. So every time we meet an element that already satisfy mx or mn we treat it asarr[j]and want to deduct as much fromkas we can.Check this and this out. Using these, you can see that choosing the maximum does not change which minimums are possible to obtain and vice-versa.
It was a really good and varied contest. But we are waitting the tutorial.
Can anyone tell me why problem F1 WA on 11?
My submission:https://mirror.codeforces.com/contest/2013/submission/282168778
some problems to initialize the "lg" array. I modified it and got accept282181464
Thanks a lot!
Problem F1: My solution fails at 1326th test case of test point 2. see 282161893
I just simulate the game process by finding what next nodes the current player could reach by bfs, and block these nodes from now on. The one who can not reach any new node fails the game.
Could you give me a hack case, or is there something wrong with my code? Thanks a lot!
Why dont you learn how to stress test.....
Anyways, here you go
Your code outputs Alice, however here Alice is actually in zugzwang. If she moves to 2, she loses when Bob moves to 9 and if she moves to 5, she loses when Bob moves to 3.
Just curious, for stress testing these type of problems do you just generate many random trees?
Yes
(i, random(1, i — 1)) trees should be fine for most problems, and is what i did for F2 stress testing
Alright, thanks
Thank you!!!
My solution to E that doesn't use "greedy":
First find $$$d = \gcd(a_1, a_2, ..., a_n)$$$, then transform $$$a_i \leftarrow a_i / d$$$. We will work with this new array $$$a$$$ and just multiply the result by $$$d$$$.
Realise that because $$$\gcd(a_1, a_2, ..., a_n)$$$ is now $$$1$$$, the prefix $$$\gcd$$$ must go to $$$1$$$ sooner or later.
Imagine we have arranged the array optimally, let $$$g_i = \gcd(a_1, a_2, ..., a_i)$$$, then the answer is $$$g_1 + g_2 + ... + g_n$$$, or we can write it as $$$n + \sum_{i = 1}^{n}{(g_i - 1)}$$$.
Realise that if $$$g_i = 1$$$ then $$$g_{i + 1} = 1$$$, so once $$$g_i = 1$$$ then we don't have to care about later elements because they don't contribute at all to the answer.
Which mean to choose the optimal sequence, we want start from some $$$g_1 = a_i$$$ and go to some $$$g_i = 1$$$ with the lowest cost possible, where from $$$g_i$$$ we can go to $$$g_{i + 1} = \gcd(g_i, a_j)$$$ with some $$$a_j$$$.
So now we can try to find the best way to go from each $$$g_1$$$ to $$$1$$$, and we will do this with dynamic programming:
In my solution, I find $$$x$$$ for each $$$y$$$ like so:
The coprime counting can be done like so:
Let $$$k = a_{max}$$$, the final solution is as follow:
The iterating $$$y$$$, finding $$$q$$$, and updating $$$x$$$ is done in $$$O(k\ln(k))$$$.
The prime counting is done in at most $$$\sum_{i = 1}^{k}{O(\frac{k}{i} \ln(\frac{k}{i})})$$$. This is a bit complicated, but it should be $$$O(k \ln(k)^2)$$$.
My implementation: 282179720 (pretty much the same as the one in contest but cleared up to use the same variable name I used in this post)
This looks a bit complicated considering an $$$O(n^2)$$$ solution passes AC
https://mirror.codeforces.com/contest/2013/submission/282184391
This just starts from $$$gcd$$$ being mininum $$$a_i$$$ and on each iteration find next minimum $$$gcd$$$ with all remaining elements in $$$a$$$ and sum these $$$gcd$$$s in $$$ans$$$.
That is O(NlogN).
gcd's prime factorization will consist of at most logN numbers and each time finding the next minimum gcd will remove at least one of those numbers. Your code will loop through array at most logN times until gcd becomes 1 and it will stop. Thus it's N logNThat aside, the point of the comment you're replying to is to describe a method that we can use precisely to avoid this approach if we can't prove it.
Considering nested loops is the first thing that comes to mind isn't this problem too simple for E on Div.2?
During contest I discarded this approach as too simple, thinking it was a bait of some sort.
Well based on the fact many skipped D to solve E, probably many people will agree with you. But yeah it is definitely quite straightforward, even compared to some Div 2 D in the past.
where is the editorial? (cry emoji)
Editorial ?
why is this giving Idleness limit exceed 282218277
C can be solved with $$$2n-1$$$ operations.Just by starting with "? 01" and "? 10" when $$$n \gt =2$$$.
soullless please give the editorial
Still waiting for the editorial
Customary thanks to Dominater069 for solving the contest and providing his clean and consise solutions.
Hi, I have been flagged by the system for my solution to problem E. I ensure that the code was written by me, in a private environment. The logic is quite simple and similar to few grandmasters as well. Kindly help with this issue. I have been a trustful participant. I have also tested rounds on CF, with few coordinaters knowing me. I am happy to provide any more evidence. Thanks! MikeMirzayanov
Mansur why'd you badmouth Dimash? :(
https://mirror.codeforces.com/problemset/problem/2013/C