### Berezin's blog

By Berezin, 5 years ago, translation, ,

Hi everybody!

When you've seen my nickname you probably thought: "Finally! At least this round is not made by Sereja! And you are right! I, Dmytro Berezin(Berezin) give this round... and my neighbour Sergii Nagin(Sereja)

The action will take place in Friday, 25th october, 19:30.

Thanks to Gerald Agapov(Gerald) and Maria Belova(Delinur) for help in preperation and translation of problems respectively.

Thanks to Yaroslav Tverdokhlib(KADR) for help in testing.

You have to help Dima equip his personal life :)

The point values for this cause is 500 1000 1500 2000 3000.

I highly recommend you also to try to solve them.

Thank you for your attention, and have a successful round!

•
• +189
•

 » 5 years ago, # |   +9 I hope that it will be a good contest for every point of view as Sereja's contests.
•  » » 5 years ago, # ^ |   -8 I hope so )
 » 5 years ago, # |   +48 the law of conservation of Sereja : Sereja can be neither created nor destroyed, but he always go from a contest to another contest!
 » 5 years ago, # |   +15 I hope you guys have managed to solve the problem with the servers from last time.
•  » » 5 years ago, # ^ |   +8 Testing was a breeze. Thanks a lot guys.
 » 5 years ago, # |   0 I hope that the English problem set is not the same level of English as this post!
•  » » 5 years ago, # ^ |   +22 I am really sorry for the level of my English, if you read my bad-english post attentively, you will find, that english problems are not translated by me.
•  » » » 5 years ago, # ^ |   0 What?? You have advanced level Enlish in university and bad English at codeforces))
•  » » 5 years ago, # ^ |   0 problem set is level of English? do you knoving engrish?
 » 5 years ago, # |   +12 Sereja is a hard-working and good problem setter :)
 » 5 years ago, # | ← Rev. 5 →   0 good luck all :)
 » 5 years ago, # |   +9 I hope it will be a interesting contest and everyone will enjoy and learn more knowledge from this contest .
 » 5 years ago, # |   +2 I don't know if I'm the only one but I'm having tough time understanding the statements.This is the first time it has happened to me since I've joined CF. :(
 » 5 years ago, # | ← Rev. 2 →   -11 Why so hard-thinking & tough understanding problems in this round... Dying for none solved problem...
 » 5 years ago, # |   -8 a very awful only DIV 2 contest
 » 5 years ago, # |   +8 Could someone explain solution of Problem D?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 DP problem: DP[i][j] 1<=i<=n 0<=j<=1DP[i][0]=the answer of the first i hares when before i,feed i-1;DP[i][1]=the answer of the first i hares when before i-1,feed i;final answer will be max(DP[n][0],DP[n][1]); sorry for bad english.
•  » » 5 years ago, # ^ |   0 I'm still not sure if this solution will be accepted, but here's a simple one:State is the current hare and a flag whether the last hare that was processed was fed before the current one: 1 if it was fed before, 0 if not. So if the last hare was fed before the current one the value for this state is max(b[current]+state(current+1, 1), c[current]+state(current+1, 0)). Otherwise it's max(a[current]+state(current+1, 1), b[current]+state(current+1, 0)). The reason why this works (I hope) is because the only thing you care is whether the current hare was fed before the current-1 and whether it was fed before the current+1.
 » 5 years ago, # |   +45 Problem CTell all extracted numbers to Inna and then empty all containers. I guess lots of people who got WA#10 didn't see then empty all containers.
•  » » 5 years ago, # ^ |   +4 Also I found a bit tricky that the sequence of operations doesn't necessarily end in 0, so you can do whatever you want with the last numbers.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 yes my very first submission failed on this test case (pretest 3).but there was another tricky case is when there are more than 3 elements before a 0 with the same maximum value (pretest 5). example 5 5 5 5 0 this failed my second submission 4886056 :Pmy third 4887916 passed all the pretests, and, thankfully, the system tests! :)
•  » » 5 years ago, # ^ |   0 I am one of the victim :( .
•  » » 5 years ago, # ^ |   +3 oh my god...i missed that... so sad......
•  » » 5 years ago, # ^ |   +3 I missed the exact same point!
 » 5 years ago, # |   0 What a great problem for C! One of the trickiest problem i've ever seen. Fully apprecieted, thanks @Sereja!Although, i spent too much time on it. After i solved it [as i think now, before system test :D], this problem idea made my day! Nice~!
•  » » 5 years ago, # ^ |   +3 It was Dima's problem)
•  » » » 5 years ago, # ^ |   0 Oh, i see ... Thanks a lot @Berezin !
•  » » » » 5 years ago, # ^ |   +3 Thank you :)
 » 5 years ago, # |   0 please explain problem c for me I dont understant that
 » 5 years ago, # |   0 I'm quite astonished. After finishing C, I wrote a DP solution for D, but that runs in O(N^3). After getting TLE in pretest 12, I just had one minute left so I just limited the internal loop to 100 iterations, so the DP would not be computed correctly in some cases. But still, my solution passed the final tests. So lucky :D4890679
 » 5 years ago, # |   0 here is my problem C, wrong answer on pretest 3 http://codeforces.com/contest/358/submission/4890344 pretest 3, give 0 as n, which is totaly against what it says in the problem: The first line contains integer n (1 ≤ n ≤ 10^5) — the number of Inna's commands.
•  » » 5 years ago, # ^ |   0 The input of pretest 3 is clearly seen:2 0 1So, I advice you to check it again more carefully.
•  » » 5 years ago, # ^ |   0 yeah i figured it out, nothings wrong
 » 5 years ago, # | ← Rev. 2 →   +7 very quick system testing for 3500+ users. problem A gets severely affected.
 » 5 years ago, # |   0 In problem B it was mentioned that message size will not exceed 10^5 but test 24 was. 100000 i . . i For which message size will be atleast 3*10^5 . It cost me WA . Its cheating. :'( :'( . Someone must look into this.
•  » » 5 years ago, # ^ |   +1 Not really, it would have to be at least 3*10^5 if the answer was yes, but it's no.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 no, the problem only guaranteed total length of all words doesn't exceed 10^5 which is valid for that test, and that doesn't mean it also guaranteed all words + '<3' also will not exceed 10^5
•  » » 5 years ago, # ^ |   0 Not really. It does not say that the text message will contain all the read words.
 » 5 years ago, # |   0 how did so many users fail the system tests of problem A?? o.Owas there a tricky case? there must have been one, because it's impossible that so many users were incorrect with their ideas!
 » 5 years ago, # |   0 Can someone explain how Prob A is to be solved? I started off wrongly and got entangled, realizing mistakes after every wrong attempt.
•  » » 5 years ago, # ^ |   0 the only way there is a self-intersection is, when there are 4 points of the form i j i j, meaning that a semicircle goes from point 1 to point 3, and also another goes from point 2 to point 4.
•  » » » 5 years ago, # ^ |   0 a.k.a you have two segments, given by coordinates x1a,x2a(left,right) and x1b,x2b(left,right) and the first should start before(strictly) the second and should end before(strictly) the second
•  » » 5 years ago, # ^ |   0 There are four cases, handle them and you get AC:let A,B be the last two points entered, and C,D be each pair entered before. These patterns are the only one producing entanglement:ACBD BCAD CADB CBDA(Note that if you have XYZ entered before, you handle the pair (x,y), then (y,z), etc)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 actually the cases can be reduced if A = min(x1,x2) and B = max(x1,x2)
•  » » » » 5 years ago, # ^ |   0 Yes, that's one way to handle them :)I also forgot to add that it has to be enforced that A
•  » » 5 years ago, # ^ |   0 it is easy to check when they do not intersect, so you have [a1,b1] and [a2,b2].they do not intesect if b1=a2 && b1<=b2) || (a2>=a1 && b2<=b1) example:E1:([4,7] AND [1, 8] ) E2: [1,8] and [4,7]) so you check every connected pair of points.
•  » » 5 years ago, # ^ |   0 Thank you, everyone! :) I got it! Consider x1, x2, x3, ... , xn. Make pairs (A,B) for all x(i),x(i+1) such that: A=min[x(i) and x(i+1)] and B=max[x(i),x(i+1)]Now, consider 2 segments (P,Q) and (R,S).P ---------------------- Q'R' can lie either within PQ or outside it. If R lies outside, R---P--------------QS can either lie outside or inside. If S lies inside PQ, then there is an intersection, else there is not.R---P------S-------Q (intersection) R-S-P--------------Q or R---P--------------Q---S (no intersection) If R lies inside PQ, P -------------R-----QIf S lies Outside PQ, then there is an intersection, else there is not.P -------------R-----Q---------S (intersection) P -------------R--S--Q ( no intersection)So, it is just 2 cases we have to check, if we make a min/max pair.
•  » » » 5 years ago, # ^ |   0 Actually you can get past the problem with brute force( O(n^2) ) by treating only one case.
 » 5 years ago, # | ← Rev. 2 →   0 Awful translation, made me unable to solve problem D. If hares 1 and n only have one neighbour they should be unable to be in the state where they have both neighbours full or empty but in the first test case it is clearly visible that the answer is 4+3+2+4 or 4+2+3+4, both cases leading to the last hare getting its happiness from BOTH his neighbours being empty (what an evil hare!!!)Can someone explain that?By the way, Sory for mi bad englando!
•  » » 5 years ago, # ^ |   +1 What's the problem, then? The sample clearly explains that question. That's what the samples are for — clarifying the problem statement (and testing the program, of course).And it kind of makes sense, if you imagine the happiness values given per number of full adjacent hares, which is at most 1 for the border hares.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 "Inna knows how much joy a hare radiates if it eats when either both of his adjacent hares are hungry ... or both of the adjacent hares are full".Last time I checked both was considered as being two.
•  » » » » 5 years ago, # ^ |   0 Yeah, the translation isn't precise, I give it that. But I'm saying it shouldn't pose a problem in the contest, as long as you look at the samples and try to understand them carefully.
•  » » » » » 5 years ago, # ^ |   0 Being less than precise, it's contradictory.I understand that nobody is perfect and I do not mind grammar and other translation mistakes but the fact that annoyed me was that at the question :" In the first test case, to get to 13 happiness the last rabbit should be fed before both his adjacent hares ("Number ai in the first line shows the joy that hare number i gets if his adjacent hares are both hungry") but this would be imposible because the last hare does not have two adjacent hares. What should be done? "I received: "Read the problem statement."
•  » » » » » » 5 years ago, # ^ |   0 I'd have replied something along the lines of "That's allowed" instead, since the inclarity really comes from the problem statement being what it was.But the way I see it, you're nitpicking about formal correctness too much during a contest, and that might have cost you points. You really could've just decided based on the samples, instead of asking. (I try to understand the samples instead of the statement quite often :D)
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I understand that I might be too strict about these things but I learnt from life( pointing at programming contests ) that If you don't make sure of every last detail you will most certainly regret it later.And along the lines of understanding the problem from the sample cases, why not go as far as to give the contestants only the sample input and output: "Let them figure out the problem statement!" ?
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Trust me, there are much worse statements. Here, the basic idea of the problem was clear, yours was just a minor question. For example, I didn't even think about it (but I would, if there was an answer "Impossible" mentioned in the statement) when I read the problem. (Apart from it being formally incorrect, ) it's not nearly as bad as you make it seem.I guess it just takes experience with reading problem statements.
•  » » » » » » » » » 5 years ago, # ^ |   +3 "Just because other kids do drugs at his age we should go easy on our own for skipping school."(or something along those lines)Besides, not everyone has the same mentality:While you and probably the majority of the "red community" could make out a poorly formulated problem from the available test cases, I and maybe others below the "purple grade" will have difficulties in understanding it. To be fair for everyone, why not make it correct?
•  » » » » » » » » » 5 years ago, # ^ |   +4 Lol, it says my comment can't be nested anymore. We need to go deeper :D (Maybe it's best to consider this the end of discussion, since we don't really have more to add.)On topic: yeah, I'm that kind of guy. I simply accept small imperfection (and bash at large one that much more :D). Of course, all is a matter of opinion. I just want to say what I think about it. But it may be precisely because of mentality that I got this far — to be precise, it's "if you aren't doing well enough, just try to improve as much as possible". Things like this, I take as a challenge. I still have ways to go, though. Red is just the "can solve easy/medium problems in time" level.
 » 5 years ago, # | ← Rev. 3 →   0 Very nice round — congrats to writers — , but I think that you sould put more pretests if you make statements that request answers "yes"/"no".
 » 5 years ago, # |   0 Does E involve eulerian/hamiltonian paths?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Yes, it involves Euler tours on an undirected graph.First, vertices: for each possible K you can extract a graph of which points were directly visited: Assuming the upper-leftmost point is at (sx,sy) then exactly all points of the form (sx+i*k, sy+j*k) are intermediate positions for the victim.The remaining '1's indicate moves from one intermediate point to another, so if there is an unbroken line of points between (x,y) and (x+k,y) or (k,y+k) then an undirected edge should be added between them.A valid sequence of kicks corresponds to an Eulerian path through this graph, so you just need to apply the standard algorithm for verifying that one exists.
•  » » » 5 years ago, # ^ |   0 We'll have to consider àll unit squares as starting points right? What exactly is a semi-Eulerian path?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 I was taught that a fully-Eulerian path starts and ends at the same vertex, but a semi-Eulerian path begins and ends at distinct vertices. (upd.: above definition is wrong.)In the former case, any vertex will do as a start point because the tour is closed and cyclic.In the latter case, the two endpoints will be the only ones with edges.length()%2 == 1 and either will do as a start point.In practice you don't need to explicitly identify start and end points -- you can just check that the graph is connected and has either 0 or 2 vertices with an odd number of edges.
•  » » » » » 5 years ago, # ^ |   0 Ok, thanks!
•  » » » » » 5 years ago, # ^ |   +8 Interesting, I was taught that a Eulerian circuit starts and ends at the same vertex, while a Eulerian path in distinct vertices.
•  » » » » » » 5 years ago, # ^ |   0 Yes, after a quick check it turns out that "fully-Eulerian" and "semi-Eulerian" are supposed to describe graphs, not paths.Maybe my teacher was a little confused. Alternatively, maybe it's time to invest in a hearing aid and/or start paying more attention in lessons.Revised the wording -- thanks!
 » 5 years ago, # |   0 Sorry but for B, why this case is a "yes" ? 3 i love you <3i<3love<23you<3ww I thought he can only insert "digit", "<" and ">"
•  » » 5 years ago, # ^ |   0 Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 oh I missed that, so sad :( small characters mean "lower case" right?
•  » » » » 5 years ago, # ^ |   0 yep
•  » » » » » 5 years ago, # ^ |   +6 by the way the accepted solutions output is "yes" for 3 i love you <3i<3dont<3love<3you<3
•  » » » » » » 5 years ago, # ^ |   0 as "dont" can be counted as " a random number of small English characters, digits, signs "more" and "less" into any places of the message. " it is within the bounds of the statement
•  » » » » » » » 5 years ago, # ^ |   0 The contest is over, so now we can see the truth: Dime will never send such sms, so the answer is "no" :) P.s. but the comment above is correct when speaking about contest rules.
•  » » » » » » » 5 years ago, # ^ |   0 as a matter of fact it's not an encoding, decoding system, the better way was not using the terms encoding and decoding, the translation is one way it should be noted finally I should thank the writers there is a little mistake doing a great work
•  » » » » » » 5 years ago, # ^ |   0 haha :D
•  » » 5 years ago, # ^ |   0 costed me 3 WAs, but finally ACed
 » 5 years ago, # |   0 Tired of being victim of overkill :( Solution of B was doable in 10 lines, instead I choose the long way..
 » 5 years ago, # |   0 Could anyone help me why my submission 4899840 can't pass Test 12?
•  » » 5 years ago, # ^ |   +3 For: 3 i love you <<<<3333iloveyouYour code outputs yes while it should output no. The problem with you code is that it does not check if the characters are in the right order i.e (<3word1<3word2...), it just checks if they are there. It's something similar to this: If your program would check if two words are the same, the words "love" and "elov" would be the same.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Thank you so much for answering. I found where the problem of my code is with your help. I changed pos=sts.find_first_of(s[i]); in my code to pos=sts.find_first_of(s[i],pos); and it was accepted successfully. :)
 » 5 years ago, # |   +3 Loved the contest. Just depicts where a contestant's reading and interpretation skills stand.
 » 5 years ago, # |   0 I wrote the code for Dima and the Text Messages in CodeForces Round 208 division-2 in Java. Every time I submit the code it says TLE. But don't know why it says so even if I am using BufferedReader and PrintWriter for reading and printing the values. My solution code in 4901148.
•  » » 5 years ago, # ^ |   0 In Java a + b is slow for strings (copies both a and b), you have to use StringBuilder.append() instead.