### GlebsHP's blog

By GlebsHP, 8 years ago, translation, ,

Hello everybody!

Today's round will be held by SergeiFedorov and me. We have done our best to make it diverse (different task complexity and themes) and rated (we know it's important). Your questions, wishes and constructive criticism (destructive we already can do :-)) leave in comments.

The contestants will plunge into the cold February of Nvodske and will be to help one's friends to survive the cold. Just imagine all responsibility!)

On this occasion I would like to thank all Codeforces team for the great job, they are doing, Artem Rakhov (RAD) for his help in task preparations, Maria Belova (Delinur) for problems translation, my mom, my dad, our soundman and Tuscany winemakers, for us didn't fall ill while preparing this round.

Distribution will be something like:

div. 1: 500-500-1000-1500-3000 (yeah, it really costs 3000)

div. 2: 500-1000-1500-1500-3000

Good luck & have fun!

• +218

 » 8 years ago, # |   +5 Good luck all.
 » 8 years ago, # |   +11 3000 point problem In both division :O . That would be amazing (either for solving or learning) :)
 » 8 years ago, # |   +42 3000!! Is the problem something like writing an OS? :)
•  » » 8 years ago, # ^ |   -7 Yeah, perhaps more difficult. \m/
 » 8 years ago, # |   +11 For problem B div 1, substring means contiguous sub-sequence?
•  » » 8 years ago, # ^ | ← Rev. 2 →   -22 Did you know that there is "Ask a question" function here?I asked the same question during the contest, and they said "NO". I was wondering why I am getting negative votes, but when I read my question again,what I asked was 'Is "ac" a substring of "abc"?'.What a foolish mistake! I am sorry for the confusion.
•  » » » 8 years ago, # ^ |   +16 Weird. I asked this question too, and they said "yes".
 » 8 years ago, # |   +6 div1, B. What if (k > n) ?
•  » » 8 years ago, # ^ |   -8 m n
•  » » » 8 years ago, # ^ |   -6 Я час потратил, чтобы это понять. В конце от безысходности изменил так условие и прошло:(
•  » » » 8 years ago, # ^ |   -25 какого чёрта? "строк длины ровно n", "ПОДСТРОКА длины В ТОЧНОСТИ k". у меня у одного проблемы с пониманием того, как любая строка может подходить?
•  » » » » 8 years ago, # ^ |   -12 Покажи мне хоть одну подстроку длины 42 в строке abacaba, которая не является палиндромом.
•  » » » » » 8 years ago, # ^ | ← Rev. 3 →   -33 спасибо. условия кривоватые.
•  » » » 8 years ago, # ^ |   -33 По-моему раз нету подстрок "длины в точности k" то ответ 0.
•  » » » 8 years ago, # ^ |   -26 Хотя да.Согласен
•  » » 8 years ago, # ^ |   +8 any string is OK. So ans in m n
•  » » 8 years ago, # ^ |   +22 Than any string will do as there is no restriction
•  » » » 8 years ago, # ^ |   +3 Why is that... when k>n there doesn't exist any string satisfying the constraint shouldn't the answer be zero...?
•  » » » » 8 years ago, # ^ |   +2 We do not need a string, that should satisfy the constraint. We just required that ANY string must satisfy the constraint
•  » » » » » 8 years ago, # ^ |   +19 That's totally misleading statement... :( (or I was too stupid to figure out at the time :P)
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +5 If you've worked with logic you come to think like that.The statement "If 1=0 then 2=3" is always true, because 1 isn't 0. After some time you forget that that's not the way normal people think, (They think the statement doesn't make sense), and confusion can happen.However, I very much recommend thinking the logic way. It just works more often :)
•  » » » » 8 years ago, # ^ |   +24 I also thought 0. :(
•  » » » » » 8 years ago, # ^ |   +14 Me too. The problem statement is not well written.
•  » » » » » » 8 years ago, # ^ |   +4 When k > n, there are 0 substrings of length k. And there are 0 substrings of length k that are palindromes.0 = 0, therefore all substrings of length K are palindromes. In this respect, the problem statement was written correctly.However, it IS a common confusion specially if not familiar with how the "For every" quantifier works on empty sets. And after all, (n > k) is a silly test case to include — its only addition to the problem is this confusion. I think at least it would have been better if (k > n) was not allowed or was an example.
•  » » » » » 8 years ago, # ^ |   +32 Five minutes or so after receiving WA #3, I raised a clarification asking that, for K > N, whether I should output N^M or 0. And the reply I got is:"No comment."
•  » » » » » » 8 years ago, # ^ |   0 I asked if for K > N is 0 correct answer and reply was "no".
•  » » 8 years ago, # ^ | ← Rev. 2 →   +9 [Posted to the wrong position] I am really sorry.
•  » » 8 years ago, # ^ |   +1 why the answer is not 0? I got lots of wrong answer on case 3..
•  » » » 8 years ago, # ^ |   0 Here is your answer ;-)
 » 8 years ago, # |   +35 Though my rating may increase i think this round should be unrated. CF was down for about 7-8 minutes and also got down several times last 20 minutes. I lost valuable points because of server down,it got down just when i tried to submit C,and i had to wait for 7-8 minutes to submit it.
•  » » 8 years ago, # ^ |   +27 The worst part is that the problem statement for C changed. I didn't check the statement again and spent lots of time trying to produce correct output for C.
•  » » » 8 years ago, # ^ |   +8 Statement for D was also changed.Do they only happens in the English version?
•  » » » » 8 years ago, # ^ |   0 If D also changed then they really should have updated the problems page with that message.
•  » » » » » 8 years ago, # ^ |   +3 I mean really, there are messages for problem C/E so that if you read 'undefined' in a popup you will get to know that the problem statement was changed.But if dolphinigle's report that D changed is true, then there should have at least be a note in the problems page saying that it was changed...
•  » » » » » » 8 years ago, # ^ |   +2 It was sort of minor I suppose (replacing "until" with "while"), though it did cost me some good time, since I turned off my common sense during programming contests.Maybe I should rethink that protocol :S
•  » » » 8 years ago, # ^ |   +5 I was the same
•  » » » 8 years ago, # ^ |   +16 Same here... somehow did not get the clarification broadcast, couldn't understand what's wrong before refreshing out of despair
•  » » » » 8 years ago, # ^ |   +24 I've got a javascript alert which said "undefined". In last contest i've got same alert and than found that my solution have been hacked. But this time it was the clarification. Hope admins will fix it soon.
•  » » » » » 8 years ago, # ^ |   +8 Ahh... There WAS also that "undefined" alert box for me. Somehow I wasn't in the mood or something I didn't think much about it and simply ignored the alert. Now that you've mentioned it there was indeed the JS alert box with unknown intention... Should have thought it's trying to tell me something though :p
•  » » » » » » 8 years ago, # ^ |   0 Indeed when I got this "undefined" prompt, I had a first impression that, this may be due to some bugs in Codeforces system, or admin accidentally broadcasted a wrong message. (Meanwhile I was busy thinking for problem C sample test case #2, and I simply ignored the box.)Perhaps I did this because in previous codeforces testing round, there was some prompt like "Don't worry, it's just a testing."
 » 8 years ago, # | ← Rev. 2 →   +14 I think it should be fair to make this round unrated. Lots of problems came up and affected vast of coders.
 » 8 years ago, # |   +8 What datastructure do you need for maximum subarray part of div 1 C? I was thinking maybe use a segment-tree with several fields for combining the segments in the tree.
•  » » 8 years ago, # ^ | ← Rev. 3 →   -13  double mn = 0, sum = 0.0; for (int i = 0; i < n; i++) { sum += y[i]; mn = min(mn, y[i]); res = max(res, sum - mn); } 
•  » » 8 years ago, # ^ |   +3 It can be done without segment tree.For each interval [a,b] its length(b-a+1) can be uniquely represented in binary number system.Let this number has m ones in binary form: length=2^k1+2^k2+....2^km..(k1>k2>...>km)..Then we can solve for intervals [a,a+(2^k1)),[a+(2^k1), a+(2^k1+2^k2) ),.... individually and also check for the subarrays which lies in several consecutive intervals.
 » 8 years ago, # |   +1 Can anybody tell me what is the problem with using below code in problem B div 2? cout << "\b." << "\n"; it was working fine on my system but was giving wrong answer on pretest and also on custom as it wasn't erasing last ",". It cost me 2 penalties :(. Solution id 1192671.
•  » » 8 years ago, # ^ |   +13 Because '\b' is a char too. It doesn't have any special meaning outside terminal.
•  » » » 8 years ago, # ^ |   +1 Does \b mean backspace ?
•  » » » » 8 years ago, # ^ |   +1 Yes, it does.
•  » » » 8 years ago, # ^ |   0 Thanks.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 '\b' only means backspace on terminal, but it cannot erase you already output in the stream.
•  » » » 8 years ago, # ^ |   0 Thanks.
•  » » 8 years ago, # ^ |   0 Ah, I very much like what you were trying to do. Those final ','s are so annoying :)
 » 8 years ago, # |   0 C-Div2. "Number's divisor is called non-trivial if it is different from one and from the divided number itself."I thought it means that for number N, the divisor d should not be equal to 1 and N/d. But now my friend tells me that it meant not 1 and not the number itself.Now, it makes sense. But why add the word "divided"? I took the long route of solving the problem because of this condition and now it is wrong.
•  » » 8 years ago, # ^ |   0 Divided != divisor. If text was "...from one and from the divisor number itself", you'd have been right.
 » 8 years ago, # |   +10 Can anyone explain how the solution to the second example case of Smart Cheater is constructed?I thought the conductor should not sell tickets for the last four segments, resulting in an expected profit of 466.32 + 973.55 + 2537.56 + 72802.56 = 76779.99, but this 80 less than the reference output. I can break down these numbers further if it helps, but I wonder what I'm missing here!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +10 Conductor should choose C and D for each passenger.
•  » » 8 years ago, # ^ |   +13 For each passenger conductor may choose his own [C;D] in [A;B]. This segments [C;D] may be distinct for various passengers.
•  » » » 8 years ago, # ^ |   +5 I got the same output as Soultaker. (And of coz, after quite considerably long time to find that the problem C's statement is updated.) The problem statements are so ambiguous... I could only understand it right now.
•  » » » » 8 years ago, # ^ |   +35 I think that these ambiguities are due to the English translations. The problem setters are usually programming contest veterans, so I assume they know how to write clear and unambiguous problem statements, but those qualities may be lost in translation.For example, for this problem, I think for this part:However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments [A, C] and [D, B], or not sell the ticket at all.The original Russian text reads:Однако кондуктор может не продать пассажиру билет от остановки c до остановки d (c < d), или вовсе не продавать билет. Более формально: Кондуктор выбирает не более одного отрезка с C по D (C <= D) на который он НЕ ПРОДАЕТ БИЛЕТ.I don't know Russian so I'm not entirely sure whether this is much more clear, but at least I spot the word "пассажиру" (meaning "passenger") in there. The English version doesn't mention the word "passenger" at all, and in fact underscores that there is a no more than one segment chosen by the conductor.I can't complain too much, though, as there were plenty of non-Russian competitors that were able to solve this problem, presumably using the English translation. Still, I would enjoy these contests more if for me there would be more actual problem-solving involved and less figuring-out-what-the-problem-is, especially since the problems on CodeForces (once I understand them) are often quite interesting.
•  » » » 8 years ago, # ^ |   0 Thanks for the clarification! That was not at all clear from the problem statement.
 » 8 years ago, # |   +78 The Problem C's description's change waste a lot time of me or someone else...I think today's round should be unrated>_<...
•  » » 8 years ago, # ^ |   +1 +1 and Orz
•  » » 8 years ago, # ^ |   +3 ym clj!!! I think the sample 1 is too simple, and it is hard to work out sample 2 by hand.
 » 8 years ago, # |   -27 Problems were nice.
 » 8 years ago, # |   +34 I think each contestant should be able to decide if their rating is updated for this round.
•  » » 8 years ago, # ^ |   +2 lolwut? A round should be rated or unrated for ALL. If not our ratings would become inflated and meaningless.
•  » » » 8 years ago, # ^ |   +1 This has been done before. I guess that'll make everyone happy at least.
•  » » » » 8 years ago, # ^ |   +5 Neither of them are good reasons to do such thing. I think frank44 is right about the risk of inflating ratings if a vote becomes a habit.
•  » » 8 years ago, # ^ |   -7 I think it should be unrated for all.
•  » » » 8 years ago, # ^ |   -11 And I don't think so.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 There were problems with statements in D and E.
•  » » » » » 8 years ago, # ^ |   0 And I still don't think so.
 » 8 years ago, # |   +24 Problem D of Div. 2 sucks when k > n.
•  » » 8 years ago, # ^ |   0 It really doesn't. While it's a bit of a "silly" case it makes perfect sense. The requirement is that all substrings of length k should be palindromes. Since there are no substrings of length k, all strings pass. It makes perfect logical sense.
 » 8 years ago, # |   +25 Many people complained about the not working announcements before. It always says undefined whether it's a hack or announcement. It has been like that for at least 3 round. Could you please fix it.
 » 8 years ago, # | ← Rev. 2 →   -26 This is another contest where I've run into problems with writing solutions in Python. This time I spent AN HOUR trying to figure out why my solution for C div2 gets TLE. I didn't even care to check other problems because this one was so frustrating. After the contest, when I ran my solution locally, it turned out that on one of testcases in Codeforces environment it took 2000ms, whereas on my machine it took < 700ms. I vote for adjusting the time limits to the runtime performance of languague, in a similar manner as Codechef does. Otherwise there's no sense in allowing to write solutions in Python, knowing that it might fail, even though the same algo would run within limits in C/C++.
•  » » 8 years ago, # ^ |   +36 Choosing right language is a part of problem solving process.I use Python for almost all problems on Codeforces, because it's often much faster to code solution in it (for example, for today's "Quantity of Strings" it has built-in modular exponentiation).But for some problems Python is not fast enough, it's OK.Also you can use "custom test" functionality to test execution time on the Codeforces server.
 » 8 years ago, # |   +7 If there is going to be a voting, then count me for unrated. (I cannot keep refreshing the page , sorry, I have exam tomo.)
•  » » 8 years ago, # ^ |   -27 Very bad, that it is rated. X-(
•  » » » 8 years ago, # ^ |   -6 How can you make it rated ? Problem B (div1) :: "Any its substring of length k" should have been "**All of** its substring of length k"
•  » » » » 8 years ago, # ^ |   +5 Could you elaborate? What's the difference in this context?
•  » » » » » 8 years ago, # ^ |   -9 "aaaab" satisfies any substring of length 4 which is Palindrome. but does not satisfies "all" substring of length 4, since aaab is not palindrome.
•  » » » » » » 8 years ago, # ^ |   0 Also, in the case of k > n. behavior is undefined, so it should have been clearly mentioned what to do.By behavior being undefined, i mean to say, "any substring of length k", what of you mean by a substring of length 7 in a string of length 2 ?
•  » » » » » » » 8 years ago, # ^ |   0 You should count number of strings under the constraints mentioned in problem statement.If k is more than n , we have n^m possible strings.
 » 8 years ago, # | ← Rev. 2 →   -20 I think contest should be rated for we Div 2 because there was a problem in only E and I dont think it affected more than a 3-4 people ( only 1 person had solved before the updation of the statement at 7:47. So all of the people were doing the other problems then and I dont think anyone starts off with E especially when its 3000 UPD: And yes it is rated
 » 8 years ago, # | ← Rev. 3 →   0 What should the output for the following case for problem B (div2) be? 2 2 Alex 12-12-12 99-87-76 2 Mula 22-22-22 99-87-76 My Output is: If you want to call a taxi, you should call: Alex, Mula. If you want to order a pizza, you should call: Alex, Mula. If you want to go to a cafe with a wonderful girl, you should call: Alex, Mula. System answer is: If you want to call a taxi, you should call: Mula. If you want to order a pizza, you should call: Alex, Mula. If you want to go to a cafe with a wonderful girl, you should call: Alex. Haven't both Alex and Mula got the same number of phone numbers of each type? Taxi: Alex 1, Mula 1 Pizza: Alex 0, Mula 0 Girls Alex 1, Mula 1 Can someone please spot the issue with my output. Thanks.
•  » » 8 years ago, # ^ |   0 Ok, I figured the issue. Thanks.
•  » » 8 years ago, # ^ |   0 Taxi numbers consist of six identical digits. 12-12-12 isn't taxi number, that's your fail
•  » » » 8 years ago, # ^ |   0 Got it, thanks.
•  » » 8 years ago, # ^ |   0 Why? Alex don't has a taxi number, but has "other" number. Both have one pizza number
•  » » » 8 years ago, # ^ |   0 Yep, I messed up the check for taxi numbers. Thanks.
•  » » » 8 years ago, # ^ |   0 No. The problem statement says, the numbers of pizza deliveries should necessarily be decreasing sequences of six different digits (for example, 98-73-21) So, 99-87-76 is a call girl number.
•  » » 8 years ago, # ^ |   0 This was my challenge. Sorry about that!
 » 8 years ago, # |   +35 forever blue
•  » » 8 years ago, # ^ |   0 С возвращением =)
•  » » 8 years ago, # ^ |   -21 Может, стоит сменить ник и аватар?
•  » » » 8 years ago, # ^ |   +18 смени
•  » » » » 8 years ago, # ^ |   -9 Я не голубой и не синий(где же Петросян с его намеками?)
•  » » 8 years ago, # ^ |   +8 Great :D I want that to be in unicode!
 » 8 years ago, # |   +15 editorials from the author???
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 English version will appear tomorrow. Sorry for delay.
 » 8 years ago, # | ← Rev. 2 →   +5 Could you please give specific examples of confusing phrases in English statements?
•  » » 8 years ago, # ^ |   0 Aw, if you told us when we were preparing our contest months ago with your translation of statements, I would show you some places, we had fixed. But now I even don't remember what were the corrections.I think it's good practise to give someone English statements before the contest, so he could fix confusing phrases with you (or with one, who translates statements).
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +5 I usually have a look at the corrections applied to my translations after a contest so don't worry, the odds are I didn't miss those ones!Your idea is great but first, sharing problem statements before the contest might be against the Codeforces rules and second, I actually do check the phrases that seem confusing to me. What I'd like to know is what the programmers find confusing...Incidentally, do you know anybody who translates statements? I know only one linguist apart from me... Thanks for the sound advice!