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.

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 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

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:

Codehope 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

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

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?

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_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?

Cwas 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