Hello, Codeforces! :-{D

As two important events IOI and ACM ICPC are coming soon, me and my friends as the Iranian IOI team decided to prepare a gift for all the Codeforces users who'll soon participate in one of these events, and also everybody else. :)

This round authored by me (havaliza), dani1373 and keivan with help from fab. I want to thank all the Codeforces team for their kind and great effort to maintain this website.

Hope you enjoy solving the problems as much as we're enjoying preparing them! ^.^

**Update 1.** The score distribution for Div. 1 is **500-1000-1500-2500-2500** and for Div. 2 its regular.

**Update 2.** Special thanks to Aksenov239 who helped us so much to prepare this round.

**Update 3.** Here is the editorial. To be completed soon :)

Good time for Chinese!

Nice moustache :)

like!

'#198' ?

Wish you 4 shiny gold medals :-) I believe the contest is going to be one of the greatest.

Thanks to the early time because I have an exam on 24th morning. :D

I'm going to be travelling at the time of the contest... which, of course, doesn't mean I'm giving up on doing it. As long as I get internet connection in a train...

The network in a train could be really instable, I have suffered several times because of this.

early time is good! since there is cookoff also on codechef.

Email I've just received says that round will be today (22.06.2013). A bit confusing. Is something wrong with my calendar?

Change tag, it's wrong.

worst time for Iran I guess. Nobody can participate :( . Everybody is in the club :D

I want to see you in IOI!!

Hope to see you in IOI! ^.^

This time we do both the contest codechef/cookoff and codeforces Div I/II round Really good timing :)

I hope the english will be understandable this time! :)

Ну вот, щас на кф ещё и систему ЕГЭ введут... а преподы из школ будут следить, чтобы мы не списывали.. :)

I'm sorry, but what was popped out?

If you mean a JavaScript alert that popped out about 30 minutes ago (for me), it's a change to the rules:

Attempting to digitally extract other contestant's code during the hacking is considered cheating. You may not use any technical/digital tools to obtain other contestant's code, including (but not limited) ORC, traffic capture, browsers plugins and so on. The only allowed method to analyze other contestant's solution is reading it in a hacking window. However it is allowed to manually retype the solution or it's parts to run it locally.(Can-do's and Can't-do's, item 8)

If you mean the pop-up a few minutes ago, the theme of the announcement was 'Hacking during the contest'. It said, that we aren't allowed to use any technical help in form of tools etc. to extract defenders code. We are only allowed to analyse it by looking or we may also write parts of the code down manually. Edit: ah, a few seconds too late.

copying contestant's code to hack using any plug-in is considered cheating, but it's OK to retype it

Количество зарегистрированных во втором дивизионе равно моему году рождения — надеюсь это хороший знак=)

Ahhhh, having to look at "Codeforces is temporary unavailable Possibly the server is too busy, something has gone wrong or it is server maintenance. Anyway try again in a few moments. " during the closing stages of the competition, when trying to submit a solution wasn't too enjoyable :(

I hate those moments when I think I did well in contest and it's unrated because of server problems :-(

Is pretest 2 at problem E (div 1) correct? I don't see any solution passing it.

I passed and I got WA on pretest6 ...

And I found that I may got WA on this test

4

1 0 5

1 2 3

2 1 2

2 2 1

The answer should be

NO

YES

But sometimes even i passed this case, i got WA on pretest2 again.

This test is incorrect — interval lengths have to be increasing.

Hmm.. I didn't consider that, sorry for the mistake.

But if I swap the second line and third line.

4

1 2 3

1 0 5

2 1 2

2 2 1

Should it be YES, NO ?

Yes, it should be YES, NO.

i was able to see someone's solution for D. handle is sn23581. I think many of coders have seen solutions. As codeforces allowed to see. You can check the log.

I think , the contest should be unrated, or make it unrated for me or other who have seen other's code.

same to me

Jun 23, 2013 7:01:33 PM Announcement General announcement ***** The round is extended for 10 minutes.

Announcement came after the contest ended.

I think this Contest should canceled I saw solutions of some contests before time extention i saw fog solution in C he use array called deg & his solution contain one loop only i just talk about this to ensure that some contests show solutions during this small period of time before you extend time Thanks

Actually, I do not understand why contest is extended, because a lot of coders saw other participants solutions, so they can send them now.

I think the best solution is to make contest unrated or delete submissions and challenges after 01:59.

Agree to delete hacks and submissions after 01:59.

agree!! with the second

I think no one can see others' solution until judging is started.

No, please don't make the contest unrated. Not again :( There were too many unrated rounds in the last period. Also, as I can see, no other solutions for problem D were submitted after the contest was extended, so I don't see any problems (even if some people saw the source code, as long as no submissions were made, I think it's ok).

I think that cancelling the submissions made after the contest ended (01:59) would be the best solution. Also, please tell us as soon as a decision is taken.

you speak in your case , not generally , in Div2 i saw Problem "C" solution so if i submit it and gain points and my rate increased you don't mind about this ?

I just said that the submissions/hacks should be ignored. I don't see any problem in that case.

But what about those who cannot submit the solution in last minutes of the contest?

It is the same for everybody. I don't think that the contest should be unrated just because it was 2 minutes shorter.

Why do you insist so much, perhaps because you solved just one task? :P I would like to see if your reaction would've been the same with you having 3 tasks solved.

I am so silly that I thought I could AC pE.

After I got WA for long time, I found out that I didn't clearly understand the porblem... so sad.

for the case: I1 (0,5) and I2 (2,3), query I1 I2 is NO, query I2 I1 is YES..

I can open the code of others in the first minute after contest. But I do not know the contest is still running, because the announcement is not shown in the standing page. :(

I think it's possible to make this round rated by ignoring all submissions or hacks after extending;if the system can do it!

But the contest was extended, because there were problems with server in the end of the contest and while someone was not able to submit his solution in last 5 minutes in contest it would be unfair for them.

That makes sense. Now I'm wondering how many (cheating) solutions are there... I hope they're few and it's rated...

I'm not telling those are cheater, but I was 33rd and when the contest was extended I finished 44th so 11 coders needed that time...

It would be unfair to leave this situation as it is now, because a lot of people left their computers immediately after the end of contest.

and only 50 solutions which passed pretests sent on this interval

hope this contest will not be unrated !!!

I gauss it will be unrated because of the extra time.

to solve div2 E /div1 C :

the key is to use B[n]=0 advantage so the problem is reduced to:

what is the minimum cost to completely cut the n'th tree

let's reverse the trees (also A and B arrays)

dp[i] means minimum cost to cut tree 1 (which was n before reversing) using only trees from 1 to i assuming A[i]=1

we have:

dp[i]=min for all j<i(dp[j]+B[i]*A[j]);

using convex hull trick we have O(n) solution.

but I had very bad luck getting WA on test 3 :(

please help me 3950250

Sorry, mixed with div2 CI think you have integer overflow in

`bad`

functionlong long overflow in bool bad(int a,int b,int c)

slycelote and Sammarize

thanks, but how to avoid this? should I use some big integers or there's easier way?

look at this: 3948609.

But, most competitors have used double.

thanks.

I don't have an overflow but its still giving WA on test 3. What's wrong? 3952143

No, you have. Here it is: "(DP[q[t-1]]-DP[i])*(a[q[t]]-a[q[t-1]])".

DP and a are arrays of long long type. Shouldn't overflow?

Yes, and long long is overflowing.

DP[i] ≤ 10^{18}anda[i] ≤ 10^{9}.OH. Right. Thank you!

I think I understand your idea. would you explain more about your code? what do the add & query functions do?

it's convex hull trick , function "add" adds a new line query searchs for best line

see this link: http://wcipeg.com/wiki/Convex_hull_trick

Can you please describe this convex hull trick in your own words.I would be pretty thankful if you do.

My english is poor so my words will be worse , however I think this article is very good I learnt this trick from it. if there's something you can't understand you may ask me to explain it for you

FFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

Writers, thank for the contest ;-)

Except the dance club which I didn't understand, the problems were really nice ;-)

About

`Psychos in a Line`

Div1B/Div2DHow to pass a case like follow:

My solution will get

`Time limit exceeded`

on this case.One can use generator for this ;-)

edit: I misunderstood the first version of your question. I thought you are asking how to use it for hacks. Now I cannot remove my comment...

Put i in a queue(kill list) if a[i] > a[next[i]] and i is not dead, then go through the queue and start killing people and update the next[i], you might need to use 2 queues to do this.

In your tes case, there is only 1 number in the queue every time, so O(n).

Store a list for psychos, who will be killed. And in each turn recreate this list by the previous list(it is possible, because in next turn only those psychos can be killed, who was next after psycho from previous list(who were killed in previous turn))

A very interesting contest :)

How did you find out the solution for Div1A without using backtrack for small n values? I still don't get why the answer is correct.

Upd:the solution isx·2^{n - 1}. It's not obvious why all these solutions give the same result.if a > b and a^x < b^x, it is mean that "^x" operation is chenge first different digit in a and b.

If bit i is 1, then A0B > A1C (A contains i — 1 bits, B and C contain n — i bits).

If the first bit of

xis 1, we swap two halves of array, that gives us 2^{n - 1}× 2^{n - 1}inversions. Thei-th bit gives inversions in the same way, but we swap halves of 2^{i}arrays sized 2^{n - i}, for 2^{2n - i}inversions. Clear to see every bit is independent from the others.why?(but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions)

For instance

n= 4. Arrays for differenti's look like this:i= 0:i= 1:i= 2:i= 3:Easy to see the pattern here.

thanks！

I wrote down all the numbers in binary when n = 3 and x = 111, instantly I found the beauty of the answer:)

The least significant bit affects each pair of subsequent numbers ((0)-(1), (2)-(3), (4)-(5), etc): if LSB of x is 1, then we count each pair (2^(n-1) at all), else we don't.

Next bit affects pairs of subsequent groups of 2 numbers ((0,1)-(2,3); (4,5)-(6,7), etc), each pair of groups adds 2 * 2 pairs.

And so on: i-th bit affects pairs of subsequent groups of 2^i numbers.

I just solved a simple case by hand:

dp[i] — number of bad pairs in set with (2^i) numbers

dp[i] = (s[i] = 1)·(2^{2i}) + 2·dp[i- 1]so if x[i]==1 must inverse bit, and if x[i] == 0 the bit will not change.

eg.

I randomly guessed ans+=2^(i+length(n)-2) for '1' in ith digit.

Sorry about unfortunate contest ending. We will investigate accounts who saw the other's solutions and accepted code after it. It doesn't look like there are many such participants.

No matter whether this contest will be rated or not, plz start system test first. Many people are waiting for the result anxiously。

Why chinese have different dots(.) ? Before, I saw some chinese writing (?)(.) and some others characters differently. Can you please tell me the reason of this ?

because chinese words and english words are two different systems.

besides, are you talking 全形碼 。？， <--?

If I understood you correctly ("are you talking about 全形碼 。？"), YES I am talking "？". :)

Chinese is double-byte-character-set, check wiki DBCS, so we Chinese makes everything double bytes. like 。。。，，，！！！？？？Even this: Ｈｅｌｌｏ Ｗｏｒｌｄ.

check this and this

really, can you do it after systest? It is rather more interesting for most copetitors.

What about people who left their computers immediately after finish of the contest?

Life goes on. :D

I wrote a lot of scripts and found that no more than 8 persons from both divisions tried to see other's solutions and passed system tests after it. So I don't see any reason to make it unrated for all. Sorry again about the issue.

I think that it's quite unfair to distinguish those participants who have accepted their solutions after viewing the other's code and those who haven't viewed code in "intermission" but have also got accepted verdict. The reason is that one cannot be sure that they won't be able to get accepted without viewing the other's code. So, to my mind, they shouldn't suffer from the fact that they have viewed it.

P.S. I don't refer to any of above-mentioned groups.

What is the Test 5 in B DIV2? I send an O (n ^ 3) and I have TLE, with n = 100??

Mine is O(n^3.5) ans passed in in 15ms, so you are the one slowing down the system test...

I think that a solution in O(N^4) should pass because 10^8 can pass in two seconds, indeed my solution is O(N^4)

Thanks for interesting problems!

I think have an unique DP method to the problem A div1. 3951181

I don't know if ther is other people use this method...

Actually many people use this, such as myself...3944678

check tunyash comment: comment

orz

It seems many competitor passed Problem D by simple brute force.

I wonder if it is the expected right solution or the test cases are weak?

It's third or fourth contest, that contains the problem, which has

n≤ 50000 orn≤ 100000, and you have to solve using simple straightforward algorithm, and optimize it.I don't know if it's good or bad, but all thinking skills you have to use when solving the problem are useless here, you just have to optimize it well.

And you have also to notice that the TL is large enough :( I didn't see it in time and wasted plenty of time thinking over a fast solution.

Yes, 6 seconds tell you: "man, O(n^2) should be the right solution".

well,but how can that worth 2500 points...

Only seven participants solved the problem. It's fair enough.

:) well, I have the same question.

By the way, I guess that there is solution. I'm not sure, but I guess, that you can find the shortest tandem repeat in the string like the algorithm for the longest one, and then remove all tandem repeats using linear algorithm. There will be such tandem repeat lengths.

I have c*n^2 + n^1.5 but c is small enough (4 seconds). But it's not a simple bruteforce.)

The actual solution has time complexity

O(nsqrt(n)log(n)) and we didn't expect bruteforce solutions to pass the tests. Actually we're not ok with what happened! :(And what is the work time of this solution? I guess, it's not much faster, than bruteforce.

Yep :)

The runtime of our solution is about 3 seconds.

Hi, actually I think I have a O(n^1.5+nlg^2n) solution. The nlg^n part took me too long to think of during the contest, so I was not able to finish it during contest time. The latter part requires hash, though.

The idea is that:

Note that we can implement a function

`cut(d)`

that given a length d, cut according the rule all XX s.t. length(X)=d. This should not be too hard so I'll skip the detail. The time required is O(n).Suppose you have a oracle function

`foretell(d)`

, that could tell you (ignore how for the time begin) in a fast enough time, whether there exists X | length(X)=d s.t. XX is in S. Once you have this, the rest is simple. Because if we only call`cut(d)`

on d | foretell(d)=true, then there will be at most O(n^0.5) calls.So the question remain: how fast can

`foretell(d)`

be? I came up with an overall O(n/d*lgd) one, and I think there may be better solution. Anyway my version is: For each d, partition the (current) S into segments where each except possibly the last is of length d. Then for each endpoint x of segments, we record two things:These could be obtained by binary search + hash (hmm..), and we just need to check whether there is x s.t. left_extend[x]+right_extend[x]>=d.

The overall runtime is clearly O(n^1.5+nlg^n), and could pass systest in a mere 109ms. I wonder if there is something better (in runtime / don't require hash .. etc) in the latter part though. Anticipating for great opinions.

After each change of the string

S(and the beginning), build suffix array ofS. By the properties, we only build the suffix array times.Then right_extend[x] can be calculated in

O(1) by finding the LCP (RMQ) ofsuffix(x) andsuffix(x+d).left_extend[x] can be calculated similarly using suffix array of

reverse(S).Good point and thanks!!

Now we really have a totally reasonable solution (and without hash!) that could run well below the time limit.

Has it been made official whether or not this contest will be rated?

Disclaimer: rather angry and loud comment follows.WHY THE HELL?Good problems, great social platform, but still going down during rounds. What's the problem? Slow code? You're programmers, optimize it! You cannot, because you need 'readable' code? Damn it, the website doesn't work during rounds, who cares about program's code if it doesn't work?

Too much users? Set limit of participants, like TopCoder do. At least rounds will be reasonably rated.

Not enough servers? VK offered you, not even once. If your code is good, it should be easy to scale on 10 servers.

Please, stop being prideful and make Codeforces a stable system!

285! The CodeForces community can't be undrstood:)

Is the contest unrated?

I think no. ;-)

my dfs solution for problem B div 2 failed on test 5 because I didn't pass the visited vector by reference to the dfs function :(

is this something to be expected?

There should be

`vector <bool> &visited`

in the runDFS declaration:3951797

Otherwise, it just creates a copy of your vivsited array for every function call, which means u get additioncal O(visited size * times RunDFS is called).

What was the point of restricting Div2 B (ping pong easy) problem with increasing segment lengths?

Did we have to use that in the optimal solution?

I think, it's important for "ping pong hard" problem from Div1. Statements are the same except n's range.

It can be promise that the interval you add in the future would not be full covered by the interval you had added.

So you only have to consider what intervals it can conneceted. And the interval you connected can go to each other... (it should be a<c<b<d, not a<c<d<b)

Will someone give some hints/explanation for Div 2 D (psychos in a line)? Thanks!

I took pen and paper and for each psychos wrote down when he will be killed and in which step. Do it and you will understand what to do. Another hint is you may need segment tree.

I completed it without tree with O(n) and without turn simulation.

I set their targets onto the next psycho and then let right ones kill as long as they can, taking targets of their victims to skip dead. As kills are made every turn, maximum number of kills is answer. The only problem was that already dead psychos kept killing but I solved that with giving those kills to their killers as they would grab them later anyways. Targets can be changed only N times(after kills).

How can one use a segment tree here?

Consider the initial line of all psychos. Let us choose the psycho that has the highest ID number. Now you can divide the initial task in two parts: (a) solve the task for the line of psychos to the left of the psycho with the highest ID (excluding him); (b) solve the task for the line of psychos to the right of the psycho with the highest ID (including him).

The answer to the initial task will be the maximum from the answers to sub-tasks (a) and (b).

In order to solve sub-tasks like (a) and (b) you can keep recursively dividing any (sub)line of psychos in two parts, around the psycho with the highest ID in this line. For the purpose of finding such psycho every time you can use a segment tree.

find_max()by a segment tree?

Please, help me understand, I think I didn't get well the problem. In the problem B of DIV2, test case #4:

How does the last '2' query return "NO"?

The segments 9 and 6 (highlighted) are overlapping.

Thanks!

You can't move from an interval to an interval that contains it.

Thank you, srnth! I just changed that and now my solution is accepted :)

An editorial, plz!

I hope the editorial is good,detailed and understandable

can anyone help me to solve Problem B (Div 1) or Problem D (Div 2). Thanks in advance :)

On each step you must check for abilitiy of kill only for people who kill on the previous step, and then remove killed people. Each man or kill someone or go away from list of killers. Total amount of murders is O(n) and total amount of cases when man go away from killers list is O(n) too.

suppose the test data was-

5 4 3 2 1 22 20 10 15 14. So after first step the array became-

5 22 15 . And after second step the array became

5 22.

Now how to solve this in O(n). Please explain by taking it as example.

I looked at your AC code here, http://codeforces.com/contest/319/submission/3944800 and your logic made sense. However, I am confused as to why you didn't get TLE on the test case below. A test case that will cause this to be O(n^2) will be 100000 100000 99999 99998 ...

Unless I violated/misread the problem statement.. was the provided test case too weak?

[EDIT] here is a sample test case. I copied the exact same code, but replaced the input with pregenerated test case: http://pastebin.com/PJPaK7Da

In this case, everyone will die in the first round itself. It's still O(n). The complexity is the sum of (no. of people who killed someone in the round) over all rounds. To be part of a given round, a person must have killed in the previous round. As the number of killing victims cannot exceed n, the number of killers(counting people who killed twice, twice etc.) cannot exceed n.

Hence, the complexity is linear. EDIT: In my implementation, it took log(n) time to find the right neighbour of a person. Hence, the complexity would be O(nlogn)

I agree. That's why I upvoted his comment for the same observation you mentioned. However, his implementation for killing (unfortunately) causes it to be O(n^2), which you can try by using the sample test I provided. You can see line 26-28 of http://pastebin.com/PJPaK7Da

my idea: observe that only elements i with a[i]>a[i-1] will not be chopped down in step 1. others will be chopped down instantly

maintain a linked list X

run the array once from n to 1 (reverse order)

assume initial answer to be 0

if (a[i]<a[i-1]) and i!=1 then answer will be max(answer,1) as at least one step will be taken

otherwise insert the element to the head of X. To know how many steps he will go on, we try to make the inserted element to chop down the new elements.

Assume ans2=0 be the moment which the inserted element cannot kill anyone anymrore, On each next element that is smaller than the inserted element, the inserted element can surely chop down it, and ans2=max(the number of steps the previous element need i.e. the previous ans2,max(ans2,1)+1), ans=max(ans2,ans) return ans at last.

For the test case,

note that the process runs from bottom to top

refer to my code 3950756 if you cannot understand my poor english :(

I found these two youtube videos really helpful for problem Div 1 E: Seth MacFarlane Take a look and here is another video And this one !

Editorial please

Hello. Participate in progressive competition in the Caribbean Online Judge! This is the link for more information: http://coj.uci.cu/contest/contestview.xhtml?cid=1301