PrinceOfPersia's blog

Codeforces Round #366
By PrinceOfPersia, history, 8 years ago, In English

Hello ladies and gentlemen.

I'm honored to announce you that Codeforces Round #366(or should I say, IOI 2016 opening CF contest) is gonna take place on August 7th and I'm the writer. Please note that the timing is unusual.

As usual, there are 5 problems in each division and duration is 2 hours.

I want to thank LiTi for testing this round, GlebsHP for helping me prepare it and MikeMirzayanov for legendary and unique platforms of Polygon and CF.

The main characters of this round are The Avengers!

I wish you all Accepted solutions and Successful hacks.

Scoring will be posted soon.

Problems are sorted by their expected difficulty, but I strictly recommend you to read all the problems.

GL & HF!

P.S: Top IOI participant in each division (only with handle present in this list) will be rewarded with Persian souvenirs in Kazan.

UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!

UPD: Scoring is 500 — 1250 — 1250 — 2000 — 2500 in Div.1 and 500 — 1000 — 1500 — 2250 — 2250 in Div.2

UPD: I'm really sorry about the difficulty. System test is about to begin.

UPD: Editorial is out.

UPD: System test is over, congratulations to the winners.

Div.1 winners are:

  1. kcm1700
  2. WuHongxun
  3. dotorya
  4. lawrenceli
  5. W4yneb0t
  6. Swistakk
  7. KADR
  8. fqw

Div.2 winners are:

  1. korla.march
  2. dev.plvlml
  3. dantrag
  4. ODT
  5. ntopia
  6. vokeal
  7. pyrexshorts
  8. _index

Souvenir winners are lawrenceli from team USA and eXeP from team Finland (If that's not true write me in private).

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

Comments Comments (262)
| Write comment?
»
8 years ago, # |
  Vote: I like it -66 Vote: I do not like it

kiram to maghzet

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

    kiram to kasi ke manfi bede... kalle kiria manfi midin vase chi

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

      namosn mellat nmifhmn chi migi mosbat midn :D

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

        به تخم چپم که نمیفهمن کصکشا

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

          bashe fahmidim toam az in chiza baladi hala gooreto gom kon inja jaye in harfa nist.

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

A contest for IOIers, prepared by an IOIer.

Just how freaking amazing PrinceOfPersia is.

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

Top IOI participant in each division will be rewarded with Persian souvenirs in Kazan.

This remind me of the reflection of zhj who participate in IOI 2015 as China team's member.

He said a iran team member gave lyy 300 IRR as souvenir and as return, lyy gave him back 10 RMB. After that they checked the exchange rate...

(300 IRR = 0.0664 RMB)

(No offense, just saying. I look foward to seeing cool souvenir from iran team too!!)

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

    I really don't think that the value of the currency matters because it's a souvenir and I seriously doubt they would want to spend that money anyway.

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

      Yea I think so. It is just funny that they didn't get along with the exchange rate and didn't know how much to give as return as proper. And giving a relatively large amount of money.

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

        Last year I didn't prepare any souvenir and in the last moment I heard from my brother that in IMO people exchanged their own currencies, so I picked up moneys which I got from my grandpa, those were for 30 years ago and had absolutely no value in cash! However they are really rare and antique somehow :-D I'm sorry for the inconvenience I caused.

        By the way, this year is different and you can expect many cool stuff :)

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

          wow! Then I think it totally worth it. Sorry for the misunderstandings.

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

        "relatively large amount of money." XDDD

        Are we seriously creating a discussion which looks like accusing somebody of being a dirty defrauder because of <1,5 USD?

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

          lol I don't know how can you read my word as accusing somebody as a defrauder. How can you defraud someone by giving someone money first.

          I just think nobody would give 10RMB as souvenir as normal. 10RMB is a banknote(normally people would give penny as souvenir). Also 1, 5RMB is also banknote so I think giving 10RMB is abnormal.

          I apologize if my wordings are shown as offensive as English is not my mother language. I have no intention to say anyone as a defrauder.

          I agree 10RMB is not much money but I can eat many food and have breakfast using just 10RMB. I would be doubted before I give someone 10RMB as souvenir if the amount of money means nothing and can give other as alternative and the meaning is still the same. That's why I used the word relatively. Or maybe I'm just poor or stingy.

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

    300 IRR :|

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

Are you really confident of using "the Avengers" character? :D

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

    I don't think I get the references. Can someone enlighten me, please?

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

      It's Mickey Mouse and Minnie Mouse in front of Kazan Kremlin (IOI 2016 is gonna be held in Kazan).

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

        Nope, the castle is just located in Disneyland.

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

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

Avengers related contest after Suicide Squad premiere? :D

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

Why is it unrated?

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

    The writer never said that it was unrated.

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

    It is rated, and I will become purple JIBANCANYANG. that is great, okay gays come on!

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

      You would better change "gays" to "guys" because of their meanings! :D

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

      Is it funny to say the same thing again and again :|

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

    wrong place

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

    Forgive me gyus, I mistaken this word as unrated.

    UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!

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

BTW, there are some teams (like team Kazakhstan) who weren't on my list but are now here. Wouldn't taking handles from that list be a better idea?
UPD: he changed it

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

    You rewarded with 3rd place in the last contest :P :D
    anyway good luck bro ^^

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

Go back to my blue xiaoai. Fighting!

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

Is it rated?

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

    Sure！

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

    Why do people ask this question so many times? Usually the rounds are rated and in the case it ends up being unrated (last contest), it's usually made pretty clear (almost always in bold).

    Do people just want negative contribution?

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

      I think in this contest people have read Totally unrelated as Totally unrated it happened to me.

      but in other contests I don't know why maybe it's one of codeforces traditions.

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

    I used to be voted down because of this question. From that, I always find the information in mail! =)) My contribution is negative. You should find by yourself before asking anything.

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

    Why negatives??

    We should know this after the last contest became unrated...

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

salam

manam mikham emtahan konam babinam mosbat midan?

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

    do most words in your language ends with "en" or "em" ?

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

Good luck guys! Wish you success!

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

"Top IOI participant in each division will be rewarded with Persian souvenirs"
Should I expect no-math problems ?

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

I hope everyone will be better!

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

I hope this round quickly judged. Better rating!

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

    Well, this turned out to be a case of being careful what you wish for.

    (As in, systest will be over very quickly)

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

Iranian contest always contains full of expected value problems... ~.~

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

I wish high rating for everyone :D

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

Good Luck Everyone!!!

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

    and may be you are Mr Everyone, right? Nice to meet you! ;)

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

It would be fun with Avengers :D. Moreover so many hacks I guess. GL all :)

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

Is this contest rated or unrated?

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

What is the major idea in lots of amd's problems? — Math and Probability I guess

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

    In Iran's INOI math , graph theory & combinatorics is very important & also PrinceOfPersia is a INOI gold medalist!

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

I hope to be a pupile in this round , I hate my gray color XD XD motivate me please XD

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

hey 10 mins delay please :(( I'm coming...

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

amd problems that I solved in practice are very test case-y.

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

Ignore this comment.

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

These problems are for Div 0.

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

Hello. I returned after 5 day trip without internet and occasionally found that #366 is running. I could participate during 1h 20min which remain, but why registration is closed, reason?

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

You know the contest is hard when there are only 27 people in Div 1 who solved B and only one person to solve C when the contest is 80 minutes in....

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

I think that today no avenger cannot solve all the problems at the time of the contest. Because it is very difficult tasks. ('_')

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

Fill like "Hawkeye" — so useless.

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

OK

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

The Avengers take a revenge with their hard problems!!

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

Nothing to to do when there was 1 hour left... Most difficult round I have participated in.

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

Hardest contest ever. How to solve Div1B? I tried O(n^2) DP but failed...

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

Thanks for this round. But I still want to say, I feel very terrible now.

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

After contest ends can somebody explain how they solved Div1 B (Div2 D)?

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

    The solution is trivial if O(n3) dynamic programming algorithm passes 4 seconds limit.
    I will wait till the submission is allowed and test my solution.

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

      Obviously it doesn't pass

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

      Isn't it impossible for O(n^3) to pass in 4s?

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

Did the author prepare interesting problems? — Yes, he actually did!

Did the author prepare interesting contest? — No, absolutely no!

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

May have gone away 1 hour and 53 minutes before the end :|

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

Anybody else thought that in A the first t notifications are the first t in the stack of notifications like any social app? :D

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

    Really I WA many times on that..

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

    Wasted 2 WAs because of that :(

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

    Oh, so it wasn't translator's fault!

    6 WAs because of that :c

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

I hope Codeforces can balance the difficulty next time……

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

So many people overflowed on 2B, but apparently overflowing is completely irrelevant when just determining whether an integer is odd or even. Sadness.

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

    My hack for Div2B was
    2
    2 1

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

    Can somebody explain why this happens? , Me too, I had a lot of overflowing solutions in my room and I couldn't find a case to hack them.

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

      If it is int, then overflowing goes modulo 231. We only need the parity of the sum. Parity doesn't change modulo 231, so overflowing is not a problem at all.

      UPD: If we check whether the sum is equal to zero mod 2 — we can't hack anything. But if we check whether it is not equal to 1 mod 2 — overflowing works I believe.

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

    No

    if somebody used if(s%2==1) print 2 else print 1 then we can hack by

    3

    1000000000

    1000000000

    1000000000

    But everyone in my room checked using s%2==0.

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

      Yes, since that was the only hackable solution, I too checked all the solutions. Lots of if(s%2), if(s&1), and if(s%2==0), but not one if(s%2==1). Guess there's no justice in this world.

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

        why is (s_int & 1) always equivalent to (s_LongLong & 1) in overflow?

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

          You can just think it as if the first bit in int represents -2^32, so it doesn't affect the % operation nor the & operation.

          Well, technically it does affect % operation, as dush1729 said.

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

What is test case 3 in div 2 C?

code can anyone see my mistake? please tell me

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

Oh no, I just finished B :(
What was everyone hacking on A?

UPD: Seems like my B is too slow.

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

Damn -O2 optimization ;(

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

    I got 2 unsuccesful hacking attempts because the optimization fixes the O(N) while loop

    Good to learn that the compiler optimizer does that for next time :)

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

      I wonder if they actually knew the optimization would work or just wrote inneficient code and got lucky ...

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

        I have read about it many times(in CF blogs) but I thought 10^14 operations will give TLE even with -O2 optimization. I guess it's best not to hack Div2A for TLE.

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

I like long statements but this time statements in div1-A and div1-B were so misleading. Reading the same notifications and jumping to the left only when one is small — at least strange.

An approach for "Kangaroo" problem from CEOI few weeks ago gives a solution for 704B - Ant Man immediately.

But kudos for providing hard problems.

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

    Could you give a link to statements and analysis? Thanks.

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

      According to Xellos's comment, their online judge is down.

      The problem statement was:

      You are given three integers s, e, N (1 ≤ s ≤ e ≤ N ≤ 2000). Find modulo 109 + 7 the number of paths from s to e that:

      1. Each of n vertices is visited exactly once.
      2. You can't go twice in a row to the right (e.g. 3 -> 7 -> 9).
      3. You can't go twice in a row to the left.

      The solution is described by muratt's comment — in short go from left to right and keep dp[i][the number of times you move above i].

      My solution today: 19697314.

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

        Thank you. Really not obvious, that we can do this, it's the NP-problem in common case (I thought that we can create a test where |xi - xj| doens't take part much in the answer).

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

        I've read your solution and the muratt's comment and still cannot comprehend the solution.

        Could you, please, elaborate a bit more on the method you used?

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

          Imagine an optimal path. For every position i imagine a vertical line cutting the path j times. The idea is to calculate dp[i][j] — the minimum cost of arranging parts of the path on the left (before i) so that it would go exactly j times through a vertical line over index i. In my implementation j is the number of times the path goes from left to right. So, it must go from right to left j or j + 1 times (the latter if we are between s and e).

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

            Is there any proof why this gives optimal solution? Why this can't be applied to generic graphs to solve TSP problem? Is your solution the same as in editorial or it uses diferent idea? If different, do you understand how is it solved in editorial?

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

              As in any dynamic programming — we consider all possible paths so yeah, we must find an optimal solution. A solution in editorial is slightly more complicated but the idea is the same. Two dimensions of my dp are (I think) the same as two first dimensions of dp in the intended solution. I handle s and e a bit better.

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

Was Dinic intended in D?

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

    Yes

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

      Then why are the constraints so high? I spent about 20 minutes, trying to come up with a faster solution, but in the end I just convinced myself, that it can't be done faster. Do you have any proof, why it works fast? The graph is bipartite, but the capacities are not unit, so I don't think that it works in .

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

        It works in according to Karzanov's theorems.

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

          In my solution I also need a binary search around Dinic so it'll be O(E1.5·logN). Does the intended solution do the binary search as well or it's just me?

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

            It's just you, though I understand where this log comes from :)

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

              I see, thanks! In this case I can't wait to read editorial to see how to avoid that binary search :)

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

                It's not something magically invented to that problem, that is just what needs to be done in typical LR flow, however I admit it is a bit tricky and I also had binary search on my mind for some time. In my implementation I firstly compute flow from s' and t' to find a saturating flow and then compute max flow from s to t on the residual network resulting from previous flow (notation as here: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf)

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

                  Ah, right, instead of minimization we can try to maximize the flow here. In my solution I was always thinking in terms of minimization of the number of blue points (if r > b, then swap blue and red) and that's why I needed a binary search. But in this problem we can instead maximize the number of red points and thus we can solve it without binary search. Thanks!

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

On the other hand, system testing will be shorter than usual:)

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

Very tough problems — thanks amd for the contest!

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

The problems were interesting, that's for sure, and I'm eager to find out how B and C are solved, however, the contest itself was very unbalanced. There were too many contestants who were simply stuck after solving problem A. Ideally, the difference in difficulty for every two "adjacent" problems should not be so large.

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

I think that these problems are difficult to understand

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

Div2.D/Div1.B has pretty strange storyline...

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

any help for DIV 2B.. I suffered there -_-

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

    Just sum all arr[i] — 1, and check parity of the sum. If it's even, print 2, if it's odd, print 1.

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

    Yeah! A chain of size C will always take C-1 moves before it is reduced to chains of size 1. It doesn't matter what moves the players make — the total number of moves will always be the same. That means you can update the winner just by checking if the new chain has an even or odd length.

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

    No matter the way they play, they winner will be determined by the number of turns the game takes to end. So, is just a parity check!

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

http://mirror.codeforces.com/contest/705/submission/19709431 Some one please tell test case 3 ?? Why is my code wrong ?

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

    The way you handle the third operation is incorrect. Your code considers whether there are still unread messages for application X if I understood it correctly.

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

    I think test case like below will break your code

    In the 4th command x[1]>0 but its position is 2. So you should not remove it.

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

I received a compilation error with the following message:

"Can't compile file:

cc1plus.exe: out of memory allocating 5584 bytes"

What happened? (I submitted the same code after it and the verdict was another one)

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

    Sorry, it happens sometimes because of some memory lacks. I'm finding the way to fix it.

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

In Div2D/Div1B is simple Dijkstra-like approach incorrect? If it is(I guess it is after those results) — why?

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

    Because with Dijkstra, how will you guarantee that you've visited every vertex exactly once in your optimal path?

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

    How you will check that the answer found by Dijkstra passes through all vertices?

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

    I solved it with dp

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

Man I busted real hard after Div 2 A lol. Can anyone explain the logic behind why B was so simple? And I screwed up too many times on C.

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

    Check out ghazanfar_iiuc's question above!

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

      Ah! That actually makes a lot of sense lol. Dang that was pretty simple I guess. Thanks for the help!

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

    Generally it is easy to see that if you generate winners for first 10 values or something else...

    It is classical Grundy theoreme and you can see that for even numbers grundy value is equal to 1 and of odd it is equal to 0. After that in case total xor (it is same as amount of even numbers % 2) = 0 winner is second otherwise winner is first.

    P.S. You don't need Grundy, it is just checking parity with finding optimal strategy. Anyway I thought as above on the contest.

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

      Hmm interesting. I'll take a look at the Grundy theorem sometime soon then. Thanks for the help!

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

biggest integer number is odd and after overflow we have even negative number.

it is correct for B (if you use int instate of long long int) ||(have overflow).

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

Whether someone else got TLE on d2 third with using set ?

I can not understand why that solutions gives TLE and some other solutions with Seg. Tree are correct.

My TLE code

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

I was cheated by the javascript timer in my computer. When I was going to submit Div1C (2 minutes remaining), bump... The contest is over, :( !@#%. **** I hope my solution is bad, otherwise !@#%.

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

Didn't registered for the contest and came 45minutes late, looked at the standings and thought WTF 45 minutes in no Div2 participants solved Antman.

It only took me 15minutes to understand all other participants' feelings.

I wonder how the Div2D question is solved, it's pretty hard to take delta x into consideration.

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

By the way, queues are very evil, vectors are much more kind.

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

    12MB vs. 260MB... why? Can someone explain?

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

      Yep, this doesn't look right; I used queues.

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

      This is known problem, deque allocates way too much memory to store elements in it. Queue is using deque as a container for values by default.

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

As a chinese netizen, I devoted myself to the great Chinese network. When there are 10 seconds to the end, I submitted a solution of B(I think it is correct because I stress tested it). And then when I refreshed the page, it says the solution wasn't submitted. If the contest was 5 seconds longer I could have made it submitted. :(

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

understanding the description is harder than solving the problems

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

I think the contest is not div1 but div0...... It's too hard!!!

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

wish you all high rating:D

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

How to solve DIV 2-C

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

    Deques: deque<pair<int, int> > q — store all added notifications, deque a[N] — added notifications for each app.

    int ans = 0, cnt = 0;
deque<pair<int, int>> q, a[N];
// ...

for (int i = 0; i < q; ++i)
{
    if (type[i] == 1)
    {
       a[x[i]].push(cnt);
       q.push(make_pair(cnt, x[i]));
       ++cnt;
       ++ans;
    }
    else if (type[i] == 2)
    {
       ans -= a[x[i]].size();
       a[x[i]].clear();
    }
    else
    {
        while (q.front().first < x[i])
        {
            if (a[q.front().second].front() == q.front().first)
            {
                a[q.front().second].pop();
                --ans;
            }
            q.pop();
        }
    }
}

    Something like this :)

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

      Could you explain this ?

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

        Sure, firstly, we just add notifications one by one to deques (q — all notifications, a[x[i]] — notifications of the x[i]-th application). Add means push cnt value to deques, cnt — number of current notification, in other words, the number of queries of the first type. So we could notice, that all numbers in each deque will be sorted. We want to store there only non-readen notifications.

        Secondly, ans — number of non-readen notifications, for 1 type: just increase by one ans, for 2 type: we decrease ans by a[x[i]].size(), because we read all non-readen notification, for 3 type: a little bit more complex.

        Thirdly, 3 type, we need to remove all notification from common deque, that have number less than x[i], but we should descrease answer only this number presents in the app deque. So, all deques are sorted, we have pair<int, int> on top of the q (which means: first — number of notification, second — number of application), then we need to remove this notification from application. So we do this like for two-pointers problem.

        In conclusion, we add and remove one notification from deques one time, so complexity is O(n + q).

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it 
    msg apps[n]; // app[i] stores information about all the messages of application i.
int message_queue[max_messages]; // message_queue[i] stores index of app responsible for message i.
int curr_unread_message; // index of the message in message_queue[] that is not currently read.
int queue_end; // index of the next to last message in the message_queue

int total_unread_messages; // total amount of unread messages from all the apps.

    Probably, the most interesting part is msg structure: 

    apps[i].unread_messages = 15; // 15 is total amount of unread messages by from app i.
apps[i].queue_index; // The index in the message_queue[].

    All the messages of app i in the message_queue before index apps[i].queue_index are read by Thor. When comes the query of the seconds type, we change that value: apps[i].queue_index = queue_end.

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

Not Happy....Problem set.

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

It looks like in order to perform well in PrinceOfPersia's contests it is profittable to get well acquainted with his previous contests :D.

http://mirror.codeforces.com/contest/547/problem/D -> http://mirror.codeforces.com/contest/704/problem/D (with solution fitting to both problems here: http://mirror.codeforces.com/blog/entry/18126?#comment-230210)

http://mirror.codeforces.com/contest/536/problem/E -> http://mirror.codeforces.com/contest/696/problem/E (those are not that similar, but HLD is a rarely used method)

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

Is any solution for Div1-C with simple implementation?

I solved this problem but i could n't implement cause it was so long!

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

How to solve DIV 2-D........n^2 -DP ? Maybe?

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

    I solved it just by adding chairs one by one. Just insert them in the optimal place in current path. So you are right, it is something kind of DP.

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

      orz! rank1!

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

      I don't really understand why this solution can solve this problem. Could you please explain it to me or give me some proof about the correctness ^_^.

      p.s I think this solution is kind of a greedy solution.

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

        How do we know that this greedy solution works?

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

v

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

    I don't quite understand your code... But it seems that you are considering cycle by cycle, since you are setting x and y to 0 whenever a new cycle is added.

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

You would better make this contest unrated -_-

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

I'm surprised E does not have any submission in Div2 and D does! E was definitely felt easier D.

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

I got TLE on third with O(n) solution. This becomes funny :D

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

    Same idea and same TLE well dunno why it doesn't work

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

    Me too, TLE with O(2*N)... :/

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

    It seems that many people are getting TLE43 on Div2C with the O(n) solution where you take a vector and then keep track of the most recent deleted location.

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

    u = x + 1 is causing troubles when x + 1 < u. Rather make it u = max(u, x + 1). Queries like 3 100000 -> 3 1 -> 3 100000 -> ... will break your solution...

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

      Well that was a simple mistake haha thanks for your help ! It won't happen next time for sure

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

      I not to miss that case, nice hack :P

      In last time with this queries, I am always think that queries are sorted. My bad!

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

Could somebody tell me what's the type of the problem C of div 2? I Had a really hard time solving it,and I wonder if I want to solve a problem like C of div 2 in this contest next time,what should I learn? Is there some problems like this or some tutorial I can refer to?

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

Does anyone have an idea, what might be the purpose of the function lucky_test() in 19691627 ?

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

    adrenaline

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

      considering there's no srand, I'm not sure it's for adrenaline.

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

      I am sorry, but I still did not understand the purpose of lucky_test().

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

    To generate random input for the program and test your implementation. You can implement 2 solutions: bruteforce and clever one. Then use lucky_test() to compare results: bruteforce(a, b) == clever_solution(a, b).

    I read once again the usage of the function... well, probably it is really for adrenaline :)

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

      Comparing your bruteforce() and clever_solution() has nothing to do with this lucky() function...

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

System testing is slow as hell

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

Thanks for tough but interesting problems, PrinceOfPersia! And for lightning-fast editorial!

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

Thanks for the early Editorial! I hope this continues in future contests .

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

Heck! :\ Used set instead of queue in DIV2C. Thought it won't affect much. But here i am with TLE on 43rd case. :'( Hurts!

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

    I used set and it worked. Your solution handles incorrectly the third query. You should change "last = t" to "last = max(last,t)" or something like that!

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

      Woh! Crap! I was initially using a separate 'if' to handle cases greater than 'last'. Later, I wrongly assumed that loop condition was taking care of everything automatically and removed the 'if'. Didn't notice that 'last=t' wasn't handled by 'for' loop condition. Thanks for pointing that out, I really appreciate that.

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

    http://www.codeforces.com/contest/704/submission/19712670 segment tree with lazy update solution :D if segment tree can work set should definitely work

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

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

Why my submission for problem 705a is wrong at tests 11 19688500

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

So Avengers have won the match :P

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

What is the greedy solution for Div2D/Div1B?

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

    First add to the current path two chairs: s and e. Then, go through all other chairs and add them one by one to the path. For each chair, find the best position in current path where it should be placed. The best position is the one for which the total time for new path will be minimal.

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

      I literally have no idea why this works, but so far we were unable to find countertest.

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

        Me too. But I believe there is a proof.

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

        I was considering this solution but didn't wrote it cos I couldn't it. Still not convinced it's correct :d

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

      Seriously? How does this work...?

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

      It seems like, it can be proved (or disproved ;) ) by induction.

      For n = 3, it is valid to insert new vertex v1 in the middle: ( s, v1, e).
      For n = 4, after we've inserted v1, we can only choose between 2 configurations: ( s, v2, v1, e) and ( s, v1, v2, e).

      Let's say the configuration ( s, v2, v1, e) is better than ( s, v1, v2, e). Now consider the fifth vertex v3. We have two choices:
      1. Try adding v3 to the winning configuration.
      2. Try adding v3 to the loser configuration.

      Then we get two sets of possible configurations:
        After adding v3 to the winning configuration:
      1. C1 = ( s, , v2, v1, e), C2 = ( s, v2, , v1, e), C3 = ( s, v2, v1, , e)
        After adding v3 to the loser configuration:
      2. D1 = ( s, , v1, v2, e), D2 = ( s, v1, , v2, e), D3 = ( s, v1, v2, , e)

      Now compare the pairs of configurations: (C1, D1), (C2, D2), (C3, D3). If configurations Ci always give better result than Di, then induction worked and solution is correct. Otherwise, we can construct a counterexample to that greedy solution.

      Start with pair (C1, D1): C1 = ( s, , v2, v1, e) and D1 = ( s, , v1, v2, e).
      The configuration D1 is better than C1 only if the time of the jump T(, v2) is significantly bigger than T(, v1).
      For pair (C2, D2) we need to compare T(v2,  ) + T(, v1) and T(v1,  ) + T(, v2).
      And for the pair (C3, D3) we need to compare T(v1,  ) and T(v2,  ).

      If you know how to proceed with the proof, please write the comment.

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

        But how do you take delta x into consideration? It changes position by position so you can't only consider the best pair of a[]d[] or b[]c[] right?

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

        I believe this case: 

        5 1 2
8 10 12 16 17
18 20 17 16 21
2 20 5 13 17
8 8 10 12 15
13 12 4 16 4

        Fits the property that ( s, v2, v1, e) is better than ( s, v1, v2, e), but it also has

        • Sequence C: 125 132 130
        • Sequence D: 130 131 138

        So the greedy still holds (as 125<130), but each comparison C_i<D_i is not true.

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

          Ok. It means that in order to disprove the algorithm we have to find an input with the property that minimum time in the winning configuration is worse than the minimum time in the loser configuration:
          min{T(C1), T(C2), T(C3)} > min{T(D1), T(D2), T(D3)}.

          I think, at first it would be easier to find the case when mini{Ci} = minj{Dj} and then tweak it to find counterexample or some restriction will show up which we will use to prove the general induction step.

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

            I tried generating random sample cases and the greedy still passes. I did observe two trends, one of which I know how to prove:

            • C1+C2+C3 <= D1+D2+D3 (by simple cancellation and algebra)
            • There exists i,j so that C_i=D_j (not sure of the specifics of a proof, just something I noticed from samples)
            → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Consider this example

        Consider each edge that's not drawn as very big integer. The greedy approach will build path s->e, then s->1->e, then s->2->1->e, then s->3->2->1->e. The weight of s->3->2->1->e is 2+2+2+2, but the weight of s->3->1->2->e is 2+1+2+2 which is less.

        If I'm not mistaking this should be a counterexample. What do you think?

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

          Ah, except this graph is not possible, as the cost from 1 to 3 can't be one. T(3,1)>T(3,2)=2 because of the ordering of x_i. That's why when you do the greedy out of order you get WA, but when you process them in order it works.

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

            Here's a proof that the greedy works for a special case of n=5.

            First, denote X(a1,a2,a3,a4,a5) as the total time of the past (a1,a2,a3,a4,a5).

            The approach is to consider an optimal length 5. We want to show that when you remove v5, you have an optimal path length 4.

            The special case is that: s=v1,e=v2, and (v1,v3,v4,v5,v2) is optimal.

            Thus, since it is optimal X(v1,v3,v4,v5,v2)<=X(v1,v4,v5,v3,v2). Writing out each T, you obtain:

            (x3-x1+d1+a3)+(x4-x3+d3+a4)+(x5-x4+d4+a5)+(x5-x2+c5+b2) <= (x4-x1+d1+a4)+(x5-x4+d4+a5)+(x5-x3+c5+b3)+(x3-x2+c3+b2).

            Which reduces to a3+d3 <= b3+c3. However this is exactly the statement that X(v1,v3,v4,v2)<=X(v1,v4,v3,v2), if you cancel variables on both sides.

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

              I see your point. Seems like the ordering makes a lot of problems.. I considered the problems is equivalent for the problem for random graph (positive integer weights) but actually it isn't T_T

              I don't agree T(3,1)>T(3,2) because the a, b, c and d values can be set such that this is incorrect. (but still you convinced me that the whole graph couldn't be random). Seems like I should spend more time on proving / disproving.

              This special case of n=5 is too specific. Do the same arguments hold for other (all) cases of n=5?

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

                Yes I made a mistake, T(3,1) is not necessarily greater than T(3,2), but there is an ordering property. My specific example isn't terribly helpful, but it does motivate the idea of trying to compare path permutations to reduce to the result of the smaller inequality.

                Thus I wrote a program to do this. It uses the same method that Pixar started. However, as I mentioned earlier, it is not true that C_i<=D_i for each i. But if you rearrange the D_i, depending on what s and e are, you can get C<=D. Here are my results and the source code:

                I can explain what the output means for one example, s=1,e=2. 

                1 -> 2
0 0 -1 0 0 
0 0 1 0 0 
0 0 1 0 0 
0 0 -1 0 0 
0 0 0 0 0 

1 3 4 5 2 vs 1 4 5 3 2 
0 0 -1 0 0 
0 0 1 0 0 
0 0 1 0 0 
0 0 -1 0 0 
0 0 0 0 0 

1 3 5 4 2 vs 1 5 4 3 2 
0 0 -1 0 0 
0 0 1 0 0 
0 0 1 0 0 
0 0 -1 0 0 
0 0 0 0 0 

1 5 3 4 2 vs 1 4 3 5 2 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0

                The five by five grids are the coefficients of a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 etc. in each inequality (when it's all reduced and moved to the right). E.g. 1 3 5 4 2 vs 1 5 4 3 2
                means X(1,3,5,4,2)<=X(1,5,4,3,2) which is equivalent to 0<=-a2+b2+c2-d2, which is the known inequality at the top.

                At the very top is the inequality X(s,v3,v4,e)<=X(s,v4,v3,e). (If the opposite is true, all the signs below can be flipped.)

                Thus this shows that C_1<=D_3 (they're equal actually), C_2<=D_1 (as this reduces to the starting inequality for a path of length 4), and C_3<=D2 (similarly).

                Some observations that may be able to generalize:

                • There always equals i and j so that X(C_i)=X(D_j).

                • I believe the comparison is always a shift of D, i.e. the solution is either (C_1,C_2,C_3)<=(D_1,D_2,D_3),(D_2,D_3,D_1), or (D_3,D_1,D_2)

                EDIT: After more carefully reviewing my results I observed that this second observation is not true.

                Source code: http://pastebin.com/m4YPJK7t

                Output: http://pastebin.com/W1kC7SeB

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

what do you call this!? :O

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

Now waiting for contest with DC heroes :)

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

CHEAT:

user "Deemo" cheated in #366. he used fakes to see if both of his solutions were right or not. and after that he submit them with his own account. Trust me. I know him and his evil plans.

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

    Well I guess he didn't solve A fast and waited to see if he can solve B or not (and if yes submit A after that)

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

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

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

Compare 19711616 and 19711892, first one in java second c++.

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

Please could someone explain, why this 19701013 solution got AC? İt's complexity is O(n*max(ai)).

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

Thanks for interesting problems and kind of boring round )

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

This is the only contest announcement I have seen that has negative contrib :O

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

It is not good at all to announce a round only in English. Minus.

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

Could anyone explain why this solution got TL? (Problem C(div2) / A(div 1))

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

Guys, come on, I don't understand amount of downvotes. Tasks were nice, there were no major issues with them. Nothing bad in having challenging tasks. When did solving only those problems we are able to become hotter than facing challenges :)?

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

this amount of downvots are bother me more than they bother PrinceOfPersia
the tasks were superb , they were very tricky and difficult
now this is the last contest for PrinceOfPersia , here
thank you a lot AMD I will miss your contests

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

I don't know about you, but I feel that this was one of the best contests I have ever taken part in. It was obviously much harder than a regular CF round, but the problems felt so unique and original, and the solutions were beautiful (and not that hard to comprehend, to my pleasant surprise). Great round!

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

Sorry ,I want to know where is Tutorial.

→ Reply