Codeforces Round #189

11 years ago, # |

+13

I'm sorry, but what was popped out?

→ Reply

chaotic_iak

11 years ago, # ^ |

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)

→ Reply

latvian

11 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Mostafa.Gabriel

11 years ago, # ^ |

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

→ Reply

teleport

11 years ago, # |

-36

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

→ Reply

Joker_Poker

11 years ago, # |

-11

The comment removed because of Codeforces rules violation

→ Reply

latvian

11 years ago, # |

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

→ Reply

11 years ago, # |

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

→ Reply

pauldb

11 years ago, # |

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

→ Reply

11 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Petr

11 years ago, # ^ |

+15

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

→ Reply

11 years ago, # ^ |

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 ?

→ Reply

Petr

11 years ago, # ^ |

Yes, it should be YES, NO.

→ Reply

faiyaz26

11 years ago, # |

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.

→ Reply

Killever

11 years ago, # ^ |

same to me

→ Reply

jehad131

11 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.

→ Reply

Killever

11 years ago, # |

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

→ Reply

agul

11 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.

→ Reply

NiVeR

11 years ago, # ^ |

Agree to delete hacks and submissions after 01:59.

→ Reply

Son-Goku

11 years ago, # ^ |

agree!! with the second

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # |

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

→ Reply

11 years ago, # ^ |

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.

→ Reply

Killever

11 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 ?

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

NiVeR

11 years ago, # ^ |

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.

→ Reply

11 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..

→ Reply

wanbo

11 years ago, # |

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. :(

→ Reply

hogloid

11 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!

→ Reply

11 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.

→ Reply

hogloid

11 years ago, # ^ |

← Rev. 3 →

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

→ Reply

11 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...

→ Reply

sasha.sochka

11 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.

→ Reply

aaaaaaaaaaaaaaaaaaaaaaab

11 years ago, # ^ |

← Rev. 2 →

and only 50 solutions which passed pretests sent on this interval

→ Reply

AU.Bahosain

11 years ago, # |

+21

hope this contest will not be unrated !!!

→ Reply

niike0goood

11 years ago, # ^ |

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

→ Reply

11 years ago, # |

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

→ Reply

aaaaaaaaaaaaaaaaaaaaaaab

11 years ago, # ^ |

← Rev. 2 →

Sorry, mixed with div2 C

→ Reply

slycelote

11 years ago, # ^ |

I think you have integer overflow in bad function

→ Reply

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

slycelote and Sammarize

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

→ Reply

11 years ago, # ^ |

look at this: 3948609.
But, most competitors have used double.

→ Reply

11 years ago, # ^ |

thanks.

→ Reply

akshatb

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

akshatb

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

Yes, and long long is overflowing. DP[i] ≤ 10¹⁸ and a[i] ≤ 10⁹.

→ Reply

akshatb

11 years ago, # ^ |

OH. Right. Thank you!

→ Reply

mosiomohsen

11 years ago, # ^ |

← Rev. 2 →

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

→ Reply

11 years ago, # ^ |

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

→ Reply

Rubanenko

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

Neodym

11 years ago, # |

← Rev. 2 →

-54

FFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

→ Reply

11 years ago, # |

Writers, thank for the contest ;-)

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

→ Reply

kphmd

11 years ago, # |

← Rev. 3 →

About Psychos in a Line Div1B/Div2D

How to pass a case like follow:

100000
100000 1 2 ... 99997 99999 99998

My solution will get Time limit exceeded on this case.

→ Reply

11 years ago, # ^ |

← Rev. 2 →

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...

→ Reply

11 years ago, # ^ |

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

→ Reply

PolarNick

11 years ago, # ^ |

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

→ Reply

p-space

11 years ago, # |

← Rev. 2 →

A very interesting contest :)

→ Reply

ifsmirnov

11 years ago, # |

← Rev. 2 →

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·2^n - 1. It's not obvious why all these solutions give the same result.

→ Reply

11 years ago, # ^ |

if a > b and a^x < b^x, it is mean that "^x" operation is chenge first different digit in a and b.

→ Reply

flashmt

11 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Endagorion

11 years ago, # ^ |

If the first bit of x is 1, we swap two halves of array, that gives us 2^n - 1 × 2^n - 1 inversions. The i-th bit gives inversions in the same way, but we swap halves of 2ⁱ arrays sized 2^n - i, for 2^2n - i inversions. Clear to see every bit is independent from the others.

→ Reply

HaibaraAi

11 years ago, # ^ |

← Rev. 2 →

why?(but we swap halves of 2i arrays sized 2n - i, for 22n - i inversions)

→ Reply

Endagorion

11 years ago, # ^ |

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.

→ Reply

HaibaraAi

11 years ago, # ^ |

thanks！

→ Reply

11 years ago, # ^ |

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

→ Reply

naagi

11 years ago, # ^ |

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.

→ Reply

Gassa

11 years ago, # ^ |

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)

→ Reply

tunyash

11 years ago, # ^ |

← Rev. 3 →

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

dp[i] = (s[i] = 1)·(2²ⁱ) + 2·dp[i - 1]

→ Reply

kphmd

11 years ago, # ^ |

← Rev. 2 →

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

→ Reply

11 years ago, # ^ |

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

→ Reply

MikeMirzayanov

11 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.

→ Reply

kAc

11 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。

→ Reply

accidentallygivenfuck

11 years ago, # ^ |

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 ?

→ Reply

11 years ago, # ^ |

because chinese words and english words are two different systems.

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

→ Reply

accidentallygivenfuck

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

hime

11 years ago, # ^ |

check this and this

→ Reply

11 years ago, # ^ |

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

→ Reply

sasha.sochka

11 years ago, # ^ |

← Rev. 2 →

+24

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

→ Reply

NiVeR

11 years ago, # ^ |

Life goes on. :D

→ Reply

MikeMirzayanov

11 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.

→ Reply

Malinovsky239

11 years ago, # ^ |

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.

→ Reply

Boxer

11 years ago, # |

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

→ Reply

11 years ago, # ^ |

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

→ Reply

p-space

11 years ago, # ^ |

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)

→ Reply

redjohn

11 years ago, # |

Thanks for interesting problems!

→ Reply

gagaga5-gagaga

11 years ago, # |

-7

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...

→ Reply

shigule

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

check tunyash comment: comment

→ Reply

gagaga5-gagaga

11 years ago, # ^ |

-9

orz

→ Reply

YuukaKazami

11 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?

→ Reply

niyaznigmatul

11 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 $\text{[math]}$ 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.

→ Reply

ifsmirnov

11 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

11 years ago, # ^ |

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

→ Reply

YuukaKazami

11 years ago, # ^ |

+26

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

→ Reply

11 years ago, # ^ |

-15

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

→ Reply

niyaznigmatul

11 years ago, # ^ |

:) well, I have the same question.

By the way, I guess that there is $\text{[math]}$ 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 $\text{[math]}$ such tandem repeat lengths.

→ Reply

11 years ago, # ^ |

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

→ Reply

havaliza

11 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! :(

→ Reply

11 years ago, # ^ |

And what is the work time of this solution? I guess, it's not much faster, than bruteforce.

→ Reply

havaliza

11 years ago, # ^ |

Yep :)

The runtime of our solution is about 3 seconds.

→ Reply

kelvin

11 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.

→ Reply

SteamTurbine

11 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 $\text{[math]}$ 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).

→ Reply

kelvin

11 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.

→ Reply

kullalok

11 years ago, # |

+23

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

→ Reply

yeputons

11 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!

→ Reply

NegaTeeF

11 years ago, # ^ |

-40

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

→ Reply

hasib

11 years ago, # |

-29

Is the contest unrated?

→ Reply

dario-dsa

11 years ago, # ^ |

-7

I think no. ;-)

→ Reply

kmamp

11 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?

→ Reply

ONU_1785

11 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Dixtosa

11 years ago, # |

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?

→ Reply

Lelby

11 years ago, # ^ |

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

→ Reply

11 years ago, # ^ |

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)

→ Reply

PeterGriffin

11 years ago, # |

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

→ Reply

Shafaet

11 years ago, # ^ |

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.

→ Reply

lightstone

11 years ago, # ^ |

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

→ Reply

ONU_1785

11 years ago, # ^ |

How can one use a segment tree here?

→ Reply

IgorS

11 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

HaibaraAi

11 years ago, # ^ |

find_max()by a segment tree?

→ Reply

martinezgjuan

11 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!

→ Reply

srnth

11 years ago, # ^ |

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

→ Reply

martinezgjuan

11 years ago, # ^ |

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

→ Reply

NegaTeeF

11 years ago, # |

+20

An editorial, plz!

→ Reply

11 years ago, # |

I hope the editorial is good,detailed and understandable

→ Reply

red_coder

11 years ago, # |

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

→ Reply

11 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.

→ Reply

red_coder

11 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 became

5 22.

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

→ Reply

xenoslash

11 years ago, # ^ |

← Rev. 2 →

+14

I looked at your AC code here, http://codeforces.net/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

→ Reply

kira

11 years ago, # ^ |

← Rev. 3 →

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)

→ Reply

xenoslash

11 years ago, # ^ |

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

→ Reply