PrinceOfPersia's blog

Codeforces Round #459
By PrinceOfPersia, history, 7 years ago, In English

I'm honored to announce that Codeforces round #459 is going to take place on January 29th and Reyna and I are the problemsetters of this round.

I'd like to thank keyvankhademi, AlexFetisov, winger, Belonogov, cyand1317 and demon1999, AnPelec for testing, KAN for coordinating the round and MikeMirzayanov for the great Codeforces and Polygon platforms.

The main characters of the round are Stranger Things characters.

The scoring distribution will be announced soon.

Good luck and have fun.

UPD0: The round is over, we hope you enjoyed it. Editorial will be posted soon.

UPD1: System testing is over, congratulations to the winners.

Div.1 winners are:

  1. jqdai0815
  2. FizzyDavid
  3. ainta
  4. aid
  5. Swistakk

And Div.2 winners are:

  1. Omar_Morsi
  2. Chaarzeh (Interesting :-?)
  3. magicalCycloidea
  4. Tanzir5
  5. UoA_Kanade

The editorial will be posted in a bit.

UPD2: Here's the editorial. Also please help me and Reyna do better next time by filling out this form.

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

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

I hope the problem statements are as short and concise as the announcement. Good luck to all!

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

Have been waiting for one of your round for a long time!

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

What is the significance in tags princeofpersia?

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

Be Careful !!

Your text to link here...

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

please don't include spoilers in the statements ...

I haven't seen the series yet

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

RIP rating in advance!

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

PrinceOfPersia is such a cool handle.

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

I hope, This round will make my handle Green !

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

On a scale from 1 to 10 , this round is gonna be Eleven

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -45 Vote: I do not like it

He didn't mention if the contest is rated or not.

UPD: I know that all #Codeforces rounds are rated for Div/2 by default but it should be mentioned and putted in bold like any other contest announcement.

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

    What's need announcement for it. it will occur unexpectedly. :D :D

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

      You are right. But we should not downvote 'is it rated' questions as it is not mentioned

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

Waiting !!!

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

Wow!! At last picture-based problems are coming after a long time. :)

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

Fun Fact:

Mille Bobby Brown is dating the biggest douche on earth(Jacob Sartorius)...

If you don't know who that guy is, just don't watch a song called "sweatshirt" by him.

I REPEAT DO NOT LISTEN OR WATCH THE SONG SWEATSHIRT BY JACOB SARTORIUS.

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

    Why are all comment sections on here filled with inane crap?

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

    Damn, codeforces is the last place on earth where I expected to learn this, but it is kinda a fun fact. The more you know.

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

Totally Tubular!

Good luck everyone! xD

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

Is it rated?

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

    All official Codeforces rounds are rated by default. They would have mentioned it, if it is unrated because of any reason.

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

stranger things contest means stranger things on contest?

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

The author of the contest makes #406 Round. There were really cool problems. Hope it will be also helpful and interesting. High ratings for everybody!

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

I have watched Stranger things but I still don't recognize the character whose picture is in the post!? :')

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

i hope Dustin's rrrrr exists in the round

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

I got a reason to watch Stranger Things :)

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

Brace yourself, tough problems is coming...

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

Took me a long time to recognize Eleven in the post having waffle

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

I hate kids.

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

So this tv show has kids as main characters and you want me to believe it's not shit?

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

    This is shit

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

    Yes it's not shit. And that is because unlike many stories that feature kids, Stranger Things would not work if they replaced the kids with adults. For the story to turn out as it does, it is necessary for the protagonists to be kids. As summarized by Jared on Wisecrack (video spoiler alert),

    "..the kids don't save the day despite being kids, they save the day because they were kids.."

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

It has been awhile before we got a rated contest

Waiting ❤

UPD: Very bad contest and my rating will decrease. Why C/Div2 is harder than usual?

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

I'm waiting an amazing contest!

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

Cant wait for the Stranger Things theme, hopefully the questions are as good as the show :)

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

map<map<int,int>,map<int,int>>M; How to access the map ?

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

    why did you comment that here?

    Any way you can access the map by another map

    map<map<int,int>,map<int,int>> M;
map<int,int> S;
M[S][0] = 1;
cout << M[S][0];
    → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

AMD is back :o

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

If you are planning to include stranger things themed pictures in problem statements, please use small low size pictures.

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

What's the compiling command for GNU C++?

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

it is gonna be data.. wait for it ..structure contest

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

    preparing a robust version of HLD :D

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

    I came here to comment this, now I’m leaving.

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

pls be short and clear

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

ahhh.....rated ;)

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

All the best for the round 4 + 5 = 9

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

Well,now my rating is 2017,I hope that I can get a rating of 2018 after this contest...

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

I hope this is a great contest!

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

scoring distribution ???

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

    I am also waiting for the same.. Hope for the nice problemset. As expected from princeofpersia

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

The scoring distribution will be announced soon.

What does 'soon' mean?

UPD:Sorry, I didn't see this question has been asked

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

Stranger Things are going to happen

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

Scoring???

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

For Div2, I don't think that problem distribution has been in correct way. :(

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

Damn that trigraph in Div2C pretest2

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

I spotted a small lore inconsistency in Div2D:

"Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on... Since the game could take a while and Lucas and Max have to focus on finding Dart, they don't have time to play."

Are they playing or are they not playing? Problem is very unclear about this. Make the round unrated. (JK)

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

problem C is very tough.. this contest is not meant for div 2!! I downvote!

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

Div2/D If our graph will have consisted from one cycle and characters on the edges will be the same, will they play infinitely?

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

My rating is about to go Upside Down...

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

Am I the only one who thinks Div2D/Div1B was a little bit easier than Div2C/Div1A?

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

    no

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

    i thought C was easier.. maybe im not good at graph problems :)

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

    maybe

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

    Div1B was straightforward, Div1A was pretty tricky and I needed to think about it for few minutes and decided to go with a bet that seems fine to me but I didn't prove it carefully :x

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

    yes , but both traditional

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

Seems like in both divisions D is easier than C (considering the number of successful submissions).

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

    Because it is a classic game theory problem.

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

anyone can explain D.. I spent 1 hrs, but i can't find the answer

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

    Use Dynamic Programming

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

    dp[100][100][26][2] The 2 is for turn Emulate the whole situations. O(N^3C) time complexity where N is # of vtx, C is # of alphabets

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

      Note that you can drop 2 easily. That is, to have dp[a][b][c], by storing whether the current first player wins when he is in vertex a and the second player is in vertex b.

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

        Good advice. Always dp[][][][0] = !dp[][][][1]

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

    I used an array state[A][B][x] to store all the possible situations, where A is the position to move first, B is the position to move second, and x is the limitation(i.e. only edges whose weight >= x can be used). Then all these nodes form a game tree. then update each node in topology-sort order, i mean, from leaves to root and make sure you visit all children nodes before you visit a node itself. Then the problem is simple. if there exists a child of a node is "first move to lose" then this node should be "first move to win", otherwise "first move to lose". All you need will be state[i][j][0].

    I'm still waiting for system test, hopefully I'll pass :P

    UPD:It passed now XD

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

    now i understand it. thanks for all help!

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

Very nice contest and nice pretests :D

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

That moment when I made the best performance in Div2A/Div2B, then got stuck for the next 115 minutes...

P/s: Can anyone give me a hint with C/D?

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

    for C: you will count which starts with ith character let number of ( : a, ? : b, ) : c if c>a+b, then it means if we change all ?s to ), it is impossible so, it is always impossible!(for example, (?))) is always impossible!)

    similary, we can think something like a>b+c, (for example, (((?) )

    Hope my comment helped you..

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

      Hmm, but what about cases when the order of the characters matters?

      Like, "(?" is a pretty string, while "?(" is not (however following characters may make it pretty, i.e. "?()?").

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

        first, ")?"(which is not in your examples though) can be shown impossible by my first comment. and lets check "?(" these kind of things, which is impossible because there are too many '('s at the right. choose one variable a=0 from front, if there is (, add 1 on a. if there is ) or ?, we can decrease 1 on a. But if a=0, we don't have to decrease it, since we can choose '(' rahter than ')'. if it is ), then we can think from right of it. So if a=0, add 1 on a, else, decrease 1 on a. if variable a is negative, it means it is impossible.

        now we can verify "?(" these kind of things.

        hope i made you understand this :) have a nice day!

        UPD: edited a little bit!

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

          Hmm, seems like I'm getting your idea — prioritizing the opening bracket.

          I was complexifying my own work by judging the '?' characters separately, therefore I encountered a whole variety of bugs without a proper solution. Turns out it was so simple.

          Many thanks! ;)

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

    For D, since you can get every possible state, just see the states that each state can go to, if any of them is winning, then the current state is winning, losing otherwise.

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

      After reading your hint and a few more comments, I'm getting it now.

      Heck, no wonder some says it is easier than C. Well, I can't blame myself anyway, anyone has his/her own bad days/periods.

      Thanks for the support! ;)

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

Div2C, I stuck in pretest 3/7 :(

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

Isn't Div. 1 D a special case of this?

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

    Also, it has appeared on topcoder: https://community.topcoder.com/stat?c=problem_statement&pm=13369

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

      Are you sure this is correct link :P?

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

        Oops I accidentally deleted a character :P

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

      I'm really sorry... I wasn't aware that it's been given before until now. I'll avoid making problem with short statements without researching thoroughly. I hope Codeforces community is kind enough to forgive me and give me tips to avoid such mistakes in the future.

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

        No worries, it's understandable, problem collisions happen every now and then. I think it's still a bit hard to search for this specific problem unless you've seen it before.

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

Any idea what could be the test case 4 for div2 C ? I was stuck on this throughout the contest :'(

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

    No idea, but I have a hack for your code: ())?

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

I am in Love with Problem D, thanks for the amazing problem :D

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

can't understand the problems.... want more explanation of the sample case...

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

I think that is why so many participants passed div1.D...:)

div1 D

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

Is there a normal solution for Div.2 C that has complexity like O(len^2)? My only thought was to use bitsets with O(len^3 / 64)...

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

any idea for Div2C? It seems very tough for me :(

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

    For each starting position, calculate the upper/lower bound for each ending position. You may reduce the time complexity if you do that in left to right. If the upper goes negative, you should stop. Otherwise, just check that upper >=0 which means there are some good solutions. (No matter what they are)

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

      Clearly speaking,
      case '(': upper++,lower++ // case ')': upper--,lower-- // case '?': upper++,lower--

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

        What is the use of lower? Should it be 0 at the valid end positions?

        Does this work for: ????))))(((()

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

          In case of the lower going below 0, you should adjust it as 0. It forces '?' to be ')' in some cases. In case of '()?)', ? should be '('. After fixing lower to be >=0, it could fluctuate around 0 and finally affects to the desired answer.

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

            Its not clear what upper and lower bound are actually counting?

            Is it counting length of the pretty string?

            In that if (( is the input string upper will be 2. which >= 0 . But that's not valid string. I am clearing missing something here, don't know what.

            Also: Is it a standard problem as some have solved it in 4 mins?

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

              I think I didn't give you a full explanation.
              But in case of that, lower is 2.
              The key idea is that if lower ≤ 0 ≤ upper, we can always expect that there exists some solution.

              In addition, for ??))))((((), let me consider the cases only starting from the first position,

              ? ? ) ) ( ( ( ( )
              lower 0 0 0 0 1 2 3 4 3
              upper 1 2 1 0 1 2 3 4 3
              solution — y — y — n — n —

              (we can only expect pretty one with even length)

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

                The key idea is that if lower ≤ 0 ≤ upper, we can always expect that there exists some solution.

                How does someone come up with that idea? Why this always works?

                What are actually upper and lower.. seems like top and bottom end of a stack which can be successfully emptied if its a balanced bracket, perhaps not.. still confused what the heck is upper and lower magic

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

                  I came up with the stack, right. They denote possible range of stack size when you check the given string of parenthesize is correct, even thought it is not tightly (lower)bounded near 0.

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

        nice solution after reading your code:)

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

Sooo, I spent 1.5 hours writing approach for d1E, it was about 330 LoC at the end of contest and it was not even nearly enough to get something working ;_;

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

    +1 (spent 1.5 hours on ), thought I found a small mistake which I couldn't fix.

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

    Same story.

    I tried to solve for all length ≤ K separately with hash and for strings having length > K with centroid decomposition but I didn't even came to writing second part. I'm not even sure my solution is enough to get accepted.

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

The contest should be unrated because you did not announce the scoring.

Trying to save my rating.

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

Problem A Div2 was inspired by jqdai0815

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

how to solve D?

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

    You can use topsort. Than start back from the nodes and calculate next dp values : dp[currentplayer][previouscharacter][firstnode][secondnode].

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

    Notice that the value for k = 0 is the number of spanning trees of the complement of the input tree. This can be computed by the matrix-tree theorem (https://en.wikipedia.org/wiki/Kirchhoff's_theorem).

    Using https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem#Explicit_enumeration_of_spanning_trees, we can know that if we compute the determinant of the Laplacian matrix of a complete graph with weight X for edges in the input tree, and Y for the other edges, we get a polynomial where the coefficient of XaYb gives us the number of spanning trees of the complete graph with a edges inside the input tree, and b edges outside (Since spanning trees have n - 1 edges, a + b = n - 1). We can compute this polynomial by interpolation.

    Because we need to evaluate in n points, and the cost of each evaluation is O(n3) (or better with faster algorithms for computing determinants), the complexity is O(n4)

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

      Your solution sounds much more fit to Div 1's.=D

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

      Why is given graph a tree then?

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

        In order to allow other solutions, quite clearly :). Mine heavily uses fact that it is a tree.

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

        Because that is not the only solution. Mine works only on trees and likely, so does the official one

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

        My solution is different I guess. Although I think that can also solve the problem for a graph. One of the testers had a similar solution for the problem (I didn't think of the graph version though). He also reduced it to n ^ 2 for trees. We didn't change the problem because we thought it would be too hard.

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

          If you are allowed, please share the novel O(n^2) solution.

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

            I'll make a place for it in the editorial, although I don't completely understand the solution.
            Here is the version winger told me.
            __ It's based on generalized Kirchhoff's theorem: if we take Laplacian matrix with x for edges in the original tree and 1 for edges not present in it, it's (polynomial in x) minors will be the answer.
            So, let's calculate this minor for every x in [0, n) and interpolate to find the answer. To compute the minor in linear time, notice that it can be computed as det(D-(x-1)*F-E), where E is (n-1)x(n-1) matrix on ones, D is some diagonal matrix and F is incidence matrix of some forest (produced by removing a vertex from original tree). It can be computed with a tree-DP in linear time.

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

              Look forward to the editorial for a detailed solution. Thanks, @Reyna.

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

              As the DP you described involved polynomial multiplication, we can use interpolation to get O(n3) solution.

              However, O(n2) seems to be mysterious for me so far.

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

                Polynomial interpolation is O(n ^ 2) from what seems to be on the wikipedia page XD.
                So we just have to calculate the determinant of det(D — (x — 1) * F — E) where E is an (n — 1) * (n — 1) matrix with all 1's and F is the adjacency matrix of a tree and D is diagonal. OK now let's try to calculate their determinant by choosing a permutation and a 3 ^ n (actually n — 1, but just assume the tree has n + 1 vertices) representing if the (i, p[i]) is chosen from E, D or F * (x — 1).
                Fact: Let's look at the determinant as partitioning the graph into cycles and assigning each edge a tag (which can be 0, 1 or 2 depending if it's picked from E, D or F * (x — 1)). The determinant will be the product of the edges (for edge (u, v) it would be E[u][v] or D[u][v] or (F * (x — 1))[u][v] depending on the tag). Okay, now I'll claim that we don't use E tags more than once! (sum of those which use E tags more than once is zero, we can prove that by swapping 2 E tags, although the details aren't easy to me). If we use zero E tags, the answer will be only the product of D's diagonal (because trees can't make a cycle). Otherwise It'll be a path with an E tag connecting both ends and all others are loops.
                Now label the vertices with starting time and denote ed[v] as the ending time of vertice v. Assume that we have a path from x to y and their LCA is p. from x to the vertex below p and from y to the vertex below p, they don't affect each other in the inversion (because they're from some px (below p from x) till ed[px] and py (below p from y) till ed[py] and these two segments don't coincide). so only from px to p and p to py affect the inversion (if we have the inversion from the paths below). We can also find the inversion from x to px with dp. I should probably write down these details in the editorial. I just found the solution (with the hints from winger) right now, so I'm not sure about the details.
                Don't hesitate to ask me for more elaboration or explanation.

                EDIT: It's wrong right now... I'll see what I can do to fix it

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

                  When we use zero E tags the answer is sum over all matchings of given tree(because we can still use v->u and u->v edges). I don't understand the last part but it probably gets more complicated too.

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

                  Yeah, you're right, I have to think a lot more now XD (because in the second part I also ignored the matchings and it gets much more complicated).
                  I'll be thankful if winger could explain a bit. I can also share his code if he allows me to.

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

                  Okay, I think it can be fixed with the fact that a swap (which is like (u, u) and (v, v) to (u, v) and (v, u)) changes the inversion parity, so we can just assume that all of them are in their place but keep in mind to multiply by -1 each time we match edges. So we can match the edges or loops in the whole process. It'll complicate things, but I guess it works?

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

                  Well, (u, u) and (v, v) use values from D and the other two use values from F so I don't think they cancel each other out or something.

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

                  Yeah, they are indeed from F, but my point is that they just change parity so we can assume that they are in their place in the permutation after multiplying by F[u][v] * F[v][u] * -1. We have to also update the dp's with matchings which I didn't notice before. They don't change the solution that much, they just make it much harder to code XD.

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

                  Finnally, got accepted with O(n2) solution.

                  Code: http://mirror.codeforces.com/contest/917/submission/37086325

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

                  Wow! Orz! It's actually pretty hard imo XD

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

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

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

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

    That`s not true buddy!! Div2A/B was easy! Yes, C was tougher then regular!

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

A royal contest, Prince + Queen (Reyna in spanish)

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

The problems C+ where really hard.. Cool actually

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

In this contest I found that a code which submitted by other one ( after me) is almost the same as mine. I want to say that I didn't give my code to anyone and I don't like this behavior at all.

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

    Did you use an online IDE or accidentally leaked your password? This happens from time to time and is really strange.

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

      I think someone had access to my account by my mistake.

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

    wich code ?!

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

    The best choice is updating your password immediately, this happened to me last year.

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

      I updated it after the contest. Thanks for your comment.

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

      Wow, going to such lengths for solutions..

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

Memoization is clean for Div1 B: http://mirror.codeforces.com/contest/917/submission/34673801

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

    It's actually strikingly amazing how similar my solution is to yours :D

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

    good understandable code.

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

    You can simplify it further by taking out the 4th dimension of your DP array. If you just store whether the current "first" player wins, and then recurse by switching u and v, and determining that current position is a win if it can recurse into a loss for the first player, or is a loss otherwise.

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

I got Idleness limit exceeded on pretest 1 on Problem D although it runs on my PC and on Ideone and now i got the same verdict in problem A after it passed the pretests !!!

UPD: the same for Problem B

UPD2: they were rejudged , thanks MikeMirzayanov.

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

    Same happened for my Solutions for div2 A and div2 B.

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

    My guess is that it's because you've used "GNU C++17 Diagnostics" compiler, which runs a bunch of debug tools alongside with your solution. They may significantly slow down the solution or even don't work during the contest at all.

    MikeMirzayanov, is it indeed the case?

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

      Sure. It seems it is good idea to hide such compilers from the submission interface in a contest. But allow them on the custom invocation tab.

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

Kareeeee

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

And the scoring distribution is never announced...

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

    Meanwhile the system testing seems to be neverending as well...

    ... even when all submissions were judged.

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

I am surprised that C got 16 ACs and D got 43 ACs. To me it seems that C is maybe not straightforward but kinda standard and easy exercise on matrix exponentiation whereas D seemed to me like a really tough problem. It seems that D was too widely known (but I didn't know it before) and also it allowed both (I guess intended) approach with generalized Prufer codes, dp on tree and dealing with multicounting and also an approach based on Kirchhoff theorem.

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

    C allows both standard matrix multiplication and dp (with some greedy speedup).

    UPDATE: Perhaps I am wrong...

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

      Well, these matrices is also some kind of dp :). But you surely meant something entirely different, can you describe your approach?

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

        Sorry...I might just make an insane comment. But I go with such approach during the contest.

        Thinking of x = 1, if two consecutive stones is far apart, it should jump with some k where c[k] / k is minimized. I guess this can be generalized to x > 1. So we can compute the dp step by step around the stone, and use the above hypothesis to skip large gaps.

        :(

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

          This is not clear yet, but I think you are on to something and intuitively this problem should be solvable without any dependence on n in time complexity. Btw, I see a notable connection between this approach and this P6 IMO 2010 problem https://artofproblemsolving.com/community/c6h356197p1936918 :P (which by the way doesn't really deserve to be IMO P6)

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

            wow! the aops link looks cool!

            Finally I realized that I missed the ``the leftmost pollywog should jump to the right'' part in the statement, which causes (1) I did not solve in the contest (2) invalidate my hypothesis (as we cannot shift x frogs together now...)

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

              Haha, yes xD. Without that condition it is entirely different problem. However your version (without that "leftmost" part) can be solved by solving x^2 subproblems with x=1 and applying Hungarian at the end. Main observation here seems to be that these subproblems can be treated independently because we can get rid of any collisions that would appear throughout whole process by some swapping targets argument. Because this reduces to independent problems for x=1 this greedy optimization can easily be applied in your version and doing k^3 single steps before and after every special point and using only best move between these parts is sufficient.

              I believe similar "depumping" arguments can be applied in original version as well, but it will be messier and code will be harder than doing exponentiation. But we would get rid of log n factor which is nice, but we would get some new factor depending on k which will annihilate this profit.

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

    Maybe there's a similar problem...(link)

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

my first ever B 'accepted', thought that I improving my skills but... the fact is, it was easy......... :-(

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

I suppose I will be specialist on this contest first time. The problem A,B were quite easy that is why almost every participant solve it. BUT MY ONE HACK PLAYS A BIG MATTER HERE!

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

    It's a lesson for you after all.

    I'm not sure what does "my one hack" mean in this case.

    If it was an unsuccessful hack, then a lesson about caution. Do not take ruthless action unless you are 100% sure about that. (I myself regretted such actions several times actually :P )

    If you were hacked, then a lesson about case-handling. Double-check your work before (or maybe after) submitting.

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

      No, I hacked somebody,+100 points have a big impact in the results. Because almost all participants have a near results to each other.

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

        Haha, then good for you. Congrats! :D

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

What is the complexity of the DP solution of D?

Is it O(m*n*26)?

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

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

    A was very much hackable with overflows but its difficult to come up with such cases.

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

waiting for ratings...

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

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

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

jqdai0815's nick... Algorithm from Problem A, isn't it? ^o^

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

Attention! Your solution 34680762 for the problem 918D significantly coincides with solutions PuPpEy/34680021, EliasM/34680268, Aldanyshov/34680302, soohotiam/34680762, kitkat_coder/34684071. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

MikeMirzayanov hey plz. resolve this. I didn't know those guy. u can check our msge.ur code checker is very poor. plz. update this. and update my profile. plz check. we are not same and we are not kelnew each others. plz. it is totally wrong

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

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

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

How can I solve DIV2 C with DP?

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

why this solution get a much greater answer for 917A? I've really no idea

bool match(int a, int b)
{
    if(S[a] == '(')
    {
        if(S[b] != '(')
            return true;
    }
    else if(S[a] == '?')
    {
        if(S[b] != '(')
            return true;
    }
    return false;
}

for(int i=1; i<n; ++i)
        if(match(i, i+1))
            ++ans, st[i][i+1] = 1;

    for(int len=4; len<=n; len+=2)
        for(int i=1; i+len-1<=n; ++i)
        {
            int j = i + len - 1;
            if(st[i+1][j-1] && match(i, j))
                {++ans, st[i][j] = 1;   continue;}
            for(int k=i+1; k<j; k+=2)
                if(st[i][k] && st[k+1][j])
                    {++ans, st[i][j] = 1;   break;}
        }
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Submitted this solution on the contest and got wrong answer on test case 1. But it showed everything ok on my pc. Can anybody help with what's wrong here? :/

http://mirror.codeforces.com/contest/918/submission/34678446

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

    It works if you read n, m using cin>> n >> m;

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

    You say ios_base::sync_with_stdio(false);, but then you mix printf/scanf and cin/cout. can't do that.

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

I am sorry to say that but unfortunately data set of problem B maybe weak 918B - Radio Station

  • For example this case:
  • 2 2
  • main 192.168.0.12
  • replica 192.168.0.1
  • block 192.168.0.1;
  • proxy 192.168.0.12;

check this my wrong solution : 34674890 which was accepted

I am sorry for informing this lately..

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

    not wrong, its just not strong enough to catch your bug. Also, many people had overflow bug in A but since its difficult to come up with a hack we have to settle with systests.

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

What's the point in making such huge problem statements ?

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

https://ideone.com/Gb6GiQ Very good solution for 3-rd task, if anyone needs.

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

Very good round, I really enjoyed it.

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

Div.2 A using regular expression: 34722038 (and B — 34722359)

→ Reply