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!

anothert trashforces made by trash russians

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.

meanie

Last line increased my expectations for the round.

div1 + div2 = div3

div1-div2=div3

I guess you inspired them :)

yep

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

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

Good luck in your exams! Vovuh

Thanks Man! I just wanted another div3

it is raining contests

3 contests in 5 days

Good Luck!

And guys, that's how

`<copy-pasted-part>`

becomes a legend.Cool! Long time no see the Div.3. I hope I will have fun in 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!

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

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.

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.

5+2 = 7Seems a lucky round! #527UPD: NO, it was'nt :(That reminded me of 1058C - Vasya and Golden Ticket.

now waiting for round #538

hope that i can be blue :D

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

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

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

Probably, participants from the first division will not be at all interested by this problemsProbably they even can't solve them.

Is C checking the possible 4 strings?

Yes, that's what I did.

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.

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

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

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/47208703

AC — https://codeforces.com/contest/1092/submission/47213730

sad part is it has nothing to do with the logic just a blunder !!! check mine exactly same mistake :((((((((((((((

Can you provide a example test case I am not able to understand what you are implying.

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

wasn't div3 supposed to be easier then div2?

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

Understood that reference. Let me make it more clearer

Difficulty level of the reference roughly matches difficulty level of the problem set.

how to solve D1 and D2 ?

D2 can be done using stacks.

how ?

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.

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

Good solution but hacked.

## Sed_Lyf

what was test case 6 for problem 3?

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

I think the hidden string is something like

aaab, because consideringaaaas sufix andaabas prefix will fail.i attached my code . Please refer to it once

Sorry, I didn't know what's the issue.

i think problem c and d hard for div3 ?

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

47221338

Why did this fail?

Problem E is IOI 2013 — Day 1 — Dreaming

Also, how to solve D1?

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.

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 :)

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.

:(I think this contest is div1+div2 combined !

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

Yes, you can solve it in O(n). Check out Dreaming from IOI '13.

I solved it in O(N). https://codeforces.com/blog/entry/63911?#comment-477736

How to solve F ?

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.

Me after open the scoreboard for today Div 3 round:

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?

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

Problem D is a pile of bullshit.

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

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

Is there any penalty for unsuccessful hack?

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

Anybody have idea for D1 pretest 9?

You can check this testcase:

For D1 :

nevermerge it down to "10". Does anyone know how to solve this problem?When seeing problem C — F :

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

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

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

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

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

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.

your code will probably get hacked

lol, i submitted it after the contest was over.

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.

yes me too

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

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

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

Chor sala apna code hack karega

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?

yes if you use dp with 2 times dfs.

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

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

Thanks, i fixed it :D

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

Thanks! :)

Was this really for Div3 noobs?

Nope

Penatlty for unsuccessful hack?

nope!

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

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

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.

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

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

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.

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)

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

Test5

a

aa

aaa

aaaa

b

ba

baa

baaa

And it printed

`PPPPSSSS`

while only one suitable string is "baaaa". So...Checked again and I might be looking some suffixes in reverse way :P

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

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)

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

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.

Any Ideas for an

O(N) solution in E.https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013 The answer on quora is pretty good.

My solution

thanks apparently i had the same code implemented during the round but had a little bug :p

I tried to make strong tests— he saidhe also said that he copy-pasted.

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

VERY HARD DIV3!

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

I did one using this:

4

a

c

ac

ab

aba

bac

I got WA at test case 17 but getting PSSPPS for this. Is that correct?

yes it is correct!

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

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.

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.

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,

I have done the same in my submission!

I can't figure what's wrong!

Can any of you helpout?

Cheaters on problem D2 Duongcvp , duyleson76

47217201, 47216097

UPD: Vovuh pelase look into it.Thanks! I informed Mike about it, we will do something.

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

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

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

ba can’t be a prefix

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

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

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

submission 47221085

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

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.

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

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.

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

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

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

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

What hack did you use?

I think test case #17 for C is wrong.

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

I still don't get 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

and thanks to MikeMirzayanov also.

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

System test is over and problems are moved to practice.

I never knew system test would be this fast!

fastest system test already done.

Where is the rating changes

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 answeri even think that F is easier than C

When is the rating going to change??

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.

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 :)Indeed, it gave an undefined behaviour. Thank you for guiding!

isn't its a rated contest ???

why its took so much time to changing rating ?

am i the only one who hate > 1 question mark ?

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.

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

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

Test 23 has the following pattern:

Spoilera

aa

aaa

...

aaaaa...aaaaa

a

aa

aaa

...

aaaaa...aaaaa

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

custom invocationand it gives WA.I had read my checker in about 20 times. It is correct.

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

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

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

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

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

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

)

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

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

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

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.maybe variable word is empty.

you can check it with asserts:

try submit this code.

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

Editorial?

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

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

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.

please release the editorial of this contest??

Can anyone explain problem E?

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

thanks a lot!

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

Then I calculated the component which has the minimum size and attached the center of all other diameters to this node. => updated the graph.

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

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.

Updated:- https://codeforces.com/contest/1092/submission/47487581

Thanks!!

when will the editorials be published?

The problem

Cis 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 theoriginal stringis 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 inafrom position`[1, size]`

are equal with the letters inbfrom`[0, size - 1]`

, same goes for`b[0] + a`

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

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

Best Contest i have ever had <3

Acha aisa kya ho gya

Finally solved 2 Questions XD

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

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?

The ones that don't have rating are excluded.

Wow, new fact!

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

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

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

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

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

hope to see such a great contest again

前排吃瓜