vovuh's blog

Codeforces Round #527 (Div. 3)
By vovuh, history, 6 years 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 awoo Piklyaev, Maksim Neon 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 Roms Glazov, Farkhod Farhod 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 PauloMiranda98 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 Warawreh 29
5 darkness_peach 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 lee_chaerin 0:01
B ajarindong 0:02
C BigDelta 0:15
D1 Sad_reacts_only 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

Comments Comments (193)
| Write comment?
»
6 years ago, # |
  Vote: I like it -183 Vote: I do not like it

anothert trashforces made by trash russians

→ Reply
  • »
    »
    6 years 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.

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

Last line increased my expectations for the round.

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

div1 + div2 = div3

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

    I guess you inspired them :)

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

      yep

      → Reply
    • »
      »
      »
      6 years 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

      → Reply
      • »
        »
        »
        »
        6 years 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!

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

Good luck in your exams! vovuh

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

Thanks Man! I just wanted another div3

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

it is raining contests

3 contests in 5 days

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

Good Luck!

→ Reply
»
6 years 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.

→ Reply
»
6 years 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.

→ Reply
»
6 years 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!

→ Reply
»
6 years 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

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

    you_paison, 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.

    → Reply
»
6 years 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 :(

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

hope that i can be blue :D

→ Reply
  • »
    »
    6 years 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

    → Reply
    • »
      »
      »
      6 years 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.

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

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

        → Reply
»
6 years 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.

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

Is C checking the possible 4 strings?

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

    Yes, that's what I did.

    → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
    • »
      »
      »
      6 years 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...

      → Reply
    • »
      »
      »
      6 years 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 ??

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

wasn't div3 supposed to be easier then div2?

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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

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

how to solve D1 and D2 ?

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

    D2 can be done using stacks.

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

      how ?

      → Reply
    • »
      »
      »
      6 years 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.

      → Reply
    • »
      »
      »
      6 years 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

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

what was test case 6 for problem 3?

https://codeforces.me/contest/1092/submission/47223304

→ Reply
  • »
    »
    6 years 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.

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

i think problem c and d hard for div3 ?

→ Reply
»
6 years 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

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

47221338

Why did this fail?

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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 :)

    → Reply
  • »
    »
    6 years 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.

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

:(

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

I think this contest is div1+div2 combined !

→ Reply
»
6 years 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.

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

How to solve F ?

→ Reply
  • »
    »
    6 years 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.

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

Me after open the scoreboard for today Div 3 round:

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

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

Problem D is a pile of bullshit.

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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

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

Is there any penalty for unsuccessful hack?

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

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

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

Anybody have idea for D1 pretest 9?

→ Reply
  • »
    »
    6 years 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
    → Reply
»
6 years 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?
→ Reply
»
6 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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

→ Reply
»
6 years 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 :/

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
»
6 years 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

→ Reply
»
6 years 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.me/contest/1092/submission/47224002

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

→ Reply
  • »
    »
    6 years 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.

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

    your code will probably get hacked

    → Reply
  • »
    »
    6 years 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.

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

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

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

What is the test 12 in C ? https://codeforces.me/contest/1092/submission/47223481

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

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

→ Reply
»
6 years 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?

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

    yes if you use dp with 2 times dfs.

    → Reply
  • »
    »
    6 years 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).

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
  • »
    »
    6 years 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.me/contest/1092/submission/47228524

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

    Thanks! :)

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

Was this really for Div3 noobs?

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

Penatlty for unsuccessful hack?

→ Reply
»
6 years 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 :(

→ Reply
»
6 years 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.me/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.

→ Reply
  • »
    »
    6 years 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

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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)

    → Reply
    • »
      »
      »
      6 years 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...

      → Reply
      • »
        »
        »
        »
        6 years 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

        → Reply
        • »
          »
          »
          »
          »
          6 years 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).

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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)

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

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

              → Reply
  • »
    »
    6 years 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.

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

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

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

I tried to make strong tests — he said

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

https://codeforces.me/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

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

VERY HARD DIV3!

→ Reply
»
6 years 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?

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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,

        → Reply
        • »
          »
          »
          »
          »
          6 years 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?

          → Reply
»
6 years 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.

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

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

    → Reply
»
6 years 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.

→ Reply
»
6 years 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? ...

→ Reply
»
6 years 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.me/contest/1092/submission/47238081

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

    ba can’t be a prefix

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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

→ Reply
»
6 years 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.me/contest/1092/submission/47223481

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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

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

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

      → Reply
»
6 years 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. -_-

→ Reply
»
6 years 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

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

I think test case #17 for C is wrong.

→ Reply
»
6 years 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

→ Reply
»
6 years 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?

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

Where is the rating changes

→ Reply
»
6 years 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

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

i even think that F is easier than C

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

When is the rating going to change??

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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 :)

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

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

      → Reply
»
6 years 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 ?

→ Reply
»
6 years 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.

→ Reply
»
6 years 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

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

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

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
    • »
      »
      »
      6 years 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

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

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

        → Reply
»
6 years 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.

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

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

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

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

      → Reply
»
6 years 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?

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

)

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

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

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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!!

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

Editorial?

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

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

→ Reply
»
6 years 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.

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

Can anyone explain problem E?

→ Reply
  • »
    »
    6 years 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).

    → Reply
»
6 years 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.

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

Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)

→ Reply
»
6 years 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?

→ Reply
»
6 years 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

→ Reply