### HolkinPV's blog

By HolkinPV, 9 years ago, translation,

Welcome friends)

We are glad to introduce you regular Codeforces round #117 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Ivan Fefer (Fefer_Ivan), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

And again score distribution will be dynamic) More information you can find here.

Note that all problems today will be given in random order.

Some Div.1 participants register for the contest before settings of registration were changed. Before the round it will be fixed and they will participate out of competition.

We hope that todays round would be succesful and everyone enjoys it. We wish you good luck and high rating!

UPD: the statement for problem 182E - Wooden Fence was formulated incorrect, correct variant of the statement will be soon, we apologize to the participants.

UPD2: the contest is declared unrated.

• +45

 » 9 years ago, # |   +18 And are there dynamic problem max scores used?
•  » » 9 years ago, # ^ |   -23 And again score distribution will be dynamic) More information you can find here.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +18 Hm, that's nice, but I asked before it was written in post. HolkinPV updated the post later (I can't delete my comment)...
 » 9 years ago, # | ← Rev. 2 →   -40 502 Bad Gateway...Please allow me to enterUPD:Oops...Did not realize that we have been given 10 more minutes to get ready :)
•  » » 9 years ago, # ^ |   -7 Okay
•  » » 9 years ago, # ^ |   0 wait a bit, contest was moved for 10 minutes due to server problem
 » 9 years ago, # |   -15 Problem A will be the easiest one as the first dynamic contest ?
•  » » 9 years ago, # ^ |   +2 No
•  » » » 9 years ago, # ^ |   +22 Yes. With probability 1/5.
•  » » 9 years ago, # ^ |   0 Note that all problems today will be given in random order.
•  » » 9 years ago, # ^ |   -16 No, "Note that all problems today will be given in random order." ;-)
 » 9 years ago, # |   +8 07:00 PM (Moscow Time), is the ideal time for a programming contest, please to keep this schedule for the future competitions.
 » 9 years ago, # |   0 Unable to ask questions. Getting "Field should not contain more than 1,000 characters" when the question is much shorter than that.
•  » » 9 years ago, # ^ |   0 Maybe you have some copy-paste from HTML. And HTML source of your question exceeded 1000?
•  » » » 9 years ago, # ^ |   +5 I did not copy paste the question initially, I just typed it in the box. I also tried using the "Remove formatting" option.
•  » » » » 9 years ago, # ^ |   0 Thank you. I'll try to investigate it.
 » 9 years ago, # | ← Rev. 2 →   +19 Unsuccessful challenge on problem E:Input: 2 41 31 3Output: 4Answer: 4How the answer is 4? It should be 2.1) #1, rev#22) #2, rev#1I asked a lot of questions during contest and got answers that for example (#1, rev#2) and (rev#1, #2) are same variants. In that case the answer should be 2 for the case above.
•  » » 9 years ago, # ^ |   0 I think answer is 4,not 2. You get 2 combinations putting type 1 first, and 2 putting type 2 first.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +3 According to the problem description 2 out of those 4 variants are the same.P.S. I even asked a question to jury by specifying exactly such 4 variants, and got a response that 2 of them are duplicate.
•  » » 9 years ago, # ^ | ← Rev. 2 →   +2 i think that they assumed that a rotation is considered as new type
 » 9 years ago, # | ← Rev. 3 →   +23 In problem E. What is the answer for the input (2 3 1 2 1 2) ? There are 4 sequence of fences. seq0 : fence[0] -> turn(fence[1]). seq1 : turn(fence[0]) -> fence[1]. seq2 : fence[1] -> turn(fence[0]). seq3 : turn(fence[1]) -> fence[0]. But seq0 and seq1 are same, And seq2 and seq3 are same too. So I think it is 2. But if so, the answer for sample3 is 18 not 20.
•  » » 9 years ago, # ^ |   +8 Same issue for me :) Spent 1 hour on discussions with jury
•  » » 9 years ago, # ^ |   +7 I'm surprising when my not-finished solution passed examples(as well as the pre-tests). That is the same question. The admin's reply is just:"I can only say, that rotation of the board does NOT change its type. So sequences with same boards but with different rotations are same."So I don't know what is wrong: the standard solution, the statement or my understanding?
 » 9 years ago, # | ← Rev. 3 →   -6 Problem C: Many people have wrong answer with pretest #15 (include me). Good pretest :D
 » 9 years ago, # | ← Rev. 2 →   +13 [upd: sorry for asking the same questions other people already did. I typed the question at the same time.]I have a question about problem E. Consider this test case: 2 3 1 2 1 2 Considering that "Two fences shall be considered the same if the corresponding sequences of fence boards' types are the same", I think the answer should be 2 — a fence with board types A and B ((1,2),(2,1)) and another with types B and A (also ((1,2),(2,1))), where A and B are the two given types of fences. ((2,1),(1,2)) would be equal to one of these solutions, since only the type (and not the rotations) are considered during comparation.However, according to an unsucefull hack attempt, the answer is 4. I asked it during the contest, and they said that a fence with types (A,B,A) and (B,A,B) is also valid, but I can't figure out how it's possible with fence lenght 3... Can somebody? Thanks!
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 If we called the first block A (1,3) and the second block B (1,3) The 4 valid fences are : (A , rev_B) , (B , rev_A) , (rev_A , B) , (rev_B , A)
•  » » » 9 years ago, # ^ | ← Rev. 3 →   0 (B rev_B) and (rev_B B) are not allowed: there are no two successive boards of the same type Update: the upper comment has been changed. See reiracofage's comment below.
•  » » » 9 years ago, # ^ |   +9 But "A, rev_B" is equal to "rev_A, B" according the statment...
 » 9 years ago, # |   0 I took a look at the last example case and “deduced” that rotation also matters in the sequence comparison… I was getting WA locally for a long time, because that was not so clear from the problem statement, but I finally got it when there were about 10-15 minutes left; otherwise, I could have gotten C I think, using BIT :(
 » 9 years ago, # |   0 Does anybody know the solution to the Problem C? I try to use the Red Black Tree, but my answer is wrong..
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 It can be solved with treap.
•  » » » 9 years ago, # ^ |   0 Can I have the solution?
 » 9 years ago, # | ← Rev. 2 →   0 on a separate note, why isn't the system test starting?? [NOTE: I said this at the time when the blog did not contain the update; don't get this wrong :)]
•  » » 9 years ago, # ^ |   +3 There is a mistake in author's solution for problem E. Now authors are trying to fix it.
•  » » » 9 years ago, # ^ |   0 would that mean the problem would get invalidated? the last example case would not be reconcilable... if the statement is wrong/example case is wrong, IT SHOULD HAVE BEEN ANNOUNCED during the contest. I took it as a case where the statement is wrong AND the example case is right...I think trying to fix the solution retroactively won't really work.
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   +6 This will be another unrated round now i think.
•  » » » 9 years ago, # ^ | ← Rev. 4 →   -7 I think there is no mistake, just a problem is missing something like: Two fences shall be considered the same if the corresponding sequences of fence boards' types and dimensions are the same.
•  » » » » 9 years ago, # ^ |   +2 Too much thinking :) Your version and the initial one are different problems. Let's just wait the officials. Don't overthink.
•  » » » » 9 years ago, # ^ |   +1 I think missing something is also a mistake. I spend some time thinking and coding another method, and found I get WA on sample 3.
•  » » » » » 9 years ago, # ^ |   0 yea, I had to change my solution assuming something not stated within the problem statement, so as to fit the example test case (I thought something was missing in the statement but moved on, being under a time pressure) ;P
•  » » » » » 9 years ago, # ^ |   0 I didn't have any idea to count different types of board sequence. Can you share your code ?you should get 18, on third sample.
•  » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 Got the same answer. I wrote recursive DP with some hashes, comparing them at the end of recursion.UPD: My Code here:
•  » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 Usual dynamic programming, but as it will count duplicate cases also (like the ones on which author solutions are wrong) there is a way to count the number of these duplicate sequences separately and then subtract from original answer. To calculate duplicate cases, you need to consider the quantities of equal boards with different types, for example if there are K boards with the same size A x B and if required length is divisible by (A + B), then there are K * (K-1) * (K-1) * ... * (K-1) duplicates ((K-1) is repeated (length / (A+B)) * 2 — 1 times).
•  » » » » » » » 9 years ago, # ^ |   0 Im not sure your solution be correct. there is a lot of possible paths (to build a fence), that have same sequence types with different width and length. I meant your solution doesn't count all paths.
•  » » » » » » » » 9 years ago, # ^ |   0 Show example in that case.
•  » » » » » » » 9 years ago, # ^ |   0 I have a close idea with yours during the contest. But I think the subtract method you mention works only for A[i]!=B[i]. If A[i]==B[i], you should have a different subtract method or deal with it when dynamic programming.
•  » » » » » » » » 9 years ago, # ^ |   0 I have excluded A[i] == B[i] during dynamic programming, you can just check if A[i] == B[i] then don't consider the variant when the board is rotated.
•  » » » » 9 years ago, # ^ |   -12 There is a bug in authors solution to problem E...Read the blog again...Its updated...I think this round is going to be unrated :(
•  » » » » » 9 years ago, # ^ | ← Rev. 2 →   -13 I respect your opinion but I think that should be rated for div 2 because several people made a big effort to solve other exercises, including me. Thanks.
 » 9 years ago, # |   0 system testing is in progress... what's admins final decision?
•  » » 9 years ago, # ^ |   0 See blog above: UPD2: the contest is declared unrated.
•  » » » 9 years ago, # ^ |   +1 it's a pitty
 » 9 years ago, # | ← Rev. 3 →   0 I didn't consider to types of board, just i checked rotation of square board with same type shouldn't count twice, and got Accepted! I think something is wrong yet.
 » 9 years ago, # | ← Rev. 6 →   0 My comment was wrong, sorry...
•  » » 9 years ago, # ^ |   -8 Right, you suddenly decided that your comment became wrong the moment it got downvoted a lot :)
 » 9 years ago, # |   0 Whats case 15 in Problem C?
•  » » 9 years ago, # ^ |   0 Try this smaller test cases: 7 6 -4 2 -2 -4 0 3 5 2 out 16 7 2 5 1 -3 -4 -1 -5 1 1 `out 7
 » 9 years ago, # |   0 In problem A, "Vasya moves at speed 1 meter per second in either direction." This makes it seem like he can move in either horizontal or vertical direction. This poor choice of words really confused me.
 » 9 years ago, # | ← Rev. 2 →   -8 spending my time from 22.00 — 02.00 waiting the systest while I have mid test in the next day and the contest end with unrated. . what a pitty. .
 » 9 years ago, # | ← Rev. 2 →   0 Comment deleted after a bit of thought, for more details read my reply 2 branches down this comment :)
•  » » 9 years ago, # ^ |   0 Oh seriously, how the hell is that anywhere near a trivial question or a "bad contribution to the community" that it gets downvoted?
•  » » » 9 years ago, # ^ |   +6 Is it a good contribution or a non-trivial question, really? :-)On a serious note, the editorial is already published here, it's just not translated into English yet. Most problem setters on Codeforces are Russian-speaking, so translating editorials takes longer than writing them, and it's a lot of work. Have patience.
•  » » » » 9 years ago, # ^ |   -8 Yeah, thanks Nickolas. I'm not trying to justify my comment or anything; but I was frustrated about my bad performance yesterday :) To tell you the truth, I think I don't actually care about the editorial, I just wanted something to complain about. Sorry and thanks again!
•  » » 9 years ago, # ^ |   +1 There is russian one
•  » » » 9 years ago, # ^ |   0 Thanks!
 » 5 years ago, # |   0 How did so many manage to solve E during the competition? It only passes if you make the same mistakes as the author; the answer to the first test case should be 3 since the second board lying down is a beautiful fence as well. You can see on the second test case that just having one board is okay.
 » 3 years ago, # | ← Rev. 3 →   0 Very old blog, but incase someone is stuck on problem C like I was, the idea is to maintain a set of K maximums using two sets.