fchirica's blog

Codeforces Round #245
By fchirica, 11 years ago, In English

Hello everyone!

We invite you to participate in Codeforces Round #245, scheduled for Sunday, 11th May at 7:30 MSK. This is the fourth round I write for Codeforces. After the last round your upvotes helped me get into the Contributors Top 10. Thanks for all your good remarks; I'll try and do my best in order for this round to be at least as good as the previous one.

This round is prepared by my friend Ioan Petcu (author of D1 E) and I (all problems, except D1 E). We've chosen the problems to be as diverse as possible — no two problems will share the same programming technique. As the problems are varied, we hope you'll find at least one problem of your taste. The main character is Iahub, currently the number one ranked contestant in the Romanian selection camps for IOI. After reading the problem statements, you'll see what the life of a very good Romanian competitive programmer is like (just kidding, it's just my evil imagination).

This round wouldn't have been possible without the people that helped me test it: Gerald Agapov (Gerald), Damian Straszak (DamianS), Dan Alexandru (DanAlex) and Vlad Badelita (vladb). As always, we’d like to thank Mike Mirzayanov for creating the Polygon system and Codeforces plaftorm and to Delinur for translating the problems in Russian.

We wish high ratings to everyone and, above all, have fun!

UPD Score Distribution

Division 1: 500 1000 1500 2000 2000

Division 2: 500 1000 1500 2000 2500

I apologize for all technical issues during the round, from the ambiguous problem statements to very easy problem D1 D. In my trial to invent a nice task, I didn't see that straight forward solution for it and I have no excuse for this.

UPD Winners

Division 1:

  1. SergeyRogulenko
  2. scott_wu
  3. vepifanov
  4. YuukaKazami
  5. ballon

Division 2:

  1. clavichord93
  2. krmunn481
  3. Dgleich
  4. PopovkinAndrey
  5. roben_76

UPD Editorial

UPD Statistics

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

Comments Comments (181)
| Write comment?
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants.

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

Good to see another Romanian made round. And it's even 1/3 Mures (my home region)

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

Thanks for the contest! Long time no see:) And tonight I' ll try my best to reach purple( well, not pupil) God bless me:p UPD: I' m so surprised to realize that tomorrow is my birthday too, what a coincidence!

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

A contest after 9 days. :) GL HF!!

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

We really expect to see what the life of a very good Romanian competitive programmer is like :)

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

I think the problem statements about programmer will be very different && interesting. May be 's counting girlfriends, scheduling for date with girls or some games with girls... haha, just kidding.

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

Im bored

Why there arent so much comment?

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

A rare occasion: the points' distribution appeared more than 1 minute before the contest :D

And yet another: there are exactly 1000 registrants in div1!

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

It seems E question will be easy

I dont want to be first again man

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

Div 1 начало в 19:40
Div 2 начало в 19:30

UPD. исправили

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

As usual, delayed :D

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

    why the 10 minutes delay?

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

      Because I had to do my dinner.

      Although it was not official, still thanks for consideration Codeforces.

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

        And I needed some time to wash off the sand, running back from the beach :)

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

      I think, server is busy.

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

Delayed?

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

Delayed :(

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

Good start!

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

delay delay delay

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

I think the "usual time of CF Round" should be 7:40 instead of 7:30

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

    Then all of the contests start at 7:50 :D

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

      If so, I think the "usual time of CF Round" should be 7:50 instead of 7:40

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

        Then all of the contests start at 8:00 :D

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

    Just a few recent contest.

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

Another time... 10 minutes delayed...

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

For me it showed that it has started.

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

Looks like somebody important rang and said he was late to register.

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

Exacly 1000 participants in div1 :O

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

    Wow, at the same second! :D

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

      What, 999?! I thought it was final..?

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

Exactly 1000 div1 registrants! :D

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

    It shows 999 to me.

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

    now it is 999 registrants in div1...... I think someone cancel it....

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

1000 coders for div1 !!!! what an amazing contest~!!!! thanks for the delay!

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

Exactly 1000 people registered for div1.

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

exactly exactly exactly

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

It's contest? :)

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

    I don't know

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

    "As the problems are varied, we hope you'll find at least one problem of your taste."- are you kidding, fchirica?

    leaving contest arena, this contest is not for me. :(

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

Is Div.2 really Div.2...?

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

I dont understand the problem A div2. Who are the red and blue balls??. I am crazy with this problem. Please, for the next competitions that you should better the content of problem. Now, I see the clarifications of problem A, is very late and I lost many points, WDF!!!!

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

Wrong answer on pretest 2

Wrong answer on pretest 2

Wrong answer on pretest 2 . . .

:|:|:|

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

What is the solution for problem A Div.2??? A is the hardest problem today:)

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

What the heck is A? Could not come up with any idea :-s

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

    0101010101 And sort them by id afterwards

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

      why can't we use all balls of the same color?

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

        Because for example if interval is 1..3, and balls are at 1,2,3 and all of them are black, and no red, then inequality |3-0|<=1 is incorrect.

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

          thanks, I misunderstood the task, I thought ri, bi are coordinates of the balls (facepalm)

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

            So I was not the only one to think on the same lines :)

            Though I made the correction but could not get an AC because of the sort thing.

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

I think D should've been B. (div1) Or A. Ok, not A, but it's seriously easy to solve. I saw several solutions that made use of the fact that |A[i]| ≤ 104 — solutions, which pass maxtests (easy to make here) in slightly under 2 seconds.

Really? >_>

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

    Really :(

    Unfortunatelly, I've tested this approach during challenges only — it passes in 1.3s in my implementation.

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

      I rewrote LLI_E_P_JI_O_K's 6595981, ran it on "40000 40000x10000" and got 686 ms using the CF Custom invocation. On my computer, it takes 1200 ms on that test and 3200 ms on "100000 100000x10000", so it should be 1830 ms on CF, +- something in the order of 10 ms.

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

      Unbelievable if O(N*max(A)) solutions could be passed systest.

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

    At the beginning, I was expecting it might be something related to dp convex hull (yeah, it's problem D) and tried to play around with the formula to solve it. And you probably know how it feels when I finally got the solution...

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

    Really sorry for that. Didn't notice such a solution. =(

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

      Why have O(nlogn) solutions timed out?

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

        Right O(n * logn) solutions haven't timed out ;)

        I mean that as someone has already noticed it's easy to make a mistake in this algorithm in this problem by writing somewhere dist2 instead of dist or vice versa.

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

    Even if we suppose that simple solutions (such as O(N|A|max) solution with some heuristics) doesn't work, I think D was too well-known for a D. It was just the classic closest pair of points problem. Some participants might have copied the implementation of this problem and submitted..

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

I try to hacking a submission when the countdown show 15sec, then when the hacking is running contest going to be ended, what happen with my hacking? It show "Status: challenge-other"

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

Why doesnt this work for A?

If we alternate the points 0 1 0 1 0 1 then no segments can have the difference more than 1.

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

    That's right. Sort them by id(input order) then

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

    A / Div. 2 sucks.

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

      Looks very hard for A, knowing that the same problem was used for Div1-E just with a little restriction change.

      Edit: My excuses, the problem is actually different, I misunderstood.

      → Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it -27 Vote: I do not like it

Nice contest, A was an exemplary A problem, not too hard, not too easy. Speaking about B, things change, a little bit hardcore to implement, otherwise a classical DP problem. C was way easier than D (look at the number of submitted codes for C, it's pretty low). C probably is some backtracking and for D I'm really curious about the solution. At E I smell an idea similar to http://acm.timus.ru/problem.aspx?space=1&num=1129, but much more elaborated. Clearly, the score distribution was a little bit wrong. Hope my rating won't decrease by too much. Overall, I liked this contest a lot. This should be taken as constructive criticism. Everybody makes mistakes. ;)

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

Couldn't understand problem A (Div. 2). I think an example would have been great in the problem statement...

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

    Look at this from left to right, in case you print 1 0 1: 0 1 1 so segment [2,3] will have |2 — 0| = 0, which violates.

    So, the problem is just with the problem text. If he had taken the time to write it properly, there wouldn't have been so many WAs for such a trivial problem.

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

Thank you Chirica!
Really nice poblemset ;)
I just needed 2 more minutes to submit C :(

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

System test!!!!!!!!!!!!!!!!

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

(Piccy.info - Free Image Hosting)

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

    Translation please. Thanks.

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

      How fast have you submitted the A problem?

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

        Just that three words means this long sentence?? Russian language!!

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

          Not really unexpected, considering Slavic languages have something called conjugation and declension (note that I just googled the english words :D).

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

          It's just one example... If you compare the today's problem statements, the Russian versions are longer than English, less words, but more characters and syllables.

          In Hungarian, "I love you" is one word, 'szeretlek', but its length in syllables (3) is same as in English. Does that really makes Hungarian more concise than English?

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

      "Did you solve the first one quickly"?

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

на чем у всех падает div1 B? на том, что не учли, что они не могут встретится в 1 или последней строчке и в 1 или последнем столбце?

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

spent over thirty minutes finding a test case that gives  - 1 on problem A Div 2. Gave up and submitted and it got accepted. I guess there was no such test case.

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

    Is there any such test case? Please mention it.

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

    There's no such case. If you color the points 01010..01, any interval will end up with the same quantity of 0s and 1s (size of interval is even) or |#0 — #1| == 1 (size of interval is odd).

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

Just adjacent xs and ys enough for D. Such a tests...

Take look to this.6597823

I think tester should explain this.

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

WA7 в D на решении с перебором

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

    I also had WA7; now I fixed it, and now I have WA8

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

Why the test cases hasn't been visible yet?

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

How do I check on which test case my submission is failing? Once I click the solution link, its showing test case number "Runtime error on test 34" but not the test case.

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

    Click the solution number, and click the "#" sign above, and you'll get this: 6595417

    UPD: Sorry, it used to be there. I don't know where it is now.

    UPD2: It is shown now.

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

the tests for problem D are very weak

6592992 should get WA with this test case n = 1003

501 elements with value 10000 , 1 element with value 5000, 500 elements with value -10000, 1 element with value -5000

(my generator code : http://paste.ubuntu.com/7448665/ )

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

Unfortunately, the announcement for problem B modified what was asked in the original statement. Instead of requiring that the two characters meet at a single cell, their paths should have only a common cell after the clarification, which is a stronger requirement (since their speed may be different).

This was surely troublesome for those who started the contest with problem B (like me)...

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

    After the contest, xhae had told me that the following paths are feasible to the problem description, but not to what the problem author requires.

    A: [1,1] -> [1,2] -> [2,2] -> [2,3] -> [3,3]

    B: [3,1] -> [3,2] -> [2,2] -> [1,2] -> [1,1] (edited, Thanks to marspeople! It was previously [2,3] instead of [3,2])

    (spent exactly same time on all cells)

    In this case, they only meet in [2,2], but this was not included in the solution (since the intersection of both paths is {[2,2], [1,2]}). The problem description is not clear enough. actually wrong.

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

      I think you meant B: [3,1] -> [3,2] ...

      Yes, the problem becomes totally different with the added clarification

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

What are tests 18 and 14 in Div1.D? I have two solutions (6592810 and 6597945) and they both got TLE on corresponding tests, while running the latter on the 'Custom run' page shows me stable 900ms running time.

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

    I think in the following line the difference should be squared:

    if (p1 >= 0 && pts[i].proj — pts[p1].proj < ans — eps) {

    I had a TL18 with a similar bug.

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

      Thank you, that's definitely a bug.

      However, I'm still wondering about the latter submission (and that's my main concern), which was tested via 'Custom run' on several test cases and still got TLE. Do you have any cool ideas about it too?

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

So, I decided to write something stupid in Div 1 D since I haven't thought of solution.

Seemingly, I couldn't construct an example with large length, so I tried to stop my search after something bigger than sqrt(100K). As I like round numbers, I only checked length up to and including 400. Which, unsurprisingly, got WA.

After the contest, I tried using binary search to determine what the actual maximum length was on the test data. Imagine my joy when I gradually found out that the answer to that question was 401.

But, seriously, I am disappointed that this task was included in the contest if the authors were unable to find a case large enough to fail these naive solutions. Even though I liked the task intended solution with conversion to geometry.

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

    I have a standard solution to "closest pair of points": sort the points and sweepline, keep the ones already sweeped in a map<>; when processing a point, try all points with close y-coordinates, up to the K-th closest in both directions, then add the processed point into the map<>. Time complexity: . I know that if K = 50, this approach hasn't ever failed me, so I use it :D

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

      What's wrong with the standard divide and conquer?

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

        It's a bit harder. What I'm talking about is basically a bruteforce+smart condition.

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

          Your bruteforce can be turned into a simple correct solution:

          • Sweep points by x and maintain a set of points that have already been processed sorted by y
          • Maintain bestAnswer — closest distance among pairs of processed points
          • When processing a point, scan the set for all points with currentPoint.y - bestAnswer < y < currentPoint.y + bestAnswer, delete points with x < currentPoint.x - bestAnswer and update bestAnswer
          • Even though you might scan through a lot of points in one iteration, all of them except O(1) will get deleted, so the complexity is
          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I just need to remember something like "an solution similarly relies on there being few numbers close to the processed one, so there shouldn't be evil test data for my approach either" :D

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

      This worked for me too for a long period now. ( even with K smaller ) It is very usefull in a Olympiad fromat as you always make many points in short time. :)

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

    never mind!

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

    401? I also binary searched and got 1002... Look at those solutions: http://mirror.codeforces.com/contest/429/submission/6598773 (1001 fails) http://mirror.codeforces.com/contest/429/submission/6598792 (1002 passes)

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

      I would guess that you're getting WA because your initial value of best is too low.

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

        This is not the case: http://mirror.codeforces.com/contest/429/submission/6599177 g(i, i+1) <= 10^8 + 1, so 10^9 is not too low.

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

          Agreed. Hmm, that's interesting...

          Here's 400 failing and 401 passing from me. I cannot yet spot the difference in our codes.

          UPD: Oh, OK. There were some extra cases added afterwards (from community, I guess). But 401 was enough during the competition then.

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

            Ah, I understand. You're really unlucky :P. But my case is similar, I set bound to 320 :P. I thought about making it larger, but on my computer it took 1s to process maxtest, so I have left it on 320. But cf servers are much faster than my laptop, for 1000 it took 0,3ms to process maxtest using my solution, if I would have known that before, I would enlarge my bound and got AC xd. But we shouldn't complain, in fact we were "cheating" and we don't deserve AC :P.

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

    I only checked up to 100 numbers back + 100 closest positions (larger and smaller) in terms of prefix sums. I didn't know how fast the CF servers were, so I wanted to avoid TLE. Sadly, this got WA on test 39, with < 500 msec. When I increased the limit to 500 I got AC (with a running time of about 1.8 sec). Anyway, I don't think it's easy to create test cases to fail something like this.

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

      "Anyway, I don't think it's easy to create test cases to fail something like this." — it is.

      5000 (k x 10000) -5000 (k x -10000)

      for some big k.

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

Div.2 B. I used easy solution with regexps, because there were no big data. Insert x in every possible position, and While (find 3+ equal numbers){delete them}, Calc what is left. Solution with Perl 6597887.

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

This guy is lucky as hell: http://mirror.codeforces.com/contest/429/submission/6591828 He set max difference j-i to 1005 and got accepted but if it will be changed to 1001 it will fail (smallest number which can be set is 1002).

EDIT: I don't know why, but I can't reply to those posts below :( Compare those solutions: http://mirror.codeforces.com/contest/429/submission/6599177 (my solution, 1001 fails) http://mirror.codeforces.com/contest/429/submission/6598792 (my solution, 1002 passes) http://mirror.codeforces.com/contest/429/submission/6598182?locale=en (eduardische solution, 401 passes)

EDIT2: Explanation of that phenomenon is here: http://mirror.codeforces.com/blog/entry/12254#comment-169126

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

Hi,

Does Codeforces usually allow users to see test cases after the contest ends?

I see that test cases for problem B (DIV 2) are visible now, but not for problem A (DIV 2). Will it be a matter of time until test cases for problem A get released, or does Codeforces sometimes not release them?

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

lol

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

What's typically too deep for a recursive solution? I figured 10^5 would cause a stack overflow, so I wrote Div1 A non-recursively (and somehow wrote a bug into it that way).

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

    Codeforces sets the stack to 256 MB, so it's not easy to overflow it with recursion. You'll likely hit a time limit before that.

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

j = 1001

WA 47

http://mirror.codeforces.com/contest/429/submission/6599410

j = 1002

Accepted

http://mirror.codeforces.com/contest/429/submission/6599408

Nice

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

Why are the test cases not showing up till now ?? -_-

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

Round Stats

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

About div1A/div2C How is this test case valid ? http://mirror.codeforces.com/contest/429/submission/6589121 test 35

which is

10

1 10

1 9

10 2

10 3

3 7

3 8

9 4

9 5

5 6

1 0 1 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 0 0

But in the question it was given The root of the tree is node 1 But in the test case it states an edge from 10 --> 1 ???

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

    Then node 10 is a child of node 1 (the root) !

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

      No the test case assumes that the edges are bi-directional and the optimal answer is found assuming 1 to be a child of 10.

      Also the 1st test case has edges,

      2 1 and 3 1, which are opposite to 1 10.

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

        I solved the case by hand, assuming that node 1 is the root, and it is showing correct answer !

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

          Hmm .. you maybe correct about what you are saying Let us assume that if the input contains a b then there is a directed edge from a->b , like in this case 1-10, which justifies 1 being the root.

          But see the sample test here,

          It has the following edges in the input:

          2 1

          3 1

          which tells us that there are edges from 2->1, which contradicts of 1 being the root. I hope you understand what I am trying to say.

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

            Actually this is how I've generated the tests , but some of them were added later. But it didn't came to my mind that this will make any difference or someone will get confused. Though , the statement was clear sorry for the inconvenience.

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

    My friend, why do you assume that the trees are directed?

    Typically trees are undirected (unless otherwise stated in the problem), and the input specification just states that a pair ui, vi means that there is an edge between those two nodes. It doesn't mention any particular direction.

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

      Problem statement states that 1 is the root of the tree.

      Doesn't that mean if the tree is rooted so it has to be directed ?? Because root of a undirected graph doesn't makes any sense.

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

        I frankly have no answer to your statement that "root of a undirected graph doesn't makes any sense".

        My recommendation, if you'd like to consider it, my friend, would be to invest a few moments studying the definition of a tree. Wikipedia's entry is fairly well-written and I think it will helpful.

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

        Yes, you're actually right in saying that since it has a root, it must be directed (by definition of rooted tree). However, naming the root isn't enough to uniquely determine the direction of each edge (since they can either be all towards or all away from the root), the edges they give you are just a list of the edges present in the tree (without direction), and it's up to you to assign them a direction that makes sense.

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

          Wonder why they can't simply give us parent index for each vertex. Would be a lot less trouble for everyone involved.

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

    The problem statement goes as follows:

    “Each of the next n  -  1 lines contains two integers ui and vi meaning there is an edge between nodes ui and vi.”

    Note that it mentions an undirected edge between two nodes, not a directed edge from one node to another. So, the statement does not imply the nodes will be given in any particular order (from the root, or lexicographical, or whatever).

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

What were your solutions to C? First important observation is that there are at least n/2 leafs. I got AC with some weird backtracking, which tries to build (n/2)! different trees (but its search space is in fact lot smaller, but I can't come up with a better estimation). but after the contest I came up with a solution O*(2^n), but 4^(n/2) is in fact a better description of that :P. Consider a dp with array dp[n/2][3^(n/2)] (^ means power not xor ;) ). We divide non-leafs into 3 groups — nonactive and used, active and used, nonused and for given dp[k][mask] where mask denotes the division of nonleafs into 3 groups. This state is reachable iff we can build a forest where set of vertices are used vertices, set of roots are used and active vertices and where k leafs were used. But when checking if fixed state is reachable we have to search many states, possibly 2^(n/2). So whole algorithms runs in O*(6^(n/2)) ("*" means "*poly(n)", it is standard notation), which is in fact O(*(4^(n/2)) algorithm. Why? I will leave that to you as a nice exercise.

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

    As far as I got you, my solution was similar, but instead of having those 3-states I was attaching children to the nodes in some order, so instead of having 3rd state I had a variable in my DP solution which shows up to which non-leaf node I have already assigned childrent.

    DP[mask][assigningTo][remainingLeafs] in my solution is whether we can assign nodes denoted by mask to the nodes from [0 .. asssigningTo] interval using additional 'remainingLeafs' number of leafs. Internally when calculating this DP I was simply checking all the submasks of the given mask.

    Here is the solution: 6599572

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

    My DFS solution runs in time. I built it based on simpler solution, that runs in: O(3n) time. Let's start with sorting nodes by number, given in input. We encode our state as pair i,j — means that we have considered first i nodes, some of them connected and mask j contains all nodes, that have no parents. First note that i is redundant, since the last one in mask is obviously the last node considered, so i equals last bit +1. Let's consider all subsets of this mask and pick each that have at least two bits set and required sum. It is known that total amount will be 3^n. And if we precalc all sums and bitcounts, we will be able to solve problem in O(3n)

    Now let's remove all leafs from mask. Then we will have state i,j — we considered some first nodes and now we have i leaves without parents and inner nodes described in mask j.

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

All of those accepted solutions are a big shame for tests preparers:

http://mirror.codeforces.com/contest/429/submission/6599749 greedy for C

http://mirror.codeforces.com/contest/429/submission/6591828 checking pairs of points with small j-i in D

http://mirror.codeforces.com/contest/429/submission/6597823 — checking pairs of points with adjacent xs and ys in D :(

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

For (Div. 1) B, when brute forcing the meeting point after pre-computing the dp tables, my original solution (which got WA on test 23) checked every possible cell, including those on the border. Then, after contest, after viewing some of the accepted solutions, I changed it to only allow them to meet at interior points. So for this case:

3 3 1 1 1 1 1000 1 1 1 1

my new accepted solution gets 8, while my old solution got 1006 (corresponding to them meeting at the left middle cell and then one of them proceeding to the middle). I'm probably just missing some detail in the problem statement, but why is that invalid?

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

    If by "left middle cell" you mean (row 2, column 1), it wouldn't be a valid meeting point because they can't get out of that cell without both moving to (row 2, col. 2), or stepping on a cell previously visited by the other person.

    There was a clarification stating something to the effect that both paths have to be completely disjoint, except for the cell in which they meet.

    So, in a 3 × 3 grid, the only valid meeting point is (2, 2).

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

      Oh okay, I somehow missed that clarification, but I see it now. Thanks!

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

What's the solution to 1E problem. I read the code, I see what it does. However, I don't understand what is the idea behind the problem. How do I proof that doing it like this always scott_wu or SergeyRogulenko always returns a solution?

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

    Consider a sorted list of all starting and ending points of every segment. It doesn't matter in which order we place points that have the same coordinate: see below why. Starting points of red segments and ending points of blue segments would be marked with +1, and starting points of blue/ending points of red will be -1. We need to make sure the sum in every prefix is between -1 and 1. This means the sum at all even points will be 0. This means points 2k and 2k+1 must have different signs. Also, obviously, two ends of the same edge must have different signs. We got a graph that we must color in two colors. Now note that the graph has two kinds of edges, and edges of the same kind can never share a vertex (by construction). This means that there are no odd cycles, so we will always find an answer.

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

The problem A div2 make me crazy!

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

I used O(min(abs(a[i]))n) past the problem D ....

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

The data for D is weak. My AC solution gets this case wrong:

1 10000 ... (2000 times) ... 10000 -5000 -10000 ... (1999 times) -10000 -5000

My AC solution: http://mirror.codeforces.com/contest/429/submission/6596958

Generator code for this test case: https://gist.github.com/jonathanpaulson/1d5fb7825395185dcd5d

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

    It is difficult that make this problem's data. But my solution is ugly. In this case 100000 10000 10000…… (100000 times) my sulution will TLE.

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

I feel so stupid trying to solve E for an hour until the time ran out then doing C in 15 minutes after the contest =\

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

About problem 429A, a recursive version solution got RE while a iterative version passed.

http://mirror.codeforces.com/contest/429/submission/6605357 http://mirror.codeforces.com/contest/429/submission/6605261

Is this a limitation of a interpreted language, so most people chose compiled languages to do the recursion?

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

    You seem to have set the stack to 100k, which seems to be enough at least for that particular test (but would probably fail on the maximum one). I would avoid python here. It barely works on topcoder, and they have WAY smaller datasets. If a correct solution to any problem takes half a second in C++, it would take like 5 seconds in python.

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

    Yes,it is a huge limitation. I don't prefer to use python for a recursive solution that has a depth of more than 1000(the default recursion limit in python) ... Though the stack size in codeforces is very large, but python requires more!

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

    In my experience:

    sys.setrecursionlimit

    just sets "desirable" limit. If stack space ends before this setrecusionlimit is reached, python interpreter just dies silently. Also Python reserves a lot of stack space on each iteration. In one examples of mine I needed just 3,000 recursion limit and it died on my local machine at around 2,500. I didn't even receive any error messages — python just stopped execution and finished. 100K I think is impossible for Python even with very large stack space.

    → Reply