Vovuh's blog

By Vovuh, history, 10 months ago, In English,

I'm in the middle of the session but I'm still trying to prepare Div. 3 rounds.

<copy-pasted-part>

Hello!

Codeforces Round #527 (Div. 3) will start at Dec/18/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD: I also would like to thank Roman Ajosteen Glazov, Farkhod Farhod_Farmon Khakimiyon and Alex hohomu Poon for help with testing the round.

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Doma_Umaru 6 331
2 BigDelta 5 141
3 AbduM 5 262
4 paulomirandamss12 5 266
5 Fill_in 5 276

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Marcosk 84
2 hmducanh 67:-4
3 jsuyash1514 58
4 Muhanad_Alwarareh 29
5 electrostrike 25:-2

796 successful hacks and 2063 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A sorry_hater_snsd_is_good 0:01
B ajarindong 0:02
C BigDelta 0:15
D1 bin_0808 0:26
D2 bigbigbigcat111 0:40
E Patunia 0:24
F Patunia 0:12

UPD3: Editorial is published!

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

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

anothert trashforces made by trash russians

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

    The legendary grandmaster Intellectual said! Oh wait...

    Jokes aside, it can be very usefull for those who are slightly weak at maths or have no experience of solving algorithmic problems but want to practice in coding. And imho even for some 1600+ last problems are not such a trash.

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

Last line increased my expectations for the round.

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

div1 + div2 = div3

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

    div1-div2=div3

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

    I guess you inspired them :)

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

      yep

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

      Lol really good joke. But, surely, I did not expect such a difficulty. I'm very sorry for such a hard problemset

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

        I don't have the right to complain more, because I'm out of the competition, but, for me, really enjoyed it. Thank you!

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

Good luck in your exams! Vovuh

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

Thanks Man! I just wanted another div3

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

it is raining contests

3 contests in 5 days

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

Good Luck!

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

And guys, that's how <copy-pasted-part> becomes a legend.

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

Cool! Long time no see the Div.3. I hope I will have fun in it.

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

I really like this Div.3 because I am a new hand absolutely! Thanks to the beloved author and say good luck to everyone who take part in this match!

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

What does trusted participant mean. Plus how to hack solutions of others once if we submit the solution

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

    After the contest double click on any solution in standings, then hack it by providing any test case for which that solution fails.

    All the best, may you reach your Avatar state today.

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

    shashankpathak, there's a link on "Remember that" in the piece of the text about trusted participants. There you can find the definition and the motivation of this term.

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

5+2 = 7 Seems a lucky round! #527
UPD: NO, it was'nt :(

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

hope that i can be blue :D

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

    C is a pretty weird problem for me :( i tried to solve it with two different algorithms but all failed even though i knew how to solve it

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

      Long way to go before blue, you will have to master all the elements.

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

        Nah there's nothing special about blue, we are still clueless

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

Probably, participants from the first division will not be at all interested by this problems

Probably they even can't solve them.

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

Is C checking the possible 4 strings?

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

    Yes, that's what I did.

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

    Checking 2 strings is enough. We have two longest (n-1 length) strings.

    One of them would be prefix and another will be suffix. Therefore, we can just guess one to be prefix and add a single char — last letter of another longest string — to the last of what we guessed. And if it isn't the case, we can do it again with another guess.

    This is valid because it is guaranteed that there is an answer.

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

      What is test 17 in C ?? I could not pass it. I firstly found strings of length n-1 in the input data and then considered if one of them could be a prefix of original string . Once I find that which one is prefix of length n-1 we can get the answer string but I can't understand where am I wrong MY SUBMISSION

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

      i solved it in the same way but getting wrong answer on test 17 .. i don't know what is the issue , i tried many different approaches all of them failed on test 17... let us assume i found the right string then i will iterate over all the prefixes and suffixes and store them in a vector in the form of pair of string and character and finally printing by just iterating over the input data and checking the other part of the pair and in case prefix == suffix i am handling that case too.

      edit: i was using find function to match the prefixes and suffixes which may fail for the case where it have different suffix(or prefix) but it matches with prefix as it is there so instead create another vector to store all of them and match them one by one this helped me :) hope this may help to others who failed on test 17...

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

      i have solved it like that but then also my solution has been hacked ...don't know why ??

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

wasn't div3 supposed to be easier then div2?

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

Is this a joke? The difficulty level rises up like bitcoin! Come on

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

    Understood that reference. Let me make it more clearer Image and video hosting by TinyPic

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

how to solve D1 and D2 ?

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

    D2 can be done using stacks.

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

      how ?

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

      Here have a look at my solution

      Solution

      So while putting elements in the stack if it is equal to the previous element then you can raise it to any ht required so remove both from the stack but the ht cannot be reduced so just keep a check variable for that.

      Now if the final size is 1 or less it is possible else not.

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

      convert each a[i] to a[i]%2 and then use almost logic of D2 for D1. D2 D1

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

    I think the hidden string is something like aaab, because considering aaa as sufix and aab as prefix will fail.

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

i think problem c and d hard for div3 ?

»
10 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

What is test 17 in C ?? I could not pass it. I firstly found strings of length n-1 in the input data and then considered if one of them could be a prefix of original string . Once I find that which one is prefix of length n-1 we can get the answer string but I can't understand where am I wrong MY SUBMISSION

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

47221338

Why did this fail?

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

Problem E is IOI 2013 — Day 1 — Dreaming

Also, how to solve D1?

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

    In D1, from some state you can always add verticals on any column for as much as you'd like, since anyway you can return to the state before with all columns being increased by some constant C (which makes no difference).

    Therefor, you can always keep at a state where the difference between the maximal and minimal column is less than 2, this implies you can take all columns modulo 2.

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

    I used stack for D1. Because we can vertically add a block, the number actually doesn't matter — only its parity does. I just checked parity every time I get an input and if i-th element has same parity with i-1 th element, both can be raised to arbitrarily number, so I just ignored them.

    At last, if we have one or zero element left, we can complete the wall. Else, we can't.

    This was my idea, but I'm not really sure if this is correct or not. Plz teach me a lesson if you found something wrong :)

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

    I passed pretests by keeping a queue of all possible consecutive indices whose values have the same parity because they can be made to reach all possible heights. Removing a pair might add a new pair in the queue if then consecutive indices have same parity. If at the end, we have exhausted all possible indices except possibly any 1, then answer is yes, else no.

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

:(

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

I think this contest is div1+div2 combined !

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

I think problem E can be solved in O(n), though I submitted an O(n*n) solution.

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

How to solve F ?

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Hint: Calculate values for each of the nodes using DP. Firstly calculate the value for just the subtree for each node using subtree values of the children. Then, calculate the complete value (for subtree + other nodes) using parent node complete value.

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

Me after open the scoreboard for today Div 3 round:

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

How to solve F?

I was trying to find the two nodes which lie at the diameter of the tree, I assumed that either of them will be the answer, but it was not to be. Can someone provide with a small test case where this assumption fails?

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

    Testcase: If diameter has the largest weight and rest are preety small maybe. Hint: use DP.

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

Problem D is a pile of bullshit.

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

Considering the low constraints, I don't think C was tough, it was good enough for Div3. I can say this until my code is not hacked. :P

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

    Felt same here. Initially I thought C was too tough for div3, requiring trie and some other skill. But I think 100 is fair constraint... Still I'm not sure before systest and hacks end :P

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

Is there any penalty for unsuccessful hack?

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

    no. div3 and educational round hacking has no effect on rating

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

Anybody have idea for D1 pretest 9?

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

    You can check this testcase:

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

For D1 :

  1. Since we have vertical bars of length two, it means all odd numbers can be made same, and all even numbers can be made same.
  2. When a parity is occurring in even length, it can toggle its parity easily. This can be used to merge the neighboring segments of odd length into an even length segment. You can do this repeatedly.
  3. If you think more, the problem is same as given a binary string S, and if you can convert "11" into "1" and "010" into "1", then find if S can be merged down to either of {"1", "01", "10"}. The order of events is important here, for example if S = "0101000", and you perform "010" transformation at 0th index first, then you can never merge it down to "10". Does anyone know how to solve this problem?
»
10 months ago, # |
  Vote: I like it +70 Vote: I do not like it

When seeing problem C — F : Image and video hosting by TinyPic

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

D1 wasn't easy at all it's harder than most of div(2) C :/

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

    Maybe he tried to troll div 1-2 participants who tried to solve from the last problems.

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

      actually all div3 contests sucks they always fail to make a balanced problem set and I will never participate in a div3 round again

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

Whoa, challenging round for cyan here :) However, I really enjoyed. Although generally people here felt this was harder than how div.3 should be, I think it gave me more "doable" challenges than div2 rounds did. (Generally I couldn't even submit for problem D on a div2 round ...)

Thanks for Vovuh and whoever worked hard to prepare a round, and to the community for giving wonderful oppertunity to enjoy problem-solving.

Hope no systest failures or hacks kill my rating xD

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

in problem C, test 17 gave me WA and when i changed the order of processing the input, it got AC. i don't know why. please someone help...

code1: https://codeforces.com/contest/1092/submission/47224002

code2: just by changing the order https://codeforces.com/contest/1092/submission/47227536 please someone check it...

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

    I have the same problem with test 14. I just changed order of appending strings with length 1 and length (n-1). Pretty sure that test for problem C isn't covers all possible answers.

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

    your code will probably get hacked

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

    Me to, i wrote cout<<"P" (or "S") and got wa on 17, but when I switched up and put answer in string, I got accepted.

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

Because I'm so stupid, I can not do C problem

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

https://codeforces.com/profile/sxzdsb this guy has inserted if(n==66) print(some random no) into his code. please admin look into this

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

Though above the Div3 level, the problems were really good(I read A, B, C, F).

Can F be solved by doing multiple DFS?? Basically, after finding the answer for 1 index as root through 2 DFS, I tried to do another DFS and pass some parameters to check for it's children, but couldn't implement it in time. Am I thinking the right way?

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

    yes if you use dp with 2 times dfs.

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

    Yes. After finding the answer for an arbitrary vertice you can calculate the answer for any children of this node in constant time. Basicaly, when you move from from a vertice u to a vertice v you have to decrease the sum of values of all subtree of v (because the distance has decrease by one) and increase by the sum of all others nodes that doesn't in subtree of v (because the distance to this vertices has incressed by one).

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

      I think it should be subtree of v instead of subtree of u in ur explaination.

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

    Yes, exactly the same idea (I used 3 dfs's). I implemented in time, was unable to debug a wrong indexing in dfs in time :(. It got accepted few mins after the contest got over... My submission: https://codeforces.com/contest/1092/submission/47228524

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

    Thanks! :)

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

Was this really for Div3 noobs?

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

Penatlty for unsuccessful hack?

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

"And for 1600-1899 the problems will be too easy."

I missed a really good contest because of this line :(

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

That moment when you submit a bunch of bullshit code in C and you get accepted.

https://codeforces.com/contest/1092/submission/47222677

Someone please hack me , end my suffering :p

I give it a chance of 70% to be hackable.

UPD : i got accepted lol.

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

    5 atmx a at tmxk mxk xk k atm for this test case your code gives segmentation fault..still unsuccessful hack

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Use custom invocation , the segmentation fault was probably caused by the compiler you are using.

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

Hi, Can someone please help me out with the solution for problem C? I got wrong ans on test case 17. After contest i swapped the order of processing the longest string and submitted and got AC.

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

    I think verdict is wrong. I had same problem and checked TC 17, it's oyyyyyyy.. (with 99 y). I checked on notepad and it's correct in both order (yyyyyyo or oyyyyyy)

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

      I think you are wrong. I checked your solution on the following case:

      Test

      And it printed PPPPSSSS while only one suitable string is "baaaa". So...

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

        Checked again and I might be looking some suffixes in reverse way :P

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

          Are you trolling me? Or what are you trying to say? I checked all your wrong submissions for this problem in custom invocation on this test and they're returned the wrong answer (in my and checker opinion).

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

            I'm not trolling you, was saying what was my mistake. Here an example: for aab, ab is suffix but when I was checking, sometimes I was looking it as "ba" (in custom inputs)

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

              Oh, then I'm sorry, I didn't understand you correctly.

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

    I had a similar situation as yours. If you are only checking for prefixes and assigning the remaining strings suffixes then it becomes important as to what you choose as prefix. Out of two largest length strings, it may seem both can satisfy prefixes but only one can satisfy suffixes. So as you change your order of processing, you may get AC on a wrong TC as you are changing your prefix. But you need to check suffixes also.

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

Any Ideas for an O(N) solution in E.

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

I tried to make strong tests — he said

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

https://codeforces.com/contest/1092/submission/47229976 The solution for D2, Can this be hacked. Just got hacked in my original D2 solution and found my mistake, I was just missing one simple condition. So I wanted to know can this be hacked now. Thanks

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

VERY HARD DIV3!

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

Saw a lot C's solutions are getting hacked. What are the hacks for C?

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

How to solve C Question? I'm guessing the full string using prefixes and suffixes of length n-1 and then if any string is a prefix of fullString it is assigned P and other one of same length is assigned P! I'm always failing on test 14 Please help!

My Submission

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

    in short:

    From the input you can get 4 candidate strings from which the suffixes and prefixes could come from. These 4 string are )for instance) combinations of 2 shortest and 2 longest strings from the input (shortest + longest or longest + shortest),

    Just check among these 4 a valid one and you solved the classification problem.

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

      Or you could just form 2 strings. Take the largest strings among the input strings, suppose s1 and s2. Two strings to be checked are:

      s1[0] + s2

      and

      s2 + s1[s1.length()-1]

      Example: 5 ba a abab a aba baba ab aba

      In this merge abab and baba to form: "ababa"(from a + baba) and "babab"(from baba + b) and check these 2.

      This works because the answer always exists.

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

        Yeah, actually this (your) is the solution I implemented, cause you just need to check 2 strings so I assumed it would run faster. Maybe my first explanation is a bit more intuitive,

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

          I have done the same in my submission!

          I can't figure what's wrong!

          Can any of you helpout?

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

Cheaters on problem D2 Duongcvp , duyleson76

47217201, 47216097

UPD: Vovuh pelase look into it.

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

    Thanks! I informed Mike about it, we will do something.

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

The rate at which my rank is decreasing, after 8 hours I will be rank 1.

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

Sorry, of course, but why is C such a slop? Maximum unpleasant. Do you like to give such tasks? ...

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

I dont think all the possible answers are provided in each testcase for checking. For example, in test case 19: 5 ba a baba a aba abab ab aba

Either ababa or babab can be the possible string. Thus, the possible answers are SPSSPPPS and PSPPSSSP respectively. But when my code output PSPPSSSP, the verdict was WA. Please look into this.

My submission: https://codeforces.com/contest/1092/submission/47238081

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

    ba can’t be a prefix

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

    All Prefixes should start with the same letter. In your output they don't.

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

    Thank you @Hasan and @ShowStopper728 for replying. My case itself was wrong. Understood my dumb mistake.

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

can someone explain why i fail test case 9 on D1? thanks.

submission 47221085

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

can someone explain why i fail test case 12 on C ?thanks. submission https://codeforces.com/contest/1092/submission/47223481

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

    Apparently according to the judge, it says "The number of 'P's and 'S's should be one and one for length 1". Maybe your output marks both strings of length 1 as P or S. One should be P and one should be S.

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

    When you check the Ps it seems you are assigning prefixes too early and leaving invalid suffixes

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

Man I solved problem C using DP , I was so proud because no one else did it that way (that I know of) and then I got hacked :( bummer, but of course I got hacked I didn't take into account at the last step of the DP to check that the remaining suffixes were valid , :( I really feel so hopeless about this contests I just get crushed over and over again, well at least I solved it using a different approach.

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

    I used DP too. I hacked myself with the same test I used to hack your code :P

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

      Yeah I should've totally took into account that checking of suffixes :(

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

very weak pretests ever!! two of my solutions were hacked. This isn't fair actually. -_-

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

Fun fact: I hacked at least 40 submissions with a test that hacks my own submission for problem C :P

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

I think test case #17 for C is wrong.

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

    You should have a look at this comment ..https://codeforces.com/blog/entry/63911?#comment-477530

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

The div3 is very good, E & F is about tree, let's know how to get diameter of the tree and how to construct the shortest diameter. and F is also nice, is similar with fermat point problem. https://www.lintcode.com/problem/fermat-point-of-graphs/

Thanks vovuh

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

System test did not happen? Or if it is going to happen, then when?

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

Where is the rating changes

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

I don't think that problem C is that hard solely because of constraints on n <= 100. Just find the strings of length n — 1 from the input. Consider one to be prefix and other one to be suffix. Find all other suffix and prefix strings from these strings and check wheather theses strings matches with the input , if not then the other possiblity must be the answer

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

i even think that F is easier than C

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

When is the rating going to change??

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

For problem C — Prefixes and Suffixes, my submission 47235377 got a MLE by using the built-in C++ sort function.

On the other hand, when replacing sort with stable_sort, the solution is accepted with only 200 KB of memory consumed 47237954.

Does anyone have a clue why this is the case?

Thanks in advance.

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

    Your compare function has undefined behaviour. Change return a.Id < b.Id; to return a.S.size() == b.S.size() && a.Id < b.Id; and you will get AC :)

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

      Indeed, it gave an undefined behaviour. Thank you for guiding!

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

isn't its a rated contest ???

why its took so much time to changing rating ?

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

I have one solution of C.Find two strings of length (n-1), assuming they are prefix and suffix, or suffix and prefix. Then let the other strings match the two strings. Because each length has only two strings, one is the prefix and the other must be the suffix. Because the problem must have a solution, if the first case is wrong, the other must be correct.

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

Why in test 23 of problem C, checker of system report "Runtime error" 47214009, when in my IDE or Custom Invocation, my code is alright with that test. (Test 23 is special case, so i can creat it myself). This is my code, include test 23 in input: https://ideone.com/PB83La

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

    vovuh Can you check the checker of problem C again ? Thank you!

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

      Test 23 has the following pattern:

      Spoiler

      Your pattern of test from ideone not matches this one. Anyway, I copy-pasted 23th test from polygon and checked your solution in custom invocation and it gives WA.

      I had read my checker in about 20 times. It is correct.

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      mistake is in your code.
      check this in your sort comparator :-
      return (a.X.length()>=b.X.length());

      remove the equality sign and you will get AC, like this :-
      return (a.X.length()>b.X.length());

      for more details refer strict weak ordering

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

        Amazing ! Thank you so much, i never know about that.

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

What means terms "improper prefixes" in Problem C? I guessed it means words which are not prefix of the given string.

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

    Prefixes which have a length less than the length of the string

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

      Thank you! Is it a math jargon? It confused me a lot.

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

Hi fellows, Why I still can not see my rating change of this round now?

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

)

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

Please update my rating for this contest, user name: dileepjallipalli29

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

    It'll change all user's rating at the same time. But not yet.

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

It's been one day, no food, no water, no sleep. Still waiting for the rating to be updated

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

I am getting a Runtime error on test 4 for C. Can someone help? 47229206. I am guessing the word since we know both the suffix and prefix of length n — 1 , and then assign 'P's and 'S's accordingly.

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

    maybe variable word is empty.

    you can check it with asserts:

    string word;
       if(first[0] + last[0] == last[1] + first[1])
          word = first[0] + last[0];
       else if(first[0] + last[1] == last[0] + first[1])
          word = first[0] + last[1];
       else assert(0);
    

    try submit this code.

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

Are the ratings for this contest has been updated?. Because I can't see any changes in my ratings. I took part in this contest and solved 2 questions. Please update the ratings!!

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

Editorial?

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

y the hell is it taking this much time for changing ratings ?

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

Fastest system testing ever plus slowest rating update ever in my codeforces career.

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

How to solve the problems like C of this contest? As i am a beginner i dont have any knowledge about that.Please Help me.

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

please release the editorial of this contest??

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

Can anyone explain problem E?

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

    For each Tree, find its center (find the diameter first, and take the node in the middle of the path, that's the center). Let Cx be the center of one of the trees with greatest diameter. Now add an edge between Cx and every other center found, now you have created another tree in which the diameter's length is minimmum. Finding all centers can be done in O(N), and finding the diameter of the final tree can be done in O(N) as well, so the overall complexity remains O(N).

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

      thanks a lot!

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

      Need some help. I tried below logic, but giving WA on Test 9.

      1. using bfs on a random node I calculated farthest node in each connected component.
      2. then for farthest node of these connected comps, I again ran bfs. this will give me other end of the diameter. --> ran dfs(node1, node2) => this will give the diameter path on every connected comps. (I know step 2 can be optimized, but we can take care of optimization later).
      3. Then I calculated the component which has the minimum size and attached the center of all other diameters to this node. => updated the graph.

      4. Calculated the diameter(dist) of the new graph again using two bfs. (one for farthest node and the other on this farthest node to calculate diameter).
      5. Printed this result.

      But somehow for me testcase 9 is failing. Could anyone look into this code and tell me what is going wrong here? Or any simple example of this test case through which I can debug?

      https://codeforces.com/contest/1092/submission/47486914

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

when will the editorials be published?

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

The problem C is not so hard as it seems in my opinion, I solved it in the folowing way : take the two sequences of length n - 1, one is suppose to be the prefix and another the suffix of the original string and the original string is either a[0] + b or b[0] + a. Just try both possibilities and take the good one.

When taking a[0] + b you should check as well if the letters in a from position [1, size] are equal with the letters in b from [0, size - 1], same goes for b[0] + a.

Hope this helps somebody, for more details take a look at my submission.

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

I need the Tutorial because the contest was really amazing and tricky specially Problem F

But my solution to F one got TLE and one Got WA I depended on tree diameter and another dfs to get max cost

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

Best Contest i have ever had <3

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

Oops, what wrong with the winners? It seems to be Doma_Umaru only got rank 5 instead of 1 (I found on his/her profile), and absolutely_bu01th4nh got rank 1?

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

    The ones that don't have rating are excluded.

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

      Wow, new fact!

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

        em rank một mà bọn nó đéo cho em rank 1 lên trang chủ anh nhị ơi

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

          vì cái tên của em nó như bu01

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

            em tên bùi tiến thành thế đéo nào thằng lồn nào nó tạo nick nhái em tên buồi

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

omg this contest was rigged by trashforces russians so i lose rating that isn't fair you know

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

your previous round was one of the best rounds i've seen since i join codeforces

hope to see such a great contest again

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

前排吃瓜