Thank you for participating!
1834A - Unit Array was authored and prepared by Artyom123
1834B - Maximum Strength was authored by jury of the olympiad, and prepared by TheEvilBird
1834C - Game with Reversing was authored and prepared by sevlll777
1834D - Survey in Class was authored by vaaven and Mikhango and prepared by Alexdat2000
1834E - MEX of LCM was authored by TeaTime and prepared by teraqqq
1834F - Typewriter was authored and prepared by Ziware
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
[Deleted]
Fast editorial!
Great contest. Good problems!
Thanks, bro!
Fast editorial!
It's a pity that I didn't manage to solve D, by the way.
[user:Ormilis] Please add a case with 1e5 elements 2,3,2,3,2,3,...... in problem E. Many solutions are accepted which will run in O(n^2) for this test case since lcm will never exceed its limit and no multiple of lcm is present in this case.
I made Video Solutions for A-E.
This seems to be unintended $$$O(n \log n \log^2 {10}^7)$$$: 210082970
I'm actually surprised there were no strong tests like $$$a_i = 2^{\frac{i}{\tt{const}}}$$$.
can not understand why the answer of question E is no more than 1e9, any strict proofs?
In order to have $$$lcm$$$ be equal to a prime number we must have it in the array. So we only have $$$n$$$ places for prime numbers, that means we cannot ever get $$$n+1$$$ th prime number which is $$$4256249$$$. So we can bound it at that number also.
Because of the prime fact you can also say that $$$1e9+7$$$ will never be included, because $$$a_i\le1e9$$$ and $$$1e9+7$$$ is prime so you cannot put it into the array.
We can prove it to be 2N+1 at most https://codeforces.net/blog/entry/117339?#comment-1038154
Hope source code.
Can anyone tell how to efficiently find the segment which has the shortest length and lies completely inside a given segment in problem D.
Just find the overall shortest segment and assume it lies inside the segment you are checking -> If not, you will check the outer segments anyway, so it won't change the answer.
I can do it by segment tree?? but is there any other method ??
To find the overall shortest segment? It should be just a simple iteration through all segments. Something like the following:
hope this helps comment-1047413
I have figured it out why simply check the overall shortest segment works:
Let's pick up a segment A, and find another segment B which shares the shortest common subsegment with A.
If the shortest segment lies out A, it will share 0 element with A, we can simply choose it, because this will be the optimal choice. When the shortest intersect the beginning or the ending, we can tell that any segment completely lies in A will not product a better answer, because any other segment inside A shares no less than the length of the shortest.
If the shortest lies completely in A, you should check if there are other better choices by check the segment have the largest ending and the one with smallest beginning.
So there is need to find such a segment you are looking for.
I am a newbie. I just participated and solved problem A and it got an accepted verdict. After solving problem A, I left the contest. I just noticed that I have got a -18 score. Are there cases where even if you solved the problem but you got a negative score? Is it just because I solved it late or because I solved only one problem? How are generally contests assess the solved problems? Thanks for the clarification in advance.
You get score based on your ranking in the contest and your rating. Basically if you perform better than would be expected of someone with your rating, your rating will increase and if you perform worse, your rating will drop
Hello everyone In problem 1834B - Maximum Strength i am not able to understand the part where it is written like "Now we can represent the numbers L and R as their longest common prefix" can anybody help me ?
The editorial says that the numbers L (after padding with zeroes) and R can be represented in three parts. The first part is the longest common prefix, the second part is the index where L and R differ for the first time and the third part is the remaining string.
If you're given for example
and
we see that the red part (the longest common prefix) contributes $$$0$$$, the blue part (the first digit where $$$L$$$ and $$$R$$$ differ) contributes at most $$$8-6=2$$$, and for the green part (the rest), we can pick $$$9999999$$$ for $$$L$$$ and $$$0000000$$$ for $$$R$$$ (because whatever you set, the blue part ensures the first number is already smaller than the second). Thus the answer is always
L-**1234565878** R-**0000002322** can you explain in this?
Is the 4th tc of D wrong, as suppose I ask stud1 ques 2,3,4,5 so his hand is at -4 and I ask stud2 ques 1 so his hand is at -1 and the hand of stud3 is at 0 so the answer should be 4 right??
You're supposed to ask the same questions to all students, so if you ask questions 2,3,4,5.
Student 1 gets a score -4
Student 2,3 get a score of -2.
Hence difference is 2 in this case.
can problem B be solved using digit dp?
You can take a look at my submission.
Amazing round! Enjoyed the problems a lot.
I think test cases maybe weak for problem $$$E$$$, I have two almost identical solutions where one is getting AC in ~0.7s and the other is getting AC in ~1.5s
My solution is the same as the editorial but I perform the actions in a slower (dumber) way. My algorithm is as follows:
I think time complexity is $$$O(N \log N \log 10^7)$$$
The other nearly identical solution that is slow is, Instead of iterating over $$$r$$$, I iterate over $$$l$$$ and perform the equivalent actions.
without #define int long long
Soln1 submission: 210273930 AC with 0.7s
Soln2 submission: 210273834 AC with 1.5s
with #define int long long
Soln1 submission: 210271657 AC with 1.6s (hackable)
Soln2 submission: 210271736 TLE
In problem B
Let's say L = 68 and R = 72 according to the editorial ans = abs(6 -7) + 9 = 10 But is 10 possible?
Choose 69 and 70 from that range. First digits differ by 1, second digits by 9.
anyone managed to solve E with sparse table?
Me 210335889 although it is possible this can be hacked.
Edit: Shaved 600ms off that with 210346369, although again I wouldn't be surprised if this could also be hacked
My $$$O(nlog^2a_ilogn)$$$ for problem E passed. 232426932
I think there was a typo in problem E's editorial: $$$n^2 \ge x^2 \ge 2^{k - 1}$$$ which is actually: $$$n^2 \ge x \ge 2^{k - 1}$$$.