Спасибо за участие!
1834A - Единичный массив придумал и подготовил Artyom123
1834B - Максимальная прочность придумало Жюри олимпиады, а подготовил TheEvilBird
1834C - Игра с переворотом придумал и подготовил sevlll777
1834D - Опрос на уроке придумал vaaven и Mikhango, а подготовил Alexdat2000
1834E - MEX НОК придумал TeaTime, а подготовил teraqqq
1834F - Печатная машинка придумал и подготовил Ziware
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Fast editorial!
[Deleted]
That was quick
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.
Thankyou
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}}}$$$.
For C look at my solution
For the C solution
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.com/blog/entry/117339?#comment-1038154
Hope source code.
Can anyone tell me what is wrong in this solution for problem D? 210103552
In your approach it is not necessary that p1 is the interval with minimum right, for example intervals are- (1,10) (1,8) (2,3) here minimum right is (2,3) interval
in E, the answer is upper-bounded by the (n + 1)th prime
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.
Почему в задаче С, s сводится только к t или rev(t), разве не может быть случая когда стоит взять некоторые символы из s другие из t чтобы в итоге получился палидром и точно не потребовалось ждать ещё одного реверса от Боба?
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
So scoring does not solely depend on how many problems you solved or when you solved them, right?
So let's say someone with a rating of 3200 solves problems A and B correctly in division 2 in the early minutes of the contests. Despite that, He/She will get less score or even a negative score. Did I understand it correctly? I appreciated your response.
See this blog
Thank you so much
B is very Bad !
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.
oh I understand thanks for replying !!
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
Nice explanation thank you very much !!
L-**1234565878** R-**0000002322** can you explain in this?
In D in the fourth testcase suppose I ask first student questions 2,3,4,5 so his hand is at -4 and I ask student 2 question 1, so his hand is at -1 and hand of third is at 0, so the answer should be 4??
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.
Thenks:)
good contest_
in B
when 9 189 answer is 19, why? TheEvilBird
I think answer is 18, by using 9 and 90
Take $$$100$$$ and $$$99$$$ and you will get $$$|1 - 0| + |0 - 9| + |0 - 9| = 1 + 9 + 9 = 19$$$.
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
For E, would we also need to consider an extra O(log(M)) complexity for lcm operation?
cool
C was a nice problem indeed, and its explanation in the editorial is great as well. good job Authors!!
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}$$$.