havaliza's blog

Codeforces Round #189
By havaliza, 12 years ago, In English

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

  • Vote: I like it
  • +304
  • Vote: I do not like it

Comments Comments (156)
| Write comment?
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Good time for Chinese!

→ Reply
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nice moustache :)

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

'#198' ?

→ Reply
»
12 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +35 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Change tag, it's wrong.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I want to see you in IOI!!

→ Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I'm sorry, but what was popped out?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like 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 :(

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yes, it should be YES, NO.

          → Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

Announcement came after the contest ended.

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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
»
11 years ago, # |
← Rev. 3   Vote: I like it +72 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Agree to delete hacks and submissions after 01:59.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    agree!! with the second

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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   Vote: I like it -7 Vote: I do not like it

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
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it +6 Vote: I do not like it

      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, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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
»
11 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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
»
11 years ago, # |
  Vote: I like it +21 Vote: I do not like it

hope this contest will not be unrated !!!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
11 years ago, # |
← Rev. 2   Vote: I like it -54 Vote: I do not like it

FFFFFFFFFFFFFFFUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Writers, thank for the contest ;-)

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

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

A very interesting contest :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +4 Vote: I do not like it

        because chinese words and english words are two different systems.

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

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

            → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        check this and this

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thanks for interesting problems!

→ Reply
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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
»
11 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Yep :)

        The runtime of our solution is about 3 seconds.

        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 8   Vote: I like it +58 Vote: I do not like it

    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:

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

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

    3. 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
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +25 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        Good point and thanks!!

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

        → Reply
»
11 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +448 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -40 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Is the contest unrated?

→ Reply
»
11 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can one use a segment tree here?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +20 Vote: I do not like it

An editorial, plz!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the editorial is good,detailed and understandable

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      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
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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,

    • 5 X={5,22} ans=max(0,2)=2
    • 4 ans=max(1,2)=2
    • 3 ans=max(1,2)=2
    • 2 ans=max(1,2)=2
    • 1 ans=max(1,2)=2
    • 22 X={22,15}={22} ans=max(2,1)=2
    • 20 ans=max(1,1)=1
    • 10 ans=max(1,1)=1
    • 15 X={15} ans=max(0,1)=1
    • 14 ans=max(1,0)=1

    note that the process runs from bottom to top

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

    → Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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 !

→ Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Editorial please

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply