havaliza's blog

By havaliza, 10 years ago,

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

• +304

| Write comment?
 » 10 years ago, # |   +22 Good time for Chinese!
 » 10 years ago, # |   +22 Nice moustache :)
•  » » 10 years ago, # ^ |   -8 like!
 » 10 years ago, # |   +11 '#198' ?
 » 10 years ago, # |   +32 Wish you 4 shiny gold medals :-) I believe the contest is going to be one of the greatest.
 » 10 years ago, # | ← Rev. 4 →   +35 Thanks to the early time because I have an exam on 24th morning. :D
 » 10 years ago, # |   +10 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...
•  » » 10 years ago, # ^ | ← Rev. 2 →   +16 The network in a train could be really instable, I have suffered several times because of this.
 » 10 years ago, # |   +31 early time is good! since there is cookoff also on codechef.
 » 10 years ago, # |   +6 Email I've just received says that round will be today (22.06.2013). A bit confusing. Is something wrong with my calendar?
 » 10 years ago, # |   -11 Change tag, it's wrong.
 » 10 years ago, # |   +3 worst time for Iran I guess. Nobody can participate :( . Everybody is in the club :D
 » 10 years ago, # |   +31 I want to see you in IOI!!
•  » » 10 years ago, # ^ |   +34 Hope to see you in IOI! ^.^
 » 10 years ago, # |   +15 This time we do both the contest codechef/cookoff and codeforces Div I/II round Really good timing :)
 » 10 years ago, # |   +19 I hope the english will be understandable this time! :)
 » 10 years ago, # |   -34 Ну вот, щас на кф ещё и систему ЕГЭ введут... а преподы из школ будут следить, чтобы мы не списывали.. :)
 » 10 years ago, # |   +13 I'm sorry, but what was popped out?
•  » » 10 years ago, # ^ |   +5 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)
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 10 years ago, # ^ |   +1 copying contestant's code to hack using any plug-in is considered cheating, but it's OK to retype it
 » 10 years ago, # |   -36 Количество зарегистрированных во втором дивизионе равно моему году рождения — надеюсь это хороший знак=)
 » 10 years ago, # |   -11 The comment removed because of Codeforces rules violation
 » 10 years ago, # |   +6 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 :(
 » 10 years ago, # |   +6 I hate those moments when I think I did well in contest and it's unrated because of server problems :-(
 » 10 years ago, # |   +8 Is pretest 2 at problem E (div 1) correct? I don't see any solution passing it.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 10 years ago, # ^ |   +15 This test is incorrect — interval lengths have to be increasing.
•  » » » » 10 years ago, # ^ |   +2 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 ?
•  » » » » » 10 years ago, # ^ |   +3 Yes, it should be YES, NO.
 » 10 years ago, # |   +9 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.
•  » » 10 years ago, # ^ |   +5 same to me
 » 10 years ago, # |   +18 Jun 23, 2013 7:01:33 PM Announcement General announcement ***** The round is extended for 10 minutes.Announcement came after the contest ended.
 » 10 years ago, # |   +2 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
 » 10 years ago, # | ← Rev. 3 →   +72 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.
•  » » 10 years ago, # ^ |   +9 Agree to delete hacks and submissions after 01:59.
•  » » 10 years ago, # ^ |   0 agree!! with the second
•  » » 10 years ago, # ^ |   0 I think no one can see others' solution until judging is started.
 » 10 years ago, # |   +7 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).
•  » » 10 years ago, # ^ |   +1 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.
•  » » 10 years ago, # ^ |   -9 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 ?
•  » » » 10 years ago, # ^ |   0 I just said that the submissions/hacks should be ignored. I don't see any problem in that case.
•  » » » » 10 years ago, # ^ |   0 But what about those who cannot submit the solution in last minutes of the contest?
•  » » » » » 10 years ago, # ^ |   0 It is the same for everybody. I don't think that the contest should be unrated just because it was 2 minutes shorter.
•  » » » 10 years ago, # ^ |   +2 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.
 » 10 years ago, # | ← Rev. 2 →   -7 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..
 » 10 years ago, # |   +9 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. :(
 » 10 years ago, # |   +14 I think it's possible to make this round rated by ignoring all submissions or hacks after extending;if the system can do it!
•  » » 10 years ago, # ^ |   +10 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.
•  » » » 10 years ago, # ^ | ← Rev. 3 →   +6 That makes sense. Now I'm wondering how many (cheating) solutions are there... I hope they're few and it's rated...
•  » » » » 10 years ago, # ^ |   +10 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...
 » 10 years ago, # |   +58 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.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 and only 50 solutions which passed pretests sent on this interval
 » 10 years ago, # |   +21 hope this contest will not be unrated !!!
•  » » 10 years ago, # ^ |   0 I gauss it will be unrated because of the extra time.
 » 10 years ago, # |   0 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 treelet'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]=1we have:dp[i]=min for all j
•  » » 10 years ago, # ^ | ← Rev. 2 →   +5 Sorry, mixed with div2 C
•  » » 10 years ago, # ^ |   0 I think you have integer overflow in bad function
•  » » 10 years ago, # ^ |   0 long long overflow in bool bad(int a,int b,int c)
•  » » » 10 years ago, # ^ |   0 thanks, but how to avoid this? should I use some big integers or there's easier way?
•  » » » » 10 years ago, # ^ |   0 look at this: 3948609. But, most competitors have used double.
•  » » » » » 10 years ago, # ^ |   0 thanks.
•  » » » » 10 years ago, # ^ |   0 I don't have an overflow but its still giving WA on test 3. What's wrong? 3952143
•  » » » » » 10 years ago, # ^ |   0 No, you have. Here it is: "(DP[q[t-1]]-DP[i])*(a[q[t]]-a[q[t-1]])".
•  » » » » » » 10 years ago, # ^ |   0 DP and a are arrays of long long type. Shouldn't overflow?
•  » » » » » » » 10 years ago, # ^ |   0 Yes, and long long is overflowing. DP[i] ≤ 1018 and a[i] ≤ 109.
•  » » » » » » » » 10 years ago, # ^ |   0 OH. Right. Thank you!
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 I think I understand your idea. would you explain more about your code? what do the add & query functions do?
•  » » » 10 years ago, # ^ |   0 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
•  » » 10 years ago, # ^ |   +2 Can you please describe this convex hull trick in your own words.I would be pretty thankful if you do.
•  » » » 10 years ago, # ^ |   +1 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
 » 10 years ago, # | ← Rev. 2 →   -54 FFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
 » 10 years ago, # |   +1 Writers, thank for the contest ;-)Except the dance club which I didn't understand, the problems were really nice ;-)
 » 10 years ago, # | ← Rev. 3 →   0 About Psychos in a Line Div1B/Div2DHow to pass a case like follow: 100000 100000 1 2 ... 99997 99999 99998 My solution will get Time limit exceeded on this case.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 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...
•  » » 10 years ago, # ^ |   +4 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).
•  » » 10 years ago, # ^ |   +3 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))
 » 10 years ago, # | ← Rev. 2 →   +1 A very interesting contest :)
 » 10 years ago, # | ← Rev. 2 →   0 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 is x·2n - 1. It's not obvious why all these solutions give the same result.
•  » » 10 years ago, # ^ |   0 if a > b and a^x < b^x, it is mean that "^x" operation is chenge first different digit in a and b.
•  » » 10 years ago, # ^ | ← Rev. 2 →   +9 If bit i is 1, then A0B > A1C (A contains i — 1 bits, B and C contain n — i bits).
•  » » 10 years ago, # ^ |   +1 If the first bit of x is 1, we swap two halves of array, that gives us 2n - 1 × 2n - 1 inversions. The i-th bit gives inversions in the same way, but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions. Clear to see every bit is independent from the others.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 why?(but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions)
•  » » » » 10 years ago, # ^ |   0 For instance n = 4. Arrays for different i's look like this:i = 0: (8 9 10 11 12 13 14 15)(0 1 2 3 4 5 6 7) i = 1: (4 5 6 7)(0 1 2 3)|(12 13 14 15)(8 9 10 11) i = 2: (2 3)(0 1)|(6 7)(4 5)|(10 11)(8 9)|(14 15)(12 13) i = 3: (1)(0)|(3)(2)|(5)(4)|(7)(6)|... Easy to see the pattern here.
•  » » » » » 10 years ago, # ^ |   0 thanks！
•  » » 10 years ago, # ^ |   0 I wrote down all the numbers in binary when n = 3 and x = 111, instantly I found the beauty of the answer:)
•  » » 10 years ago, # ^ |   0 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.
•  » » 10 years ago, # ^ |   +3 I just solved a simple case by hand: 101 000 101 001 100 010 111 011 110 100 001 101 000 110 011 111 010 1 * (4 * 4) + 2 * (0 * 0) + 4 * (1 * 1) 
•  » » 10 years ago, # ^ | ← Rev. 3 →   +3 dp[i] — number of bad pairs in set with (2^i) numbersdp[i] = (s[i] = 1)·(22i) + 2·dp[i - 1]
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 0 ^ 0 = 0 1 ^ 0 = 1  0 ^ 1 = 1 1 ^ 1 = 0 so if x[i]==1 must inverse bit, and if x[i] == 0 the bit will not change.eg. x=10 MDC NFC 00(0) 10(2) 01(1) 11(3) 10(2) 00(0) 11(3) 01(1) ans is 4 = 1*2*2  x=01 MDC NFC 00(0) 01(1) 01(1) 00(0) 10(2) 11(3) 11(3) 10(2) ans is 2 = 2*1*1  x=11 MDC NFC 00(0) 11(3) 01(1) 10(2) 10(2) 01(1) 11(3) 00(0) ans is 6 = 2*1*1 + 1*2*2 
•  » » 10 years ago, # ^ |   0 I randomly guessed ans+=2^(i+length(n)-2) for '1' in ith digit.
 » 10 years ago, # |   +72 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.
•  » » 10 years ago, # ^ |   +55 No matter whether this contest will be rated or not, plz start system test first. Many people are waiting for the result anxiously。
•  » » » 10 years ago, # ^ |   0 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 ?
•  » » » » 10 years ago, # ^ |   +4 because chinese words and english words are two different systems.besides, are you talking 全形碼　。？， <--?
•  » » » » » 10 years ago, # ^ |   +4 If I understood you correctly ("are you talking about 全形碼　。？"), YES I am talking "？". :)
•  » » » » » » 10 years ago, # ^ |   +4 Chinese is double-byte-character-set, check wiki DBCS, so we Chinese makes everything double bytes. like 。。。，，，！！！？？？Even this: Ｈｅｌｌｏ　Ｗｏｒｌｄ.
•  » » » » 10 years ago, # ^ |   +5 check this and this
•  » » 10 years ago, # ^ |   +9 really, can you do it after systest? It is rather more interesting for most copetitors.
•  » » 10 years ago, # ^ | ← Rev. 2 →   +24 What about people who left their computers immediately after finish of the contest?
•  » » » 10 years ago, # ^ |   +4 Life goes on. :D
•  » » 10 years ago, # ^ |   +10 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.
•  » » 10 years ago, # ^ |   +7 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.
 » 10 years ago, # |   0 What is the Test 5 in B DIV2? I send an O (n ^ 3) and I have TLE, with n = 100??
•  » » 10 years ago, # ^ |   +2 Mine is O(n^3.5) ans passed in in 15ms, so you are the one slowing down the system test...
•  » » 10 years ago, # ^ |   0 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)
 » 10 years ago, # |   +7 Thanks for interesting problems!
 » 10 years ago, # |   -7 I think have an unique DP method to the problem A div1. 3951181I don't know if ther is other people use this method...
•  » » 10 years ago, # ^ |   0 Actually many people use this, such as myself...3944678
•  » » 10 years ago, # ^ |   +1 check tunyash comment: comment
•  » » » 10 years ago, # ^ |   -9 orz
 » 10 years ago, # | ← Rev. 2 →   +56 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?
•  » » 10 years ago, # ^ | ← Rev. 2 →   +16 It's third or fourth contest, that contains the problem, which has n ≤ 50000 or n ≤ 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.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » 10 years ago, # ^ |   0 Yes, 6 seconds tell you: "man, O(n^2) should be the right solution".
•  » » » 10 years ago, # ^ |   +26 well,but how can that worth 2500 points...
•  » » » » 10 years ago, # ^ |   -15 Only seven participants solved the problem. It's fair enough.
•  » » » » 10 years ago, # ^ |   +8 :) 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.
•  » » 10 years ago, # ^ |   0 I have c*n^2 + n^1.5 but c is small enough (4 seconds). But it's not a simple bruteforce.)
•  » » 10 years ago, # ^ |   +18 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! :(
•  » » » 10 years ago, # ^ |   0 And what is the work time of this solution? I guess, it's not much faster, than bruteforce.
•  » » » » 10 years ago, # ^ |   +6 Yep :)The runtime of our solution is about 3 seconds.
•  » » 10 years ago, # ^ | ← Rev. 8 →   +58 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: left_extend[x] = max{l|s[x-l..x]=s[x+d-l..x+d],l<=d}; right_extend[x] = max{l|s[x..x+r]=s[x+d..x+d+r]},l<=d]; 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.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +25 After each change of the string S (and the beginning), build suffix array of S. 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) of suffix(x) and suffix(x + d). left_extend[x] can be calculated similarly using suffix array of reverse(S).
•  » » » » 10 years ago, # ^ |   +25 Good point and thanks!!Now we really have a totally reasonable solution (and without hash!) that could run well below the time limit.
 » 10 years ago, # |   +23 Has it been made official whether or not this contest will be rated?
 » 10 years ago, # | ← Rev. 2 →   +448 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!
•  » » 10 years ago, # ^ |   -40 285! The CodeForces community can't be undrstood:)
 » 10 years ago, # |   -29 Is the contest unrated?
•  » » 10 years ago, # ^ |   -7 I think no. ;-)
 » 10 years ago, # |   -23 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?
•  » » 10 years ago, # ^ | ← Rev. 3 →   +5 There should be vector &visited in the runDFS declaration:3951797Otherwise, 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).
 » 10 years ago, # |   +2 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?
•  » » 10 years ago, # ^ |   0 I think, it's important for "ping pong hard" problem from Div1. Statements are the same except n's range.
•  » » » 10 years ago, # ^ |   0 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
 » 10 years ago, # |   0 Will someone give some hints/explanation for Div 2 D (psychos in a line)? Thanks!
•  » » 10 years ago, # ^ |   0 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.
•  » » » 10 years ago, # ^ |   +1 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).
•  » » » 10 years ago, # ^ |   0 How can one use a segment tree here?
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » » 10 years ago, # ^ |   0 find_max()by a segment tree?
 » 10 years ago, # |   -7 Please, help me understand, I think I didn't get well the problem. In the problem B of DIV2, test case #4: 20 1 1208 1583 1 -258 729 1 -409 1201 1 194 1938 1 -958 1575 1 -1466 1752 2 1 2 2 1 2 2 6 5 1 -1870 1881 1 -2002 2749 1 -2002 2984 1 -2002 3293 2 2 4 2 8 10 2 9 6 1 -2002 3572 1 -2002 4175 1 -2002 4452 1 -2002 4605 How does the last '2' query return "NO"?The segments 9 and 6 (highlighted) are overlapping.Thanks!
•  » » 10 years ago, # ^ |   +3 You can't move from an interval to an interval that contains it.
•  » » » 10 years ago, # ^ |   +3 Thank you, srnth! I just changed that and now my solution is accepted :)
 » 10 years ago, # |   +20 An editorial, plz!
 » 10 years ago, # |   0 I hope the editorial is good,detailed and understandable
 » 10 years ago, # |   +8 can anyone help me to solve Problem B (Div 1) or Problem D (Div 2). Thanks in advance :)
•  » » 10 years ago, # ^ |   +21 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.
•  » » » 10 years ago, # ^ |   -7 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 became5 22.Now how to solve this in O(n). Please explain by taking it as example.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +14 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
•  » » » » 10 years ago, # ^ | ← Rev. 3 →   0 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)
•  » » » » » 10 years ago, # ^ |   0 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
•  » » 10 years ago, # ^ | ← Rev. 5 →   0 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 instantlymaintain a linked list Xrun the array once from n to 1 (reverse order)assume initial answer to be 0if (a[i]
 » 10 years ago, # |   +13 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 !
 » 10 years ago, # |   +14 Editorial please
 » 10 years ago, # |   0 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