adamant's blog

By adamant, 8 years ago, translation, In English

Hi everyone!

Yeah, you guessed it right, after a long four month break after the latest div. 1 round which was not dedicated to any official competition, you will once again have the unique opportunity to participate in usual codeforces round. No t-shirts for top-x competitors! No multi-level selection system for the opportunity to compete in final! No esoteric languages or marathon-like problems! We even will not tell you the scoring untill the very end of the round! That's it, like the good old days.

So this round was prepared for you by Ivan Smirnov (ifsmirnov) and me (adamant). We want to thank Max Akhmedov (Zlobober), Alex Frolov (fcspartakm), Edvard Davtyan (Edvard) and Mike Mirzayanov (MikeMirzayanov) for the help in round preparing, and useful advice. Special thank to Edvard for taking the role of coordinator this time and traditionally MikeMirzayanov for polygon and codeforces systems.

Good luck to everyone! We really hope that you will have a lot of fun participating in this round :)

UPD. Score distribution:

Div. 2: 500-1000-1500-2000-3000

Div. 1: 500-1000-2000-2000-3000

UPD. 2. Also thanks a lot to Alex Fetisov (AlexFetisov). Forgive me, please, I have totally forgotten about you :)

UPD. 3. If you missed the editorial, you can find it here.

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

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My nerves are thin after previous contests, I hope one amazing and interesting round !

Good luck and without frustrating bugs :)

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

Hahaha.. This blog has been written so well.. Waiting for tomorrow...

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

    প্রিয় গ্রাহক বায়োমেট্রিক সিম নিবন্ধনের শেষ দিন কাল। আর অপেক্ষা না করে ১ কপি ছবি, ভোটার আইডির কপি ও সচল সিমসহ এয়ারটেল বায়মেট্রিক পয়েন্টে আজ-ই চলে আসুন।

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

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

      MR Airtel,

      Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you.

      char c='F'; char c2='*'; cout<<c<<c2<<c2<<'k'<<" "<<"OFF";

      {sorry everyone for the disturbing comment but I feel we have to be respectful to everyone. We[bangladeshi] are just destroying our reputation.]

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

      I think some regular contestant has created a fake ID to make fun.

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

      I am too lazy to translate, what was written there?

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

        It says tomorrow is the last day of 'Sim Registration'. So hurry up.... :3

»
8 years ago, # |
Rev. 4   Vote: I like it +52 Vote: I do not like it

When i first see adamant is the author of the contest, my first impression is.. i have to read about policy based DS

(if you know what i mean :D )

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

    I don't know... What do you mean?

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

      You are the only source i found explaining the (policy based DS) in your blogs here here and here, and in the last round when i saw your submission 17490448

      ( less than 20 lines on E div1 :D ) using (policy based DS). so i think you might prepare problems which is solvable with this (policy based DS). that's it.

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

      Sorry,but where is the solution?QAQ

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

    So that's who is responsible for all these pbds-clang-incompatible solutions. Every time I need to compile them (with clang) in education round I have to delete this stuff.

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

"We even will not tell you the scoring untill the very end of the round!" — didn't you mean very beginning of the round :P?

Btw, I will keep some suffix array prepared for tomorrow :D.

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

    No, I meant very end of the round.

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

      So, are you simply not counting making it public at the start of the contest as telling?

      Btw, is it rated?

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

        All I can say is that we don't yet know the opposite.

        P.S. You should definitely have asked this question right after the post appeared to get more upvotes!

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

        How about dynamic scoring? :) You don't really get to know the scores until the end of the round.

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

          We will consider this, thanks for brilliant idea!

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

            It can be concluded from announcement that you really like usual rounds, so better keep it static :P

            Btw sometimes it is hard to get the irony in the Internet, but I hope that your post was pure irony :P.

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

I have missed so many contests in 2016 because the power and the internet are always cut off at 23:30 UTC+8 in my school. But this contest is next to the holiday so that I can fight again! I wish I won't forget the feeling of algorithm competitions.

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

666 is the sum of the first 36 natural numbers and thus it is a triangulal number.

Notice that 36 = 15 + 21; 15 and 21 are also triangular numbers; and 15^2 + 21^2 = 225 + 441 = 666.

What we see here? Triangles in the perspective. We must go deeper! Do not you think it's like this?

The largest pyramid in Egypt is the Pyramid of Cheops (IV Dynasty), the Pyramid of Khafre (IV Dynasty), Red Pyramid, Sneferu (IV Dynasty).

(IV + IV + IV) : 3 = 4

In the perspective appearance of divisions 4 officially confirmed.

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

    666 is also a special and popular number in China. When we Chinese see something is so cool or so amazing, we will say it is "666" or "66666666666"(very 666). This special meaning of this simple number begins just in these years. Similar with 666, 233 is another special and popular number in China, which means "LOL" -- Lots Of Laugh. If we Chinese see something is funny or ridiculous, we may say "233" or "2333333333333333333333" (very 233).

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

No t-shirts for top-x competitors

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

yesterday my team ended first in our university ACM qualifications, so I hope to carry that achivement in today's round :D

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

    Congratulations, was Qwerty your team's name???

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

      (1)The team that ended first was named Qwerty. (2)He was in the team that ended first. From (1) and (2) we can see that his team was named Qwerty.

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

      Thanks, yes it's Qwerty from Tishreen university :D

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

my first contest after a long time I just hope I do this good

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

Since everyone's sharing their thoughts about the contest I'm gonna share mine too. 3 contests ago I was thinking if I make it in top 200 I'm gonna become purple again, but I failed. So 2 contests ago I was thinking if I make it in top 100 I'm gonna become purple again, but again I failed. So before previous contest I was thinking if I make it in top 50 I'm gonna become purple again, but yet again I failed. Today I need a place in top 5. Wish me luck!

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

    Good luck.

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

    good luck dude :) , i need place in top 1 to be purple :3 :D

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

    haha, I need place in top 1e-3 or better to be purple :P

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

      প্রিয় গ্রাহক বায়োমেট্রিক পদ্ধতিতে সিম নিবন্ধন করে ১৯ টাকা রিচার্জ করলেই আপনি হতে পারবেন purple. মেয়াদ ৩ দিন।

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

        মাত্র ১৯ টাকা !!!! o.O তাতেই Purple :O :O

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

        MR Airtel, Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you. char c='F'; char c2='*'; cout<<c<<c2<<c2<<'k'<<" "<<"OFF"; {sorry everyone for the disturbing comment but I feel we have to be respectful to everyone. We[bangladeshi] are just destroying our reputation.]

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

          You know you are almost becoming as much as annoying as the airtel guy. Leave him be and he will lose interest. You don't need to reply on each and every one of his comment

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

    how long it will take me to be purple ??

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

      depends on you

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

      I will be blue before August! Fingers crossed! >_<

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

        It doesn't feel any different ! It's just a color.
        P.S : I want to be purple before August XD !

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

          I know that but I feel that I can solve Div2C but I am unable to solve it because I start hacking after solving Div2B which takes half hour to one hour and most of the times it's useless. I feel pathetic about this. That's why I feel I am not where I should be.

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

    just don't think about getting rating or your rating wouldn't increase ! well thats totally true for me whenever i think about rating i get my solutions failed so just code without any worries

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

Finally a chance for me to get back in Div2 :)

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

    Me too. Fingers crossed.

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

    You can do it :D

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

      And I did it :P

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        • Look on the bright side.
        • What’s the bright side?
        • You can be the winner of the next Div2 Round.
»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it

div.2 E is div.1 D
such a usual contest

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

    That's because div1 C and D share the same full point -- 2000. So it is to say, they think div1C and div1D have the same or similar difficulty.

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

      On my mind the difficulty of problems div1C and dic1D is different for div1 and div2 participants. It is about obvious the problem D is harder, because there tricky cases there. But for div2 participants who not familiar with combinatorics it's about impossible to solve problem div1C while they can come up with the solution for the problem div1D (it is not require some specific knowledges). So I decided and the guys are agreed to give the problem about four points to div2 round.

»
8 years ago, # |
Rev. 2   Vote: I like it -129 Vote: I do not like it

CF and its overcomplicated problems are stoooopid! Who needs such hard problems in their life? They making quantum computers and soon all these precious algorithms will become useless. They make fast processors and cheaper memory, and array sizes can be as huge as anything. Any average billionaire can't solve even a div2 C yet they're billionaires. Seriously, what are we doing here? I am never coming back here. My last comment on CF ever!!!!!!

I request my account to be permanently deleted.

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

    before leaving, can you tell us who you are(your name/organization/..)? I can't realize whom to miss.

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

    Finally. I was getting tired of your shit in every thread.

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

In Div. 1 D there is a sentence in the problem statement.

"Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1."

Does this not go against the philosophy of hacking, which is that any hacking contributes to the best possible set of test cases, and that any incorrect solution should be hackable? There can be solutions you know are sure to fail system tests, but cannot be hacked by any test case (for example, TLE). This seems to implicitly states that the problem setters believe their test cases are best possible and do not need contribution from participants.

However, an easy fix could be to change all the system testing to have t = 1 so that hacking and system testing are identical.

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

    I guess that for this particular problem testing the speed of the solution can be easily done with the tests from problemsetters. And the hacking tests are used for checking the correctness. The other reason is, perhaps, that it just takes too long to check the correctness of the answer provided by the solution, hence the limitation:)

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

Aaah, this C is so awesome but I couldn't finish it on time :( We can store the states through every sqrt(100000) numbers, right?

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

    Actually we can use the fact that there are only sqrt different lengthes.

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

    Formula for this problem: , where k is the length of s.

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

      It seems that I'll get TLE :)

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

      Why does this formula work?

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

        It is derived from recursive formula: f[n][k] = 25 * f[n - 1][k] + f[n - 1][k - 1]. That is similar to the LCS problem.

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

          It is a two-variable recursive formula, how can you solve it?

          I just know how to solve some simple forms with one variable such as the Master's theorem form (in Introduction to Algorithm). Can you recommend some mathematical resources for that too? I think it will be very helpful for everyone.

          Thank you.

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

why this hack failed? (Div2A)

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

    How to solve A? >_<

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

      I had deja vu, when I was reading the problem. You can read about the idea here.

      I will summarize very abstractly:
      1. You need to convert to the same dimensions. That is, you need to convert the speed of gaining new water (because of the rain) to milliliters (because drinking speed is also in milliliters): ee = c × e.
      c — is some coefficient.
      2. The whole speed of loosing the water from a cup can be expressed as v - ee milliliters per second.

      You have some amount of water from the beginning W milliliters and you loose it with the speed v - ee milliliters per second, so the time you have is:
      t = W / (v - ee) seconds

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

    The relative error was less than 10^-4.

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

What's wrong with Div2 D's TL? I just spend 30mins to debug. So desperate to optimize some loop and vector's push_back, AND IT PASSED PRETEST!!! It sucks.

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

    yes same thing here but i could n't correct it because there wasn't any time!

    very bad sence!

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

Very hard to read problem statement. I could solve problem A if problem statements were a bit more readable...

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

    yes i had the same the problem for A ! without the examples there was no hope for me !

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

    My apologies for that :(

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

      I didn't see the words "in a row" and I tried to solve it for almost the whole contest only to found it not solvable at all...

      Maybe I should read the next problem instead of stuck on this one.

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

It's been so long without a contest I forgot what it feels like...it feels good. I hope everyone has done good.

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

Geometry kills me in contests. I gotta get better at it.

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

:3 :3

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

How to solve Div2 D / Div1 C ?

None of my ideas ended up fast enough

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

    The way I did it was I first did N BFS's to determine the all-pairs shortest paths. Then I made two matrices and put in the first one sorted lists of all the distances (and which cities they were from, courtesy of multiplying by 10000 and adding the city) to a given city and in the second one a sorted list of all the distances (and what cities they were to) from a given city. I then looped through each pair of cities with nonzero distance (these will be the middle two cities in the path), and for each of those pairs I went through the largest three distances from the second city and to the first one. If any of the cities were the same (or the distances zero) I didn't consider that combination (hence why I needed the top three cities in each case). I printed a set of cities with the maximum distance given these conditions. Overall this runs in O(NM) time.

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

      Oh I see, ty

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

      O(N^2logN) actually.

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

        del

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

          Do You mean O(N^2) ?

          Yes you can do that by simply instead of sorting keeping a list of the top four cities as you won't need more.

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

            Turns out you don't need more than three, since the distance to a city from itself is always zero (and thus, anything lower-ranked than that will be a zero distance as well and will be discountable as a possibility)... leaving you with only two possible conflicts for each list.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Python module "itertools" rocks in Div2E. Hope I won't get TLE or some disgusting WA case I didn't notice. Edit: Oops, actually, there is such a case:

1
0 0
0 3
3 2
3 5

My answer:

2
0 0
0 3
3 0
3 3

Right answer:

1
0 1
0 4
3 1
3 4

And it isn't covered by pretests...

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

What is the solution for Div2 B? I sorted and took minimum of absolute of ( Prefix_i * 2 — sum + 1) .

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

    max(maxx-sum+1,sum-maxx+1) , where maxx- maximum element, and sum is sum of all other elements

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

      It is always "maxx — sum +1"

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

        I also do not see a proof. I think it works because it is impossible to form a polygon with what is given.

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

          Yes, since it is impossible to form a polygon, there must be a side such that its length >= sum of other sides. The optimal way now is to build a triangle with its base as the larger side, the rest sides combined together to a single side with a zero degree angle to this side. So third side would be (total length — sum of remaining sides). But this triangle has zero area, so we need to lift the middle vertex just so that the new side's length increases by 1.

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

      Fortunately my solution does that LOL.

      I didn't knew why my solution works but I was trying to build a triangle, I thought of taking up the maximum element only but I couldn't come up with the proof for that either so I checked whether my solution passed the pretest or not.

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

    I sorted the array, then subtract maximum with first n-1 terms and add 1. Couldn't prove it.

    Source

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

when will the sytests start ?

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

DIV 2 D(World Tour) involves finding strongly connected components along with topological sorting like tarjan's algorithm right? I just got there but couldn't figure out how to proceed further. Any ideas?

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

    Use bfs on all nodes to find All Pair Shortest Paths.

    Basically my idea is for each pair (b, c), find (a, d) such that (a, b, c, d) are distinct and d(a, b) is maximal and d(c, d) is maximal. (use set or something similar for that)

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

Please don't start system testing 1 hour later like the last contest!!

»
8 years ago, # |
Rev. 2   Vote: I like it +109 Vote: I do not like it

Hello, my name is Alexander, and I like to write things like this (sorry for quality):

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

    Writing

    if (ans > r) {
        ans = r;
        ...
    }
    

    saves symmetry. Symmetry saves you.

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

In Problem C Div2 ... I just want to know what is the importance of this sentence "The only restriction — it is not allowed to append the same string twice in a row."

for example if I have "xxxxxabab" I cant put ab in the output as I can do like that --> "xxxxxab" — "ab"

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

    In this case, xxxxxbcabab you can't get bc as output!

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

    Suppose you have the string "xxxxxghiabab", note that the only way to obtain the suffix ("ghi") is doing: "xxxxx"+"ghi"+"ab"+"ab". But, with the restriction, it is impossible to obtain that suffix (because you put the suffix "ab" twice in a row).

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

How to solve div1D? I thought at brute force fixing the direction(OX or OY) and the order othe vertices in the square. After this we get a system of equations but the problem is that it's not uniquely determined. Still, I am pretty sure that we can have at most one free element(the others depend on it), and I guess that now, iterating this free elements throught the integer values that he can take, we get a convex function, so we can ternary search. Unfortunately I am not able to prove the convex function part and there is one more problem with the integer restriction because I'm not that sure that for any fixed integer value we get all the values integer, so the function won't be defined on Z so it doesn't work anymore. Can someone who thinks he solved it tell me how?

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

    The editorial will be posted today or tomorrow.

    As a writer of this problem, I'm also very interested in a solution with binary search.

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

    If you know which vertex is, say, the top left one, the direction it will go and an upper bound on the time it has, you also know the segments of possible coordinates for top and left sides of the square. Intersect these segments using the information from all points. Now you can find out the segment of possible values for horizontal and vertical dimensions of the square. These two segments must have a common positive element.

    So, brute force the permutation, brute force the directions, binary search on the time (which is unnecessary but makes things easier) and intersect some segments.

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

      It seems nice and I'm sure in this way it can be done. Still, I don't actually understand what do you intersect. After brute forcing that stuff(I also did this thing) and binary searching the maximum change, you get some segments, knowing that on the first segment the upper left vertice can be found, on the second the upper right, and so on. But How do you actully deal with the remaining problem? It seems possible, but I can't see how. Can you please explain me more thoroughly?

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

    Wrong solution was here before;)

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

      Wow how stupid I was. In the cx=cy=2 case, I thought that it's impossible to find a solution and it was actually the easiest case. In this way, the code was much easier to write. Thanks :)

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +15 Vote: I do not like it

    17578532

    Run the following solution once, swap coordinates, run it once again.

    Create sets X and Y where X denotes a set of x-coordinates from the input. Iterate over that x1 < x2. Iterate over . Assume that we already have coordinates of 3 sides and run a function check_sq(x1, x2, y, y + |x1 - x2|) and also check_sq(x1, x2, y, y - |x1 - x2|). This function should check 4! possibilities of assigning input points to 4 points (x1, y1), (x1, y2), (x2, y1), (x2, y2). Check my code for implementation details. Also, it's possible that we know only x1 and x2, without knowing any y value, e.g. for test:

    5 0
    10 0
    5 100
    10 100
    

    We know x1, x2. Let f(y) denote a function that returns the answer for check_sq(x1, x2, y, y + |x1 - x2|. This function is maximum over 4 functions of form |y - const| so it's also strictly bitonic (it has form const1 + const2·|y - const3|). So, we can ternary search the optimal y, checking the value with already created function check_sq().

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

      Very nice explanation. I've just got AC and event though I wrote about 190 lines, they were very easy to write (about 20 minutes). This solution makes me like the problem. Thanks!

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

I am not good at English so i don't understand div2 E Also, i spend too much time to understand div2 D

I think i should study English Hard T.T

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

    I'm also not good at English but I think after a year of training and reading problems, you can understand 99% of problems with simple translator.

»
8 years ago, # |
Rev. 3   Vote: I like it +35 Vote: I do not like it

Waiting system test is like waiting prison break season 5.

you know the end will be shit , but you still waiting -.- .

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

    system testing is over , it took less than a minute

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

      and the end is shit -_-

      I failed in B+C and got D accepted

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

    It's easy. see this: 17584300

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

    Dynamic programming from right to the left, storing True or False for every suffix of length 2 or 3 (can this sequence be a suffix or not).

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

      Can you provide a code? I was thinking about that but I didn't know how to code it

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

        You can see my submission here, but I suspect you don't understand Python (here is the information about slices and indexing in the string), here are some comments:

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

Hey, My code fails in sys test 42.. but it gives the correct answer on my system. I have even handled the case it fails on, in my code. Can anyone pinpoint the issue ? Solution link:

http://codeforces.com/contest/667/submission/17577331

Sorry for the mix up, I took jury's o/p as participant's o/p..

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

For div1c, I derived the mathematical formula which runs in 100000 * 100000 — and used some tricks to prune the runtime for half. I was very nervous since I thought it might fail. but happily, it passed systest (in only 2.4s)!

Am I the only one who used pruning?

http://codeforces.com/contest/666/submission/17577445

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +23 Vote: I do not like it

    This is incorrect solution. Test: 1e5 string(5e4, 'a') 2 1e5 ... 2 1e5

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

      I'm aware of that data, and after submitting C, I tried to run that data at custom invocation — but I failed to run it (idk why, but it didn't work). so I just hoped for a fast calculation + easy testdata :)

      Whatever, pruning is just pruning :)

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

      You are right.

      It is our fault that there were no such cases in testset. We are very sorry for that. Testcases are added so solutions like yours will not pass in upsolving. However, competition result will not be rejudged since it is considered to be a bad idea to cancel AC after final results are published. You should feel lucky since your solution could be hacked, but it was not. Sorry again.

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

    There are only at most different lengths given the sum n, so you can reduce the complexity to .

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

Can someone please tell me what is wrong with my answer?

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

UDP: Sorry, I have found the ans.

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

Hacking case for div-2 C is aaxaxabbabbb. many solution with 1D dp failed at this case.

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

Can anyone tell me what went wrong? Solution A

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

    Try to change the value of PI from 3.14159 to acos(-1.0).

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

    You better not set precision.

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

      I tried using %.6f and it worked. setprecision was the reason I got it wrong!

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

In Div.2 C, I mistakenly thought a suffix sequence "aa" -> "aaa" -> "aa" is invalid. hahaha.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I tried to hack div2.Problem B.Coat of Anticubism of some users with test case

5 8 4 3 2 1

but it said invalid input, but why?

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

    In input statement, "It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has."

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

    Let's sort them first. 1 2 3 4 8.

    Now if we add the first 3 rods we have 4 6 8.

    We can construct a convex polygon with side 4 6 and 8. But the problem says that it is guaranteed that no convex polygon can be construct by the input.

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

I used bisection to solve Div2A. Couldn't find an easier solution -_-

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

    me too :p no need to think hard for the right formula , just get it right

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

OK! it's now two contests in a row, getting WA on pretest 2, which is in the samples!!!! This is really getting embarrassing :(

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

    The subjective and easy to lost points :)) :)) Sometimes me too :(( :((

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

      and lossing 226 places in the standings :(

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

Proof that in Div2B it is sufficient to make each side less than sum of others: Let the greatest side be of length d. Then split all other sides into two categories with nearly equal sum of lengths: let us add other sides in length decreasing order one by one into the category with smaller sum of lengths. Then in the end the sums will differ not by  ≤ d, with equality only in the trivial case when all sides are d. Then we can construct a triangle from d and concatenated sides from each of the categories, because all three triangle inequalities are satisfied.

»
8 years ago, # |
Rev. 7   Vote: I like it +22 Vote: I do not like it

Many solutions on Div2A would fail on the hack test by user sid02
hack test is: 2 5 3927 1250
correct answer is: 1710.545730564287
for example:
17576065 output is: 1575.38
17569724 output is: 1570.796000
17574966 output is: 1693.15
17570584 output is: 1570.8
17569909 output is: 1698.1582
17571073 output is: 1698.1581622
I was wondering why it wasn‘t added to the final system tests...

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

    All the successful hacks should have been added. If it wasn't it means there was a bug and that task should be rejudged.

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

how is NrootNlogM complexity passing for E in 2 seconds. its way more than 10^9 operations.

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

When will the editorial be posted?

BTW how to solve div2/C ?

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

    They will be posted as soon as possible. Div. 2 C is simple DP. Assume we reversed the string. Then DPlen[i] — is it possible to split s[1..i] in suffixes in such a way that last would have length len. Then you can use following formulas: . Similarly

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

      Completely ****ed up with this problem..... thanks man!

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

      Does this case "zzzzzpbpppb" exist an ambiguity in the meaning of DP? The first "pb" (from left to right) cannot be chosen because there is another "pb" on its right, However its DP value is true.

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

        But it can be chosen. zzzzz|pb|pp|pb is correct partition.

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

          How? pb is repeating here.

          Is this valid partition? zzzzzpb | pp | pb

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

            Yes, this partition is also valid.

            The only restriction — it is not allowed to append the same string twice in a row.

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

              zzzzzpb | pp | pb is valid

              but

              zzzzzpb | pb is not valid

              because pb is "twice in a row" in second case.

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

                The appended strings can't be twice in a row. First "pb" is part of the root, so it is OK!

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

              Oh I misunderstand “twice in a row”:(

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

              I just misunderstood the statement too... Btw,how to solve the problem if removing the condition "in a row"? Also DP?

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

                Hm, I don't know actually. Does anybody?

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

Can someone help me in finding out why this gives WA for Div2 D ?
Thanks!

»
8 years ago, # |
Rev. 4   Vote: I like it -29 Vote: I do not like it

There is one thing I would like to officially complain about. I didn't carefully read the statement of the task A and forgot to print YES before printing the result. I wouldn't mind subtracting points for an incorrect submission, but if the same thing happened to somebody who prints incorrect version of NO, like

NO

0

there will be no punish, because that would be caught by the first test and this is not counted as incorrect submission. This way people who are lucky to get WA on the first test case, will get away with it.

Hence I kindly ask to change this rule: either count each incorrect submission or don't count incorrect submissions on all the tests from the task statement. Otherwise the order of tests influences your final score, and that factor shouldn't be taken into account at all.

»
8 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In my solution (Problem D), my code is giving runtime error, but, when I comment line 121 (resp[0]=a) not gives? someone understand why it happen?

runtime

not runtime

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

Editorial??

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

What is the answer for this case in Div.2B?

4

1 2 3 4

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

    3

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

      Shouldn't it be 1? If we take 1 + 4 as a side and 2 + 3 as the other side, we have two sides of length 5. Then we only need a size of length 1 to build a triangle.

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

        It's invalid! We can make convex polygon using sides 1, 2, 3 and 4 because 1 + 2 + 3 > 4.

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

Why is there still no editorial in English? Is an English editorial going to be published at all? BTW, I think you should organize more rounds, the problems from this round that I managed to solve during and after the contest are awesome! :)