thanks, you too

Hey can you help me, I accidentally submitted code for A problem while thinking about pretests and now the time shows after 2h, but I had solved it before 10 min. It's a huge decrease in rank. Please a help will be great, I just commented after the contest so it can be considered. Please if that submission could be removed and my score revaluated.

Can you please also wish for green to become cyan?

Don't know about greys but i was green and now became grey.

I think it will have standard codeforces problems, but the ideas of the problems are based from the Belarusian Regional olympiad

THank you CODEFORCES for round with 5 problems.

Good luck then :)

what is the second contest?

Also div1 pupils.

it's gone, hope you're happy now :D

You will see on the contest whether it's easy or not :) We cannot change the problem, as it is already prepared.

Am i the only one who read it as easy forces.

It really took me around 10 mins just to understand the statement of A....due to which this contest became the first div 2 contest in which I solved B faster than A xD

Essay Forces!!

I participated in olympiad, this problem there today, so it's really easy

ruined by kids downvoting and crying over it

I love pretest 5 and MLE on problem C.

Wish the memory limit were 512Mb.
Tried really weird things to make my 3D dp ~476Mb solution pass (array of maps and maps of vectors, lol).

Yes, but they are more clear and contain more explanations, so you most likely will understand the problem from the first read.

That's why i solved it in 7 minutes xD

With a simple greedy solution (eliminate a sign which is causing the largest delay at each step), I came till pretest 8.

I don't know such solutions. Use dynamic programming.

Greedy is not feasible for problem C.

try this test case:

10 18 3
0 1 3 4 6 7 9 10 11 12
2 3 2 3 2 3 2 3 4 3

the answer is 42, meanwhile greedy approach is likely to give 45.

Take a look at the illustration:

So use dynamic programming, I hope my submission 142583078 may help you.

Special case: if $$$k = 0$$$, the answer is all indices from $$$1$$$ to $$$n$$$ inclusive. Hereafter we assume $$$k \neq 0$$$.

Partition the values $$$a_i$$$ into groups according to the prefix of bits higher than $$$k$$$'s most significant bit. Observe that you can consider each such group individually, as any two values from two different groups will xor into a prefix that's greater than $$$k$$$'s most significant bit.

Now in each group, we can always choose at least one member, and at most two members, because if we choose more than two, there will be two values that will xor to zero in the position of $$$k$$$'s most significant bit, thereby producing a value less than $$$k$$$.

To find out if we can choose two values from a group, we find the pair with the maximum xor and compare it with $$$k$$$. Finding the maximum xor of two numbers in an array is a well-known problem (but you'd need to modify the algorithm on this page so that you know the indices of the pair) and can be done in $$$O(m \log k)$$$, where $$$m$$$ is the number of values in the group. Therefore the total time taken over all groups will be $$$O(n \log k)$$$.

Observation is that a minimum value of $$$a_i \oplus a_j$$$ is achieved at some two adjacent numbers after sorting.

After sorting, you can write simple dynamic programming, $$$dp_i$$$ — the length of the longest subsequence that ends with $$$i$$$. Transitions are very simple $$$dp_i = max$$$ {$$$dp[j]+1$$$}, where $$$a_i \oplus a_j \geq k$$$.

It can be optimized using trie.

my solution passed with this complexity.

I have $$$O(n^2 \cdot k)$$$ and I passed pretests. $$$500^3$$$ should fit if you don't do expensive operations.

A was easy, It was based on bits and count of which is more 0 or 1, My submission My sub

Me reading all problems after 2 hours

Hint : Try to think of 3 state Dp transition and optimize space complexity

dp[i][j] = minimum time to reach L from ith speedpost (this speedpost is not removed) provided you are allowed to remove j speedposts in the middle.

Dynamic Programming. Lets iterate over the stops only. M(i,s) = minimum time to reach ith stop. ans = min {M(n,s')} where n-k <= s' <= n.

it depends on how efficient your implementation is. I'm pretty sure that my 142503668 is $$$\log^2$$$, and it got AC in 1.6s

142482987 Here

problem B

bit trie

I think the below approach is correct.

damn, I don't know how I missed that :(

I hope this is not my mistake

Maybe an interesting extension for type 1 queries is to guarantee that $$$s[l+1 \dots r-1]$$$ is an RBS.

Yes, here is my code: 142512011

Exactly, I also faced the same issues. in the end, I had to write the code in C++ ( which has the same time complexity and space complexity as of python code) and it got AC.

I didn't get why you want to maintain the size of map entry to 2.

I just collected all the indices and did the max among every two consecutive indices https://codeforces.me/contest/1625/submission/142480649

Trie is not needed if you make use of the observation that choosing elements with different msb (most significant bit) are independent and to consider which elements of the same msb should be chosen, we just need to switch off the msb and consider the subproblem recursively.

At the last step, when the msb becomes smaller than or equal the msb of $$$k$$$, we can make use of this to check whether there exist a pair of numbers whose xor exceeds $$$k$$$, and if otherwise we just pick any random number.

Hint — you can take at most 2 elements from a group of unique elements, not 1. Think about it.

Hope this helps https://codeforces.me/contest/1625/submission/142530775

Let $$$dp(i,j)$$$ = min time to reach $$$d_i$$$, by removing $$$j$$$ signs. Assuming $$$d_n=l$$$, the answer is minimum of $$$dp(n,j)$$$ over all $$$j<=k$$$.

Recursion: Consider computing $$$dp(i,j)$$$. One candidate for $$$dp(i,j)$$$ is $$$dp(i-1,j) + a_{i-1}*(d_i-d_{i-1})$$$. But it's possible that we removed the $$$(i-1)$$$th sign, so we drove at speed $$$a_{i-2}$$$ from $$$d_{i-2}$$$ all along, so $$$dp(i-2,j-1) + a_{i-2}*(d_i-d_{i-2})$$$ is another candidate. Continuing with this reasoning, and also noting that we could not have removed more than $$$j$$$ signs, we get the recurrence:

$$$dp(i,j) = min_{p<=j} dp(i-1-p,j-p)+(d_i-d_{i-1-p})*a_{i-1-p})$$$.

Base case is of course $$$dp(0,*)=0$$$.