No,you are the last PP submission. 0.0

There would be people who have missed the usual timing rounds because it is "unusual" for them .

It's your choice to live in Islamic country

People believing in Jesus are free at Sundays

you're not the only one. i can relate to this.

ok :)

Indeed

for me it was a sudden decrease from 56 to 48 :(

What part of "Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants" do you find hard to understand?

Oh boy, I literally dieded.

I almost reached rank 200, but my computer hung at the last second and it costed me 16 points. Shouldn't have submitted the code after the contest, that was freakin painful.

they forget it :)

no un

Типо да!

Во-первых, вы написали по-русски и англоязычные пользователи не увидят вашего комментария.

Во-вторых, зачем?

How does it affect you?

Well for B, you can use discount only if you are buying 2 that should solve it :| explanation sucks

If he should buy 3 pizzas, he can buy 2 pizzas with discount and 1 pizza with coupon.

Am I the only one feeling tired of reading repeated comments like this in each contest blog ?

Can you show the code please(I guess it is n * log(n)(like this))

May be complexity isn't n*n?)

Hint: think about DFS

dsu i think

Build a graph like this : If you have socks l[i], r[i], then add undirected edge from l[i] to r[i]. Now for each connected component in this graph, you must have 1 color. So we can solve each component independently. It's optimal for each component to change colours of all nodes in that component to the colour that appears the most in that component.

Consider socks as nodes and pairs as edges. Now in this graph,paint each component with the color which have highest frequency in that component.

For input
5 3 5
1 1 3 4 5
1 2
2 3
4 5

You can split all the socks into groups (sets):
S₁ = {sock₁, sock₂, sock₃},
S₂ = {sock₄, sock₅}

All the socks in group S₁ should be painted in a single color and all the socks in the group S₂ should also be painted in a single color (probably, different from the color of S₁).

For the group S_i we count the most frequent color among the socks and paint all the rest socks in that group to that color. In my example the socks in the group S₁ have following colors:
S₁ = {black, black, red}

The most frequent color in group S₁ is black, so we paint the remaining sock (which is red) to color black. After repainting the set will look like that:
S₁ = {black, black, black}.

Maybe you have to learn how to solve A and B, too early for F ..

I used some prefix array to know in O(1) time how many graphic cards are there with power from i to j.

Then for each available power of graphics, for example for power 2, i was checking prefix array every 2 (2,4,6,8) and i was increasing max result for this power by (cards in this interval)*(current value/power i was checking(2) ).

O(nlogn)

Consider every distinct tape as the leading tape and calculate the answer for this using sieve-like technique. Consider tape a[i], then all elements in range i*a[i] to (i+1)*a[i] will be added as i*a[i]. Number of elements between a range can be calculated using a precalculated array since the numbers are less 10^6.

I did it using bfs, i made disjoint sets, and tried to find out the most repeated color in each disjoint set, and subtracted that value by size of the disjoint set.

BFS works fine. The input is just not usual. For example, the input l_i = 10, r_i = 42 may be repeated:
10 42
...
10 42

this may lead you to insert 42 into adjacency list twice:
adj[10].push_back(42);
adj[10].push_back(42);

Just use dsu.

At most m edges in graph, since there can be repeated edges. How can it be dense?

Я думаю, что у очень многих участников F не пройдет системные тесты.

она использует очень стандартную идею, когда ты понимаешь, как её сюда применить, задача становится очень простой

I have the same question. It seems to be not so difficult :(

Tricky cases :( I just wonder what's the proper solution to F...

Отличное условие, мне понравилось.

You could use prefix sum from reverse to get the same and hence reduce a logn factor

Oh wait you can just compute the prefix sum. That makes sense.

my O(n log(n) ln(n)) solution passed. so I guess O(n log^2(n)) is fast enough.

For each i, iterate over its multiples. If you are currently at x*i, all the numbers in the range [(x-1)*i, x*i) will have to be reduced to (x-1)*i. So, simply add the count of numbers in this range * (x-1)*i to current ans. Repeat for all i, and take max of these.

Code

why should the main card be prime ?

Case :

4

4 6 12 36

main card : 4

But you got WA on system test 27!!

I didn't notice intervals may split during contest. To mark invalid interval [l, r], I think f[l]++, f[r + 1]-- works.

I also did similar. However "if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. " This is incomplete. There is another case.

Eg:

5 -> 6 -> 7 -> 1

7 -> 1 -> 2 -> 3

(c = 7)

As you see you could also rotate it 3 times and still ordered.

i implemented this too, but there's a catch!

Suppose n=2 ,c=6 1 2 1 3

(the numbers are 2 and 3)

Then according to the above logic you can turn max:3 times but if you turn 5 times it again becomes valid. Hope it clears the doubt!

You have missed out cases.
Let a be the char of the first word and b be that of the second word, at the first point of difference.

If a < b, the valid range is [0, c-b] U [c+1-a, c].
If a > b, the valid range is [c+1-a, c-b]

Then from the valid ranges of all the pairs of adjacent words, you can choose any common value. If there is no point which is common to all the ranges, answer is not possible.

Also, apart from these, if the second word is a prefix of the first one and is shorter than the first word, answer is not possible.

Code

You're declaring this array ll cnt[223456] too many times.

If the graph is empty, your codes is O(N²), because of this:

memset(colNow,0,sizeof colNow);

The problem isn't in dfs i think. But in

memset(colNow,0,sizeof col)

Think when there are many connected components, it will get tle.

In the worst case memset would be called 2*10^5 times , which is basically O(N^2) . Use a map instead .

you can save the vertices that you go to them in dfs ,in a vector and after dfs make the colnow of them equal zero or dfs again and do it

What I did was this.

Let DP[1][i] be the max score which can be obtained by Petya, if in his next turn he has to choose a prefix of length at least i and let DP[0][i] denote the same for Gena.
Let S[j] denote prefix sum till j, i.e. arr[1]+arr[2]+arr[3]+...arr[j]
Petya tries to get the maximum value possible and Gena tries to get the lowest value possible.

DP[1][i] = max(S[j] + DP[0][j+1]), j>=i
DP[0][i] = min(-S[j] + DP[1][j+1]), j>=i

The answer is given by DP[1][2] (1-indexing is used).

Code

Dynamic Programming on prefix sum array

check this:

http://mirror.codeforces.com/contest/731/submission/21488865

Let S[i] be the sum of the numbers from 1 to i.

Let D[i] be the optimal maximum difference for the current player if the leftmost sticker contains the sum of the numbers from 1 to i.

Then D[i] = max{S[j] — D[j]} for i < j <= N.

But since S[j] — D[j] is independent of i, we can just keep track of the maximum S[j] — D[j] and update it at every loop, leading to O(N) solution.

code: http://mirror.codeforces.com/contest/731/submission/21495276

You never have to color both the right and left sock though..

Hope that comment helps.