### Vovuh's blog

By Vovuh, history, 4 weeks ago, ,

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
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!

•
• +130
•

 » 4 weeks ago, # |   -183 anothert trashforces made by trash russians
•  » » 4 weeks ago, # ^ |   +6 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.
•  » » » 4 weeks ago, # ^ |   -22 meanie
 » 4 weeks ago, # |   0 Last line increased my expectations for the round.
 » 4 weeks ago, # |   +38 div1 + div2 = div3
•  » » 4 weeks ago, # ^ |   -20 div1-div2=div3
•  » » 4 weeks ago, # ^ |   +20 I guess you inspired them :)
•  » » » 4 weeks ago, # ^ |   +7 yep
•  » » » 4 weeks ago, # ^ |   +42 Lol really good joke. But, surely, I did not expect such a difficulty. I'm very sorry for such a hard problemset
•  » » » » 4 weeks ago, # ^ |   +6 I don't have the right to complain more, because I'm out of the competition, but, for me, really enjoyed it. Thank you!
 » 4 weeks ago, # |   -7 Good luck in your exams! Vovuh
 » 4 weeks ago, # |   -7 Thanks Man! I just wanted another div3
 » 4 weeks ago, # |   0 it is raining contests3 contests in 5 days
 » 4 weeks ago, # |   0 Good Luck!
 » 4 weeks ago, # | ← Rev. 2 →   0 And guys, that's how  becomes a legend.
 » 4 weeks ago, # |   +3 Cool! Long time no see the Div.3. I hope I will have fun in it.
 » 4 weeks ago, # |   +14 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!
 » 4 weeks ago, # |   0 What does trusted participant mean. Plus how to hack solutions of others once if we submit the solution
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » 4 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # | ← Rev. 3 →   +10 5+2 = 7 Seems a lucky round! #527 UPD: NO, it was'nt :(
•  » » 4 weeks ago, # ^ |   +5 That reminded me of 1058C - Vasya and Golden Ticket.
•  » » 4 weeks ago, # ^ |   0 now waiting for round #538
 » 4 weeks ago, # |   0 hope that i can be blue :D
•  » » 4 weeks ago, # ^ |   0 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
•  » » » 4 weeks ago, # ^ |   +2 Long way to go before blue, you will have to master all the elements.
•  » » » » 4 weeks ago, # ^ |   0 Nah there's nothing special about blue, we are still clueless
 » 4 weeks ago, # | ← Rev. 2 →   +60 Probably, participants from the first division will not be at all interested by this problemsProbably they even can't solve them.
 » 4 weeks ago, # |   +3 Is C checking the possible 4 strings?
•  » » 4 weeks ago, # ^ |   0 Yes, that's what I did.
•  » » 4 weeks ago, # ^ |   +14 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.
•  » » » 4 weeks ago, # ^ |   0 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
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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...
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I had the same mistake. Once you check for a string, you have to double check it before printing it as an answer. Check my submissions for more:WA on TC 17 — https://codeforces.com/contest/1092/submission/47208703AC — https://codeforces.com/contest/1092/submission/47213730
•  » » » » » 4 weeks ago, # ^ |   0 sad part is it has nothing to do with the logic just a blunder !!! check mine exactly same mistake :((((((((((((((
•  » » » » 4 weeks ago, # ^ |   0 Can you provide a example test case I am not able to understand what you are implying.
•  » » » 4 weeks ago, # ^ |   0 i have solved it like that but then also my solution has been hacked ...don't know why ??
 » 4 weeks ago, # |   +49 wasn't div3 supposed to be easier then div2?
 » 4 weeks ago, # |   +68 Is this a joke? The difficulty level rises up like bitcoin! Come on
•  » » 4 weeks ago, # ^ |   +81 Understood that reference. Let me make it more clearer
•  » » » 4 weeks ago, # ^ |   +15 Difficulty level of the reference roughly matches difficulty level of the problem set.
 » 4 weeks ago, # |   0 how to solve D1 and D2 ?
•  » » 4 weeks ago, # ^ |   +3 D2 can be done using stacks.
•  » » » 4 weeks ago, # ^ |   0 how ?
•  » » » 4 weeks ago, # ^ |   +1 Here have a look at my solution SolutionSo 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.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 convert each a[i] to a[i]%2 and then use almost logic of D2 for D1. D2 D1
•  » » » » 4 weeks ago, # ^ |   0 Good solution but hacked.
• »
»
»
»
»
4 weeks ago, # ^ |
0

# Sed_Lyf

 » 4 weeks ago, # | ← Rev. 2 →   0 what was test case 6 for problem 3?https://codeforces.com/contest/1092/submission/47223304
•  » » 4 weeks ago, # ^ |   0 I think the hidden string is something like aaab, because considering aaa as sufix and aab as prefix will fail.
•  » » » 4 weeks ago, # ^ |   0 i attached my code . Please refer to it once
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sorry, I didn't know what's the issue.
 » 4 weeks ago, # |   +1 i think problem c and d hard for div3 ?
 » 4 weeks ago, # | ← Rev. 4 →   +1 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
 » 4 weeks ago, # |   0 47221338Why did this fail?
 » 4 weeks ago, # |   +24 Problem E is IOI 2013 — Day 1 — DreamingAlso, how to solve D1?
•  » » 4 weeks ago, # ^ |   +1 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.
•  » » » 4 weeks ago, # ^ |   +18
•  » » 4 weeks ago, # ^ |   +5 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 :)
•  » » 4 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # |   +62 :(
 » 4 weeks ago, # |   +3 I think this contest is div1+div2 combined !
 » 4 weeks ago, # |   0 I think problem E can be solved in O(n), though I submitted an O(n*n) solution.
•  » » 4 weeks ago, # ^ |   0 Yes, you can solve it in O(n). Check out Dreaming from IOI '13.
•  » » 4 weeks ago, # ^ |   0 I solved it in O(N). https://codeforces.com/blog/entry/63911?#comment-477736
 » 4 weeks ago, # |   +2 How to solve F ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 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.
 » 4 weeks ago, # |   +33 Me after open the scoreboard for today Div 3 round:
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   +5 Testcase: If diameter has the largest weight and rest are preety small maybe. Hint: use DP.
 » 4 weeks ago, # |   -32 Problem D is a pile of bullshit.
 » 4 weeks ago, # | ← Rev. 3 →   +3 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
•  » » 4 weeks ago, # ^ |   +1 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
 » 4 weeks ago, # |   +1 Is there any penalty for unsuccessful hack?
•  » » 4 weeks ago, # ^ |   0 no. div3 and educational round hacking has no effect on rating
 » 4 weeks ago, # |   0 Anybody have idea for D1 pretest 9?
•  » » 4 weeks ago, # ^ |   0 You can check this testcase: 8 1 2 1 2 2 1 2 1 
 » 4 weeks ago, # |   +7 For D1 : 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. 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. 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?
 » 4 weeks ago, # |   +70 When seeing problem C — F :
 » 4 weeks ago, # |   0 D1 wasn't easy at all it's harder than most of div(2) C :/
•  » » 4 weeks ago, # ^ |   +9 Maybe he tried to troll div 1-2 participants who tried to solve from the last problems.
•  » » » 4 weeks ago, # ^ |   -22 actually all div3 contests sucks they always fail to make a balanced problem set and I will never participate in a div3 round again
 » 4 weeks ago, # |   +2 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
 » 4 weeks ago, # |   0 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...code2: just by changing the order https://codeforces.com/contest/1092/submission/47227536 please someone check it...
•  » » 4 weeks ago, # ^ |   0 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.
•  » » 4 weeks ago, # ^ |   +1 your code will probably get hacked
•  » » » 4 weeks ago, # ^ |   0 lol, i submitted it after the contest was over.
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ |   0 yes me too
 » 4 weeks ago, # |   0 Because I'm so stupid, I can not do C problem
 » 4 weeks ago, # |   0 What is the test 12 in C ? https://codeforces.com/contest/1092/submission/47223481
 » 4 weeks ago, # |   +9 https://codeforces.com/profile/sxzdsb this guy has inserted if(n==66) print(some random no) into his code. please admin look into this
•  » » 4 weeks ago, # ^ |   -6 Chor sala apna code hack karega
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   0 yes if you use dp with 2 times dfs.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 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).
•  » » » 4 weeks ago, # ^ |   +3 I think it should be subtree of v instead of subtree of u in ur explaination.
•  » » » » 4 weeks ago, # ^ |   0 Thanks, i fixed it :D
•  » » 4 weeks ago, # ^ |   0 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
•  » » 4 weeks ago, # ^ |   0 Thanks! :)
 » 4 weeks ago, # |   +2 Was this really for Div3 noobs?
•  » » 4 weeks ago, # ^ |   0 Nope
 » 4 weeks ago, # |   0 Penatlty for unsuccessful hack?
•  » » 4 weeks ago, # ^ |   +1 nope!
 » 4 weeks ago, # |   +25 "And for 1600-1899 the problems will be too easy."I missed a really good contest because of this line :(
 » 4 weeks ago, # | ← Rev. 2 →   +2 That moment when you submit a bunch of bullshit code in C and you get accepted.https://codeforces.com/contest/1092/submission/47222677Someone please hack me , end my suffering :pI give it a chance of 70% to be hackable.UPD : i got accepted lol.
•  » » 4 weeks ago, # ^ |   0 5 atmx a at tmxk mxk xk k atm for this test case your code gives segmentation fault..still unsuccessful hack
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Use custom invocation , the segmentation fault was probably caused by the compiler you are using.
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   0 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)
•  » » » 4 weeks ago, # ^ |   0 I think you are wrong. I checked your solution on the following case: Test5aaaaaaaaaabbabaabaaaAnd it printed PPPPSSSS while only one suitable string is "baaaa". So...
•  » » » » 4 weeks ago, # ^ |   0 Checked again and I might be looking some suffixes in reverse way :P
•  » » » » » 4 weeks ago, # ^ |   0 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).
•  » » » » » » 4 weeks ago, # ^ |   0 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)
•  » » » » » » » 4 weeks ago, # ^ |   0 Oh, then I'm sorry, I didn't understand you correctly.
•  » » 4 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # |   0 Any Ideas for an O(N) solution in E.
•  » » 4 weeks ago, # ^ |   +8 https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013 The answer on quora is pretty good.My solution
•  » » » 4 weeks ago, # ^ |   0 thanks apparently i had the same code implemented during the round but had a little bug :p
 » 4 weeks ago, # |   +7 I tried to make strong tests — he said
•  » » 4 weeks ago, # ^ |   +1 he also said that he copy-pasted.
 » 4 weeks ago, # |   0 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
 » 4 weeks ago, # |   +33 VERY HARD DIV3!
 » 4 weeks ago, # |   0 Saw a lot C's solutions are getting hacked. What are the hacks for C?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 I did one using this:4acacabababac
•  » » » 4 weeks ago, # ^ |   0 I got WA at test case 17 but getting PSSPPS for this. Is that correct?
•  » » » » 4 weeks ago, # ^ |   0 yes it is correct!
 » 4 weeks ago, # |   0 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
•  » » 4 weeks ago, # ^ |   +5 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.
•  » » » 4 weeks ago, # ^ |   +1 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] + s2ands2 + s1[s1.length()-1]Example: 5 ba a abab a aba baba ab abaIn 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.
•  » » » » 4 weeks ago, # ^ |   0 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,
•  » » » » » 4 weeks ago, # ^ |   0 I have done the same in my submission! I can't figure what's wrong!Can any of you helpout?
 » 4 weeks ago, # | ← Rev. 2 →   +7 Cheaters on problem D2 Duongcvp , duyleson76UPD: Vovuh pelase look into it.
•  » » 4 weeks ago, # ^ |   +4 Thanks! I informed Mike about it, we will do something.
 » 4 weeks ago, # |   +1 The rate at which my rank is decreasing, after 8 hours I will be rank 1.
 » 4 weeks ago, # |   0 Sorry, of course, but why is C such a slop? Maximum unpleasant. Do you like to give such tasks? ...
 » 4 weeks ago, # | ← Rev. 2 →   0 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 abaEither 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
•  » » 4 weeks ago, # ^ |   0 ba can’t be a prefix
•  » » 4 weeks ago, # ^ |   0 All Prefixes should start with the same letter. In your output they don't.
•  » » 4 weeks ago, # ^ |   0 Thank you @Hasan and @ShowStopper728 for replying. My case itself was wrong. Understood my dumb mistake.
 » 4 weeks ago, # |   0 can someone explain why i fail test case 9 on D1? thanks.submission 47221085
 » 4 weeks ago, # |   +5 can someone explain why i fail test case 12 on C ?thanks. submission https://codeforces.com/contest/1092/submission/47223481
•  » » 4 weeks ago, # ^ |   0 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.
•  » » 4 weeks ago, # ^ |   0 When you check the Ps it seems you are assigning prefixes too early and leaving invalid suffixes
 » 4 weeks ago, # |   +1 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.
•  » » 4 weeks ago, # ^ |   +2 I used DP too. I hacked myself with the same test I used to hack your code :P
•  » » » 4 weeks ago, # ^ |   0 Yeah I should've totally took into account that checking of suffixes :(
 » 4 weeks ago, # |   0 very weak pretests ever!! two of my solutions were hacked. This isn't fair actually. -_-
 » 4 weeks ago, # |   +9 Fun fact: I hacked at least 40 submissions with a test that hacks my own submission for problem C :P
•  » » 4 weeks ago, # ^ |   0 What hack did you use?
 » 4 weeks ago, # |   0 I think test case #17 for C is wrong.
•  » » 4 weeks ago, # ^ |   0 You should have a look at this comment ..https://codeforces.com/blog/entry/63911?#comment-477530
•  » » » 4 weeks ago, # ^ |   0 I still don't get it.
 » 4 weeks ago, # |   +1 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
•  » » 4 weeks ago, # ^ |   0 and thanks to MikeMirzayanov also.
 » 4 weeks ago, # |   0 System test did not happen? Or if it is going to happen, then when?
•  » » 4 weeks ago, # ^ |   0 System test is over and problems are moved to practice.
•  » » » 4 weeks ago, # ^ |   0 I never knew system test would be this fast!
•  » » 4 weeks ago, # ^ |   +1 fastest system test already done.
 » 4 weeks ago, # |   +1 Where is the rating changes
 » 4 weeks ago, # |   +4 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
 » 4 weeks ago, # |   0 i even think that F is easier than C
 » 4 weeks ago, # |   +2 When is the rating going to change??
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   0 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 :)
•  » » » 4 weeks ago, # ^ |   0 Indeed, it gave an undefined behaviour. Thank you for guiding!
 » 4 weeks ago, # |   +2 isn't its a rated contest ??? why its took so much time to changing rating ?
•  » » 4 weeks ago, # ^ |   +3 am i the only one who hate > 1 question mark ?
 » 4 weeks ago, # |   0 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.
 » 4 weeks ago, # | ← Rev. 2 →   0 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
•  » » 4 weeks ago, # ^ |   0 vovuh Can you check the checker of problem C again ? Thank you!
•  » » » 4 weeks ago, # ^ |   +6 Test 23 has the following pattern: Spoileraaaaaa...aaaaa...aaaaaaaaaaa...aaaaa...aaaaaYour 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.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » 4 weeks ago, # ^ |   0 Amazing ! Thank you so much, i never know about that.
 » 4 weeks ago, # |   0 What means terms "improper prefixes" in Problem C? I guessed it means words which are not prefix of the given string.
•  » » 4 weeks ago, # ^ |   +4 Prefixes which have a length less than the length of the string
•  » » » 4 weeks ago, # ^ |   0 Thank you! Is it a math jargon? It confused me a lot.
 » 4 weeks ago, # |   +3 Hi fellows, Why I still can not see my rating change of this round now?
 » 4 weeks ago, # | ← Rev. 3 →   +13 )
 » 4 weeks ago, # |   -7 Please update my rating for this contest, user name: dileepjallipalli29
•  » » 4 weeks ago, # ^ |   +1 It'll change all user's rating at the same time. But not yet.
 » 4 weeks ago, # |   +2 It's been one day, no food, no water, no sleep. Still waiting for the rating to be updated
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   +1 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.
 » 4 weeks ago, # | ← Rev. 2 →   +1 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!!
 » 4 weeks ago, # |   +4 Editorial?
 » 4 weeks ago, # |   0 y the hell is it taking this much time for changing ratings ?
 » 4 weeks ago, # |   0 Fastest system testing ever plus slowest rating update ever in my codeforces career.
 » 4 weeks ago, # |   0 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.
 » 4 weeks ago, # | ← Rev. 2 →   0 please release the editorial of this contest??
 » 4 weeks ago, # |   0 Can anyone explain problem E?
•  » » 4 weeks ago, # ^ |   +2 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).
•  » » » 4 weeks ago, # ^ |   0 thanks a lot!
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Need some help. I tried below logic, but giving WA on Test 9. using bfs on a random node I calculated farthest node in each connected component. 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). Then I calculated the component which has the minimum size and attached the center of all other diameters to this node. => updated the graph. 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). 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
•  » » » » 3 weeks ago, # ^ |   0 Got AC. In step 3, instead of minimum size, changed it to check for maximum size. after that used this center and attached all other nodes to this. => Got AC.Thanks!!
 » 4 weeks ago, # |   0 when will the editorials be published?
 » 4 weeks ago, # | ← Rev. 2 →   0 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.
 » 4 weeks ago, # |   0 I need the Tutorial because the contest was really amazing and tricky specially Problem FBut my solution to F one got TLE and one Got WA I depended on tree diameter and another dfs to get max cost
 » 4 weeks ago, # |   0 Best Contest i have ever had <3
•  » » 4 weeks ago, # ^ |   0 Acha aisa kya ho gya
•  » » » 4 weeks ago, # ^ |   0 Finally solved 2 Questions XD
 » 4 weeks ago, # |   0 Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   +1 The ones that don't have rating are excluded.
•  » » » 4 weeks ago, # ^ |   0 Wow, new fact!
•  » » » » 3 weeks ago, # ^ |   0 em rank một mà bọn nó đéo cho em rank 1 lên trang chủ anh nhị ơi
•  » » » » » 3 weeks ago, # ^ |   0 vì cái tên của em nó như bu01
•  » » » » » » 3 weeks ago, # ^ |   0 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
 » 4 weeks ago, # |   -25 omg this contest was rigged by trashforces russians so i lose rating that isn't fair you know
 » 4 weeks ago, # |   0 your previous round was one of the best rounds i've seen since i join codeforceshope to see such a great contest again
 » 4 weeks ago, # |   0 前排吃瓜