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!
Good luck all.
3000 point problem In both division :O . That would be amazing (either for solving or learning) :)
3000!! Is the problem something like writing an OS? :)
Yeah, perhaps more difficult. \m/
For problem B div 1, substring means contiguous sub-sequence?
Did you know that there is "Ask a question" function here?
I asked the same question during the contest, and they said "NO".
[Edit] 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.
Weird. I asked this question too, and they said "yes".
div1, B. What if (k > n) ?
mn
Я час потратил, чтобы это понять. В конце от безысходности изменил так условие и прошло:(
какого чёрта? "строк длины ровно n", "ПОДСТРОКА длины В ТОЧНОСТИ k". у меня у одного проблемы с пониманием того, как любая строка может подходить?
Покажи мне хоть одну подстроку длины 42 в строке abacaba, которая не является палиндромом.
спасибо. условия кривоватые.
any string is OK. So ans in mn
Than any string will do as there is no restriction
Why is that... when k>n there doesn't exist any string satisfying the constraint shouldn't the answer be zero...?
We do not need a string, that should satisfy the constraint. We just required that ANY string must satisfy the constraint
That's totally misleading statement... :( (or I was too stupid to figure out at the time :P)
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 :)
I also thought 0. :(
Me too. The problem statement is not well written.
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.
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."
I asked if for K > N is 0 correct answer and reply was "no".
[Posted to the wrong position] I am really sorry.
why the answer is not 0? I got lots of wrong answer on case 3..
Here is your answer ;-)
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.
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.
Statement for D was also changed.
Do they only happens in the English version?
If D also changed then they really should have updated the problems page with that message.
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...
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
I was the same
Same here... somehow did not get the clarification broadcast, couldn't understand what's wrong before refreshing out of despair
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.
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
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."
I think it should be fair to make this round unrated. Lots of problems came up and affected vast of coders.
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.
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.
Can anybody tell me what is the problem with using below code in problem B div 2?
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.
Because
'\b'
is a char too. It doesn't have any special meaning outside terminal.Does
\b
mean backspace ?Yes, it does.
Thanks.
'\b' only means backspace on terminal, but it cannot erase you already output in the stream.
Thanks.
Ah, I very much like what you were trying to do. Those final ','s are so annoying :)
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.
Divided != divisor. If text was "...from one and from the divisor number itself", you'd have been right.
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!
Conductor should choose C and D for each passenger.
For each passenger conductor may choose his own [C;D] in [A;B]. This segments [C;D] may be distinct for various passengers.
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.
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.
Thanks for the clarification! That was not at all clear from the problem statement.
The Problem C's description's change waste a lot time of me or someone else...I think today's round should be unrated>_<...
+1 and Orz
ym clj!!! I think the sample 1 is too simple, and it is hard to work out sample 2 by hand.
Problems were nice.
I think each contestant should be able to decide if their rating is updated for this round.
lolwut? A round should be rated or unrated for ALL. If not our ratings would become inflated and meaningless.
This has been done before. I guess that'll make everyone happy at least.
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.
I think it should be unrated for all.
And I don't think so.
There were problems with statements in D and E.
And I still don't think so.
Problem D of Div. 2 sucks when k > n.
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.
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.
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++.
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.
If there is going to be a voting, then count me for unrated. (I cannot keep refreshing the page , sorry, I have exam tomo.)
Very bad, that it is rated. X-(
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"
Could you elaborate? What's the difference in this context?
"aaaab" satisfies any substring of length 4 which is Palindrome. but does not satisfies "all" substring of length 4, since aaab is not palindrome.
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 ?
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.
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
What should the output for the following case for problem B (div2) be?
My Output is:
System answer is:
Haven't both Alex and Mula got the same number of phone numbers of each type?
Can someone please spot the issue with my output. Thanks.
Ok, I figured the issue. Thanks.
Taxi numbers consist of six identical digits
. 12-12-12 isn't taxi number, that's your failGot it, thanks.
Why? Alex don't has a taxi number, but has "other" number. Both have one pizza number
Yep, I messed up the check for taxi numbers. Thanks.
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.
This was my challenge. Sorry about that!
forever blue
С возвращением =)
Может, стоит сменить ник и аватар?
смени
Я не голубой и не синий(где же Петросян с его намеками?)
Great :D I want that to be in unicode!
editorials from the author???
English version will appear tomorrow. Sorry for delay.
Could you please give specific examples of confusing phrases in English statements?
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).
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!
Upsolving the contest after 9 years, still couldn't get what Div. 1 C is asking until I read the comments.
No, I still don't understand what should I calculate.