DarthPrince's blog

By DarthPrince, history, 8 months 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. OO0OOO00O0OOO0O00OOO0OO
  2. FizzyDavid
  3. ainta
  4. aid
  5. Swistakk

And Div.2 winners are:

  1. MeshOmarYasser
  2. Chaarzeh (Interesting :-?)
  3. magicalCycloidea
  4. Maxon5
  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  

»
8 months 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!

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

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

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

What is the significance in tags princeofpersia?

»
8 months ago, # |
  Vote: I like it -46 Vote: I do not like it
»
8 months 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

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

RIP rating in advance!

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

DarthPrince is such a cool handle.

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

I hope, This round will make my handle Green !

»
8 months 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

»
8 months 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.

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

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

    • »
      »
      »
      8 months 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

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

Waiting !!!

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

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

»
8 months 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.

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

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

  • »
    »
    8 months 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.

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

Totally Tubular!

Good luck everyone! xD

»
8 months ago, # |
  Vote: I like it -61 Vote: I do not like it

Is it rated?

  • »
    »
    8 months 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.

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

stranger things contest means stranger things on contest?

»
8 months 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!

»
8 months 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!? :')

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

The comment is hidden because of too negative feedback, click here to view it

»
8 months ago, # |
  Vote: I like it -21 Vote: I do not like it

HYAHNAHAHAHHAHAHAH

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

hahahahahahahaha

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

i hope Dustin's rrrrr exists in the round

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

I got a reason to watch Stranger Things :)

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

Brace yourself, tough problems is coming...

»
8 months 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

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

I hate kids.

»
8 months 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?

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

    This is shit

  • »
    »
    8 months 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.."

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

    yes

»
8 months 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?

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

I'm waiting an amazing contest!

»
8 months ago, # |
  Vote: I like it -27 Vote: I do not like it

CF pe aayegi aandhi, jab khelega anant gandhi

»
8 months 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 :)

»
8 months 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 ?

  • »
    »
    8 months 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];
    
»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

AMD is back :o

»
8 months 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.

»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it -24 Vote: I do not like it

I don't think it is rated.

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

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

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

pls be short and clear

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

ahhh.....rated ;)

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

GLHF :D

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

All the best for the round 4 + 5 = 9

»
8 months 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...

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

I hope this is a great contest!

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

scoring distribution ???

»
8 months 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

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

Stranger Things are going to happen

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

Scoring???

»
8 months 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. :(

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

Damn that trigraph in Div2C pretest2

»
8 months 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)

»
8 months 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!

»
8 months 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?

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

My rating is about to go Upside Down...

»
8 months 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?

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

    no

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

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

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

    maybe

  • »
    »
    8 months 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

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

    yes , but both traditional

»
8 months 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).

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

    Because it is a classic game theory problem.

»
8 months 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

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

    Use Dynamic Programming

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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.

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

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

  • »
    »
    8 months 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

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

    now i understand it. thanks for all help!

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

Very nice contest and nice pretests :D

»
8 months 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?

  • »
    »
    8 months 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..

    • »
      »
      »
      8 months 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. "?()?").

      • »
        »
        »
        »
        8 months 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!

        • »
          »
          »
          »
          »
          8 months 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! ;)

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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! ;)

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

Div2C, I stuck in pretest 3/7 :(

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

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

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

      Are you sure this is correct link :P?

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

        Oops I accidentally deleted a character :P

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

»
8 months 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 :'(

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

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

»
8 months 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

»
8 months 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...

»
8 months 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

»
8 months 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)...

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

    yes

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

    If you are still interested:
    my 36441589 solution is O(len2).

    First, let's do it without '?':
    for each fixed l, iterate by r, maintain "unclosed parens" counter (u).
    Interpret '(' as +1 to u,
    ')' as -1 from it.
    When u reaches zero, +1 to the result.
    When u is negative, stop iterating by r.

    To deal with '?', it's enough to maintain two counters (umin, umax).
    Interpret '?' as +1 to umax and -1 from umin.

    Upd: I found that iriszero already described a similar solution in a comment below.

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

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

  • »
    »
    8 months 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)

    • »
      »
      »
      8 months 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--

      • »
        »
        »
        »
        8 months 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: ????))))(((()

        • »
          »
          »
          »
          »
          8 months 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.

          • »
            »
            »
            »
            »
            »
            8 months 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?

            • »
              »
              »
              »
              »
              »
              »
              8 months 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)

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The upper/lower bounds are for counting the number of unclosed parentheses
              (in other words, the number of '(' for which we have not encountered corresponding ')' yet).

              I also described the idea in my comment above.

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

        nice solution after reading your code:)

»
8 months 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 ;_;

  • »
    »
    8 months 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.

  • »
    »
    8 months 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.

»
8 months 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.

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

Problem A Div2 was inspired by OO0OOO00O0OOO0O00OOO0OO

»
8 months ago, # |
  Vote: I like it -13 Vote: I do not like it

how to solve D?

  • »
    »
    8 months 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].

  • »
    »
    8 months 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)

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

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

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

      Why is given graph a tree then?

      • »
        »
        »
        »
        8 months 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.

      • »
        »
        »
        »
        8 months 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

      • »
        »
        »
        »
        8 months 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.

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

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

          • »
            »
            »
            »
            »
            »
            8 months 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.

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

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

            • »
              »
              »
              »
              »
              »
              »
              8 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

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

                  Finnally, got accepted with O(n2) solution.

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

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

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

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

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

»
8 months ago, # |
  Vote: I like it -38 Vote: I do not like it

  • »
    »
    8 months 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!

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

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

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

The problems C+ where really hard.. Cool actually

»
8 months 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.

  • »
    »
    8 months 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.

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

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

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

    wich code ?!

  • »
    »
    8 months 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.

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

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

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

      Wow, going to such lengths for solutions..

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

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

    good understandable code.

  • »
    »
    8 months 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.

»
8 months 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.

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

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

  • »
    »
    8 months 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?

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

      If this is the case then the solution must fail even the pretests. My solution for Div2A passed the pretests and failed the main tests.

      EDIT : The solution has been rejudged.

    • »
      »
      »
      8 months 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.

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

Kareeeee

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

And the scoring distribution is never announced...

  • »
    »
    8 months 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.

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

      Div 1 not done judging

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

        Hmm then this one is weird... "Final standings"?

        UPD: Got it now. Nevermind then.

»
8 months 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.

  • »
    »
    8 months 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...

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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.

        :(

        • »
          »
          »
          »
          »
          8 months 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)

          • »
            »
            »
            »
            »
            »
            8 months 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...)

            • »
              »
              »
              »
              »
              »
              »
              8 months 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.

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

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

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

Thanks to all organizers of this round, I realy enjoy it, let's hope all rounds would be like this one and even much better.

»
8 months 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......... :-(

»
8 months 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!

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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.

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

        Haha, then good for you. Congrats! :D

»
8 months 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)?

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

  • »
    »
    8 months 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.

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

waiting for ratings...

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

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

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

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

»
8 months 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://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

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

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

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

How can I solve DIV2 C with DP?

»
8 months 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;}
        }
»
8 months 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://codeforces.com/contest/918/submission/34678446

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

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

  • »
    »
    8 months 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.

»
8 months 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 - Радиостанция

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

  • »
    »
    8 months 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.

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

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

»
8 months 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.

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

Very good round, i really enjoyed it.

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

Div.2 A using regular expression: 34722038 (and B34722359)