Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and gritukan under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

**UPD** The contest is over, results are final, thanks for participating! The editorial will be published later

**UPD2** I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

An automorphic Round (376)

376 * 376 = 141

376Am I the last AC submission ?

No,you are the last PP submission. 0.0

Oh I have passed main test :).

Most of the schools are

openat that time in Iran (and maybe other countries) :(Missed four consecutive rounds just for the unusual time :(

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

I wanted to downvote this, but upvoted instead :p

unusual comments.. unusual comments everywhere

I think there can be a time dicipline all people have

`usual`

time!It's your choice to live in Islamic country

People believing in Jesus are free at Sundays

you don't have to be rude !

I didn't want to. Just pointed out how ridicilous is this argument, considering the fact that in most countries Sundays are holidays.

It's impossible to fit in every schedule. That's why contest time changes. To fit other's schedules.

I don't think " People believing in Jesus " is just pointing out !

Actually I don't care much about what you think

Actually you don't have to be rude at all

If truth is too rude for you go meet with your therapist, you have plenty to talk about.

there are too many christians in the middle east and the islamic countries -_-

Not racist.

Poor people...

Also I didn't figure out how is racism relevant here. At my memory religions only fuels it, don't they?

Codeforces should ban all the racist people, whatever their color is.

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

downvote me plz

ok :)

I hate this new usual time :(

Most of the Middle East universities are open in this time :'(

Indeed

Did anyone notice a sudden increase in contribution points? My contribution went from -30 to -3 in less than 3 days, without any wave of new upvotes.

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

Law of conservation of contribution

In contest invitation mail Zlobober isn't legendary!

The time is very good for Chinese competitor.

But it is a pity that the beginning time of this round is just the ending time of Dalian regional contest.

In the registrants list, Div. 1 participants are not marked as unofficial participants. Is that normal?

Update: it's fixed, actually.

why div 1 participants are not unofficial ?

Update : fixed

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?

The round starts 1.5 hours after Google APAC 1D ends.

Will have to eat quickly, rest in that time and be ready for the round. :D

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.

Sorry to hear that you literally dieded.

Rested in peace.

Love the timing of recent contests. Usual timing is 2am for me, so am happy to actually be able to participate in a few contests.

But I understand that others may not agree :)

I'll join. It's my first time.

Why do rounds these days occur at this unusual time?

score distribution?

they forget it :)

yeah :-)

Ok :)

6 problems for 2 hours.Hopefully problem set will be easy at least 3.

Best wishes everyone.

10 minutes Late:)

Start delayed! How unusual!

no un

2333

2333333333

Score distribution?

Why Delayed ?

I just don't get what is this problem which happens right in the begin of the contest and can be fixed in 10 minutes !

How does it affect you?

could some one say problem B more clear ? ! i cant understanr it : ( pleaseee ...

is it possible for sereja not to order any pizza on someday in 2nd problem

Problem B, Could He uses both coupons and discount at same time? like if it is 50 pizza, could he use 48 coupon and 1 discount?

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.

My submission for D is in queue for 5 mins. Still waiting.

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

i hacked on F with complexity n*n for n=10^5. It failed ! Does the new server support 10^10 ??

Edit: Got it ! My test case wasnt good enough !

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

http://codeforces.com/contest/731/submission/21488890 Another guy hacked him for me :p !!

May be complexity isn't n*n?)

How to solve C?

Hint: think about DFS

dsu i think

I too thought of dsu, but it kept failing at pretest 5. Any reason why it might not work

same with me!

Can anyone illustarate smooth dsu solution

build a graph with undirected edges from each l[i] and r[i].now socks at indices l[i] and r[i] must have same color.now use dfs to find the connected components.its just like a normal dfs on undirected graph with edges from l[i] to r[i].each connected component should have same color.after finding components,for each component find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings.for reference you can see my code.21497227

Damn, I spent about 1.5 hours on this problem and couldnt solve it. How do you guys think up these solutions? I understand it, and it is quite simple, but why does it actually work? "find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings" — I understand that sometimes you just see the pattern and cant prove it, but how to see this pattern... :( I failed many problems just not being able to see the pattern. How can I improve this skill? Thanks in advance

me too couldn't solve it during contest and i realized it later. I think it all comes with practice.

I hope so. ) Thanks for your reply.

From my practice experience, whenver I think of a strategy in a scenario I go through steps like this:

Come up with preprocessing ways that helps you analyze the situation.

If it's a game then most of the time it is minimax considering it is the most frequent one that pops up.

Go for greedy, enumerate a few test cases that I think that could be tricky to handle. If greedy still works, then go for it.

If not, see if there is a dynamic programming relation between the states. Go for dp if it is available.

If there is still no solution, then you are probably missing some major observation. Dig deeper into the sample cases for inspirations. Also check if the constraints are small enough for more naive solutions to pass.

Thank you a lot! I will try to use this strategy in practice.

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.

I used DFS....as u said.. But someone hacked me.. How? here is my solution solution

for(i = 1 ; i <= N ; i++){ if(visited[i] == 0){ for(j = 1 ; j <= K ; j++) countcolor[j] = 0; _max = 0; ll v = dfs(i); ans += (v-_max); } }

It works only with a few components count. I guess if theres maximum N and M — min, for instance 1, this would be N*K, while N = 2*10^5 and K = 2*10^5, which is TL, obviously.

you are looping through color array every time.here your worst case will be N*K.instead just use a map and you can clear the map every time you run dfs.

shit.... This simple thing !!! I should have thought of that

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.

Could you tell me how to find the highest frequency in a independent component ?

Dfs and store in map amount of each color.

yes, a map indeed. I tried to find it with an array :(

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_{1}= {sock_{1},sock_{2},sock_{3}},S_{2}= {sock_{4},sock_{5}}All the socks in group

S_{1}should be painted in a single color and all the socks in the groupS_{2}should also be painted in a single color (probably, different from the color ofS_{1}).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 groupS_{1}have following colors:S_{1}= {black,black,red}The most frequent color in group

S_{1}isblack, so we paint the remaining sock (which isred) to colorblack. After repainting the set will look like that:S_{1}= {black,black,black}.How to solve F?

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

It seemed interesting, because for small constraints it works but I got TLE for large ones which means I was doing something really wrong. So I am interested in learning.

Lets not judge just by looking at color of handle :)

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.

please explain C I tried to do it bfs but it doesnt seem to be like that

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.

this was my code, when i realized that it fails sample test 2 please help me what is wrong?

Can u copy send link to your solution instead of copy code ? This seem inconvenience. sory fo my bad E =)

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);`

That's why i prefer map<int, set> for adjacency list.

Was anyone else facing problems with opening the site? I couldn't open the site for half an hour during contest.

How did people use graph solution for problem C? What if graph is really dense ? It should go out of memory..

Just use dsu.

Dont you think that people who used graphs should get MLE on like 10000X10000 dense graph?

Wut? There is only 2e5 edges and verticles, you can find connected compounds easily.

Never mind, i think i need more sleep...

http://codeforces.com/contest/731/submission/21488359 I am getting TLE on pretest 6 using DSU

http://codeforces.com/contest/731/submission/21482988

I did using DSU check it out

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

What is wrong with following approach for D? It gets WA on pretest 5.

Toposort the letters keeping in mind the word constraints. Check for cycle, if so print -1. Also check all nodes in graph are connected. If this is ensured, sort the toposort and check if it is possible at some level to break the sequence into two parts such that they are

x,x+ 1,x+ 2, ...n- 1 followed by 1, 2, 3, 4....,x- 1. Submission: 21492973Was F easy or there are some tricky cases waiting in system testing

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

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

I will fail b because I declared N to 1e5 and not 2*1e5, horrible mistake but I'm wondering why pretest doesn't cover such case!

Are you sure it was 2*1e5?

E: :( It was, I thought the max no of elements for A was 10000 but that was for Ai

Very interesting round to me !

I saw a lot of random solutions for F and some greedy for E... It will be a lot of WAs.

Can F be solved with a fenwick tree, and summing contents of the intervals between each power? I think that is O(n (log n)^2), is that fast enough?

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.

How to solve F?

I noticed that the main card should be a prime, or 1.

Then I wrote a sieve and a map to insert a number along with its index (in sorted input) in the map for each of its prime factors.

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

I over complicated things.

why should the main card be prime ?

Case :

4

4 6 12 36

main card : 4

I was wrong

D was really interesting. I got AC it using BIT. First of all, ans can be in range [0,

c- 1]. For every successive interval, I found what intervals can lead to correct sorting order(handled byLandR), and what intervals cannot(handled by BIT). I maintained the interval [L,R] that contains the answer, and also BIT stores what index cannot be our answer. Finally, for anyL≤i≤R, if BIT allows this to be an answer, print it. Otherwise answer doesn't exists.But you got WA on system test 27!!

Yups, did not get AC. Test cases aren't available as of now. So cant tell much about the reason.

Most probably I forgot to add "return 0;" when I check whether

L>R. So it would print - 1 twice.Yes that was the problem, It got AC now. Code

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

Is the following approach for D right? I implemented this algorithm but it doesn't pass some pretests. Where is the mistake in this solution? Take two adjacent words, find the first position where letters are different. If the first letter is greater then we need to turn the wheel by minimum (c-a[i]) so that it becomes smaller than b[i]; if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. Store the maximum of the minimums and the minimum of the maximum and if the second value is less than the first then print "-1", else print the first value.

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.

Hell, how haven't I noticed it.(

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

Shouldn't the valid range for a<b be [0, c-b] U [c+1-a,

c-1]. The problem statement expects an ans in [0, c-1] and the changes in c steps in fact reflect those that can be done 0 steps. Seems the test cases are weak.Code

It doesn't matter since if [c] is available then [c%c=0] is also available, and the smallest solution always get chose first.

I used DSU for DIV2 C but I am getting TLE on pretest 6.http://codeforces.com/contest/731/submission/21488359

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

http://codeforces.com/contest/731/submission/21493869 resubmitted but result still same

It's the same complexity now. Memset on N elements is O(N) so you're calling it at most N times -> O(N ^ 2) complexity. I solved it like this : when i dfs, i store the nodes in current component in a list. So now i only need to reset for those. Each node appears in one component -> O(N) complexity for that part. Here's my code: http://codeforces.com/contest/731/submission/21485829.

Thnks a ton. I didnt know that memset on n elements is O(n).

I solved the C problem with DFS, but I got TLE... How to optimize my code? http://codeforces.com/contest/731/submission/21484127 Or is it just recursive vs queue? XD

If the graph is empty, your codes is

O(N^{2}), because of this:The problem isn't in dfs i think. But in

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

kudos to the author for such a nice contest!

What's the idea for solving E ?

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://codeforces.com/contest/731/submission/21488865

your solution is pretty good,it's easy for me to understand

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://codeforces.com/contest/731/submission/21495276

How you are taking account of the two persons , please elaborate?

The best play for one person in a certain configuration is the same as the best play for the other.

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

S[j] is what you get from choosing up until the sticker j

D[j] is the best play on the configuration j

So you choose the best play possible for every situation.

As I see, problem F easier than problem D & E, problem B easier to WA then problem F :)) funny contest

This time is so good for chinese competitor.Thank you for your good game.

Hopefully become Expert:)

You did it, brave move :)

I think problem C can be interpreted in 2 ways.

1. Counting cost of colouring of both left and right pieces of i-th pair of socks as 2.(Counting colouring of each left and right sock seperately)

2. Counting cost of colouring of both left and right pieces of i-th pair of socks as 1.

During the contest, I have implemented assuming case:1, which failed on pretest 3.

After the contest, I see that I was supposed to assume the other case.

Here are my submissions with only difference being which assumption was considered among the above.

Assumption-1 : 21492459 Failed

Assumption-2 : 21493466 Accepted

Should have got this clarified during the contest :(

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

can someone identify the mistake in my submission for "C", i keep getting WA on 6.

code = http://codeforces.com/contest/731/submission/21492734

Hope that comment helps.

i tried a testcase with repeated indeces , it is giving correct output for that .

Your code gives negative answer. That means the expression

`(size - maxi)`

sometimes is negative, that is sometimes`size`

becomes smaller than`maxi`

. You can try thinking backwards and work out an example when this is true.You use variable 'i' in two loops that are nested.

i corrected that , it still gives WA on 6 .nevermind , got it !

It would anyways TLE , it is O(N*K)

Rating Updated!

Got TLE for C at test case 33 mysolution . I tried with DSU. Could somebody help?

DSU solution http://codeforces.com/contest/731/submission/21498336

what does map<> h stores? count of occurrences of colors?

there's a small thing that needs to be considered .i think you are clearing the count array every time you run dfs.instead use a map and clear it.

my AC solution: Solution link

needed to replace count vector with map -- to avoid TLE

needed to avoid members insertion during UNION -- to avoid MLE

Thanks

Finally I'm Cyan !!, and I solved 3 problems from the first submission.

Self confidence is rising here !

thank you Zlobober very much for the nice contest

No hacks this time :-)

http://codeforces.com/contest/731/submission/21485811 WA in test case 66 :( Can anyone help ?

Someone please point out the bug ... unable to find it ....

In the last loop in main(), the upper bound for i should be m instead of n.

Why does this TLE for F ?

http://codeforces.com/contest/731/submission/21494655

I also unintentionally did the same mistake...Since the

values of array may not be distinct. So, we should avoid calculation for same elements , otherwise if we calculate for value say, 1 or 2, for many times, then this will lead to O(n*n)...I had sorted array, then was trying to escape repetition, but forgot to do that while coding,, finally, which causes TLE :( .How do you solve problem B? I wrote "something" which passed the pretests but it doesn't work it some cases. What's the normal solution for this problem?

Iterate from left to right . If arr[i] is even we can use coupons and we are done . But if arr[i] is odd , arr[i+1] should exist and should be positive . If not print NO else do arr[i+1] -= 1 .

Thanks, that's so easy and obvious...I actually thought the same but then was misled by some example which I treated incorrectly.

anyone can find my code bug for problem C ????? I'm using DSU , calculating all socks needed minus the largest number of colors for every parent. http://codeforces.com/contest/731/submission/21491376

What does the function

`join()`

return?nothing

You are coloring everything with the maximal color, not the color with maximal number in map( because pairs are sorted by the first element, not the second).

:'( F gave TLE on 26th test passed just by fast I/O Yeah Life is unfair!

I don't know why, but I found Problem B very tough (I solved it somehow though :P). Can anyone suggest a simple solution?

Here is mine:

The result is 'YES' if sum of remain elements in a is 0. Otherwise, it is 'NO'. Hope this helps.

Break the array wherever 0 is present. Find sum of each part. Answer is YES if sum of each part is even.

Code

from 0 to n-1 if a[i] < 0 answer no and break; else if a[i] is odd substract from a[i+1] 1;

then check last element a[n-1] if its odd or less than 0, answer no;

otherwise answer yes

There is something mystery in this contest for my case. My code for solving problem C returns 2 for Test 5, which is correct, on my computer. But when I upload the code, it became 3, which is wrong answer.

Because it's correct on my computer so that I have no idea where it went wrong. Please take a look: http://codeforces.com/contest/731/submission/21493963

Many thanks. P/S: Picture proof.

Which ide are you using?

it's sublime text

The Sublime Text 2 + SublimeInput for internal testing.

Comparator in C++ must return 1 if the first argument is less, then the second. Otherwise 0.

Nice round.. I think problem F was overrated ... it should have been a C or a D. however it was an interesting round. thanks

3 points from getting blue :C Anyways, can someone please tell me the solution for problem F?

Let

f(x) denote the number of integers that are ≥x. Then, if we fix a numberias leader, the total sum will bef(i) +f(2i) +f(3i) + ....We can precompute

f(i) for alli≤ 200000 by using the same method as sieving primes. The time complexity is .Interesting, I didn't think about that.

If you don't precompute f(i) you can use binary search to find it, making the complexity O(n*logn*logn) but without the need to worry about precomputation.

Very nice solution, thank you.

Interesting solution :)

I don't understand even if you precompute f(i) for all i<=200000, then also you have to sum it for i, 2i, 3i, ... (200000/i) elements. Why isn't it O(n^2). Here's my solution along the lines suggested by you, it's getting time limit exceeded and the reason I could think of is the above. Am I missing something.

http://codeforces.com/contest/731/submission/21516249

Make sure you don't visit the multiples that you have already visited and it should get accepted. You took care of the case with repeated ones but look at the one you got TLE'd (repeated twos)

Edit: it is worth noting the reason why this is O(nlogn).

If you don't visit the same number twice, it takes at most N+N/2+N/3+...+N/N.

That's the same as N(1+1/2+1/3+...+1/N). That sum is bounded by ln (look for the integral of 1/x from 1 to n) so the complexity is O(n*logn).

Thanks!

deleted

Spent an hour and 2 wrong submissions on C because I thought you had to color socks dynamically every day and not just all of them at once beforehand. :D

Good thing I went and solved F before realizing how easy C actually was.

Just wondering, how to solve C if you can color socks dynamically?

anyone knows why my solution for c fails? http://codeforces.com/contest/731/submission/21498239

All the best guys

Can someone explain the solution to Problem D?

Here is my approach:

For each block i (0<=i<n-1), compare them in lexigographical order. It should fall under one of these cases: (Let j be the position where a[i] and a[i+1] differs)

a[i] is a prefix of a[i+1] — Great! We don't have to do anything, a[i] < a[i+1] is always true.

a[i+1] is a prefix of a[i] — Great! Now we are screwed! The door is always locked.

a[i] is currently lexigographical smaller thatn a[i+1] — Then calculate when will a[i] and a[i+1] go through the cyclic shift at j. During the period where a[i+1] has gone through the cycle and a[i] haven't, a[i+1] will be smaller than a[i].

the reverse of case 3 — We will also calculate the cyclic shift time. This time, only the period where a[i] has gone through the cyclic and a[i] haven't will allow us to open the door.

You can see that there will be intervals where you can open (or not open) the doors. Now all you have to do is check for the earliest moment where you can open the door.

(You can use the range fill technique to invalidate a time interval. See my code here http://codeforces.com/contest/731/submission/21498917 )

Can u please elaborate the last part of your solution. Means how you are using the chk[] array to check for intervals where we can shift the lock ??

Let's say we are counting the amount of intervals at a certain point. The most naive solution is to increament each of the points within the interval by one — but this takes O(n) time to mark each interval.

Instead, we can increase the start of the interval by one, and the point near to its' end of it by one, and calculate the prefix sum after we have mark all intervals, and this will tell us how many intervals lie on a certain point. Why does this work? Consider each interval individually, the prefix sum will cause all points on interval [left,right] increase by one, yet since [right+1] has a value -1, therefore it gets canceled and the interval [right,n) remains uneffected.

Thanks A lot. :)

mfw practicing and see F only have the "brute force" tag.

nvm they fixed it. =]

I liked how none of the problems used complex data structure and algorithms.

quite surprised about the AC number of each problem.

I think E is quite easy, the idea is easy and very easy coding.

D is a little complicated to code, but the idea isn't hard.

F is hard for me, I didn't figure out a way by myself even after contest.

I hope for an editorial for this contest, as well as for Technocup.

plz upload the editorial!!!

I Can't get What is wrong on my solution... Solution I get Pretest Passed at 1:59.. but failed to pass Main test at Test22.

Please Let me know Why my solution is not working on this test case like 19999 10001 10002 10003 10004 ...

I solved The Problem F bruteforce. 1. sort input 2. from the small number to large number in the input, vec[1...n], Iterated if the mainpower key is v[i], if v[j] % v[i] == 0, pass. or not, v[j] -= v[j]%v[i] ( to make secondary power) 3. print the answer

The answer is 200000 * 199000

Oh my... Thanks a lot. I realized

You should say, "I submitted The Problem F bruteforce" instead of saying, "I solved The Problem F bruteforce", since all of your submissions for F got WA!

Thanks for giving great advice!!

i think there maybe some mistakes of problem F. the two same codes, the first code, define maxn=1000100,it AC;21510847. the second code, define maxn=200100,it WR on31;21510692.

Because you used num[j + i]

i see. my mistake .thanks a lot :)

21506585 — > What is my off by one error? :(

Could anyone comment the Problem E example 2?

B is not playing optimally in b)

turn 1: A takes 1 -7, puts -6

turn 2: B takes -6 -2, puts -8

turn 3: A takes -8 3, puts -5

A's score: -6 + -5 = -11

B's score: -8

diff = -11 — -8 = -3

Sometimes you can force a turn on others and thus reducing their scores. >=]

optimal moves for input2:

turn 1: A takes [1,5], S= -20000. turn 2: B takes [1,2], S= -21000.

Difference in score= +1000

When will the editorials be up!?

It's finally there: http://codeforces.com/blog/entry/47840

I'm sorry for the delay.

Where is the tutorial?

Right above ya

not able to understand why to use DSU for the div2C problem.

Could someone please explain.

@Zlobober Please add tutorial to the box names [→ Contest materials] on the righ_bottom of web-pages of the problems. Thank you.

Check it now :)

Thanks a lot~