Hello everybody!
Welcome all to Codeforces Round #131, which will be held on Monday, 30th of July at 19:30 MSK. I am (Sergey Nagin) an author of the problems. This will be my First Codeforces round and I hope it won't be the last one :).
I would like to thank Mike Mirzayanov(MikeMirzayanov) who made this contest possible, Roman Furko(Furko) and Gerald Agapov(Gerald) for helping to prepare this round and Maria Belova(Delinur) for the translation of problem statements into English. I hope that problems will be interesting for you.
Good luck!
Problems’ point values in Division 1 are 1000-1000-1500-2000-2500. Problems’ point values in Division 2 are 500-1000-2000-2000-2500.
I strongly recommend you to read ALL the problems.
The contest is over! Congratulations' to winners!
First division:
1 place: Egor
2 place: Petr
3 place: tourist
Second division:
1 place: antimatter
2 place: c175353
3 place: takaramono
I hope, that problems were interesting for you.
You can view tutorial.
Some personal information. This year I finished school and I will go to university. I study programming during almost five years. In addition to computer science, I like sports: powerlifting, arm wrestling and swimming.
so, we are gonna have some sports flavored problems!!
And everyone is in the olympics mood too!!
will the scoring be as usually or dynamic ?
Dynamic scoring is nearer and nearer to become 'usual & default' :)
UPD: not this time :D
Well usually when the contest only for DIV 2, it's using dynamic, and for both Division they usually use normal scorring IMO
I disagree..If you browse thorough the contests after Round #113(after dynamic scoring was introduced) you will find that apart from rounds #115 and #126 and all rounds from the trio NALP- Gerald-HolkinPV (which have dynamic scoring systems) ,,the scoring system has been traditional in other rounds. So I think they leave it on the authors to decide ..
Good Luck And Have Fun! :)
hacked by hackers
What said bad(he has -4)?
Don't try to understand negative votes on codeforces.
if comments have negative votes it is bad but lashabuxo-s comment i think is not bad.
If comment have negative votes — then somebody thinks it is bad.
How to run my program at local machine? Above is quickly enough?
g++ xx -o exe
exe < in.txtg++ code.cpp -O2 -o exe
g++ name.cpp && a.exe <in.txt ( in windows )
g++ name.cpp && ./a.out <in ( in linux )
Very interesting B question in Div-2..It made me so involved that I did'nt have the time to read C,D,E..But I am happy I managed to pass th pretest finally after 11 WA..
Some test example from Hacker.
Input:
3
0 0 0
Output:
000
Answer:
0
how can This Submission Pass the preetest but got compile error while Systest ?
Compilation Error на 10-м тесте facepalm
How is that even possible?
Great contest, thanks to all of you.
It seems java needs more space than C++. In div1-C I initialize a 3-D array and get MLE.
I did not look at your code but it may be the case of how you declared the array.
Arrays are objects in Java, so a[1000][1000][2] creates one million objects and a[2][1000][1000] creates only 2000. There is an overhead for each object.
If space is an issue, use a 1D array instead.
In the contest, I got many wrong answer on pretest 1 of problem D,.. After the contest, I found out the mistake, only one mistake: 10.0 => 1.0. And I got AC after fixing it... So sad!! :(
For div2 B, can someone confirm test 13 is the same with test 14, i.e. the input is ten thousand 0s? My solution passed 13 but failed on 14, quite weird.
your solution didn't pass test 13. you got wrong answer on test 13.
The solution I meant is below, not the one during the contest.
test 13 and 14 are not identical. I suppose there is a difference between them and since we can't see the whole test case we can't see the difference.
The wrong solution is here. Please give me some hints.
Input can be like this
(100000) zero for test 13
(99999) zero + 1 for test 14
both of them have same answer but, because is too long, it will cut.
input 5 0 0 0 0 5 what answer?
0
Thanks you guys who replied. I find the bug and get it fixed. This is the correct solution. It turns out case 13 and 14 are indeed different.
very nice problem set!
The problemsets are nice, thank you, Sereja.
Problem B was very confusing.. as in the problem statement, it was written: Each digit is allowed to occur in the number the same number of times it occurs in the set.
Then how the ans for second test case is: 5554443330 since in input set 4 is occurring 4 times but in output integer it is occurring 3 times only.
It is permitted to use not all digits from the set
They said: " It is permitted to use not all digits from the set"
I took it as.. if i am not taking any digit then i am not supposed to use that digit in the output at all. Means that digit's count would be made 0. I tried other way also, but because of a very silly mistake my solution got hacked.
May be you missed this -> '**It is permitted to use not all digits from the set**'
I Think It Would be better to increase Contest Time for some contests like this To let People have more Fun !
The comment is hidden because of too negative feedback, click here to view it
It's interesting to see how many downvotes that comment will get, because it'll mean that some people actually care about comments that downvoted a lot.
One of the advantages of being Petr is that you can make such troll-jokes without throwing your reputation towards S = {x : x < 0} where x belongs to R.
When I try to click "here" the page scrolls to the top and the comment doesn't show up.
I don't get how you don't get it. And I'm the "blue" one here.
Does the intended solution for div1 E use hashes? I saw only hash solutions and wonder if they can be hacked using ideas from recent anti-hash articles.
I think that this is the reason why people submited this problem in last minutes of the competition — not to be hacked...
I'm quite sure it can be solved with something similar to KMP.
Assume we can, after preprocessing, quickly compute functions prev(k, i) and next(k, i) for a permutation P, which give the first element j in [i, k — 1] preceding / succeeding k in P.
Let suf[k] be the minimum j > 1 such that the part of A composed of elements [j, k] is (EDIT) the same permutation as the part of A composed of elements [1, k — j + 1]. We can compute suf[] using a linear number of calls to prev() and next() on A.
Later we can use suf[] like a KMP table to compute all shifts that match with a linear number of calls to prev() and next() on A and B. :)
How can I know number of 1's in testcase number 12 in div2 problem B ?
There is no way to do this.
But... You can count them, and guess counter by binary search. (For example, if cnt < 4000 then cause TLE, otherwise get WA)
I found a better way compared to this. print out number of 1's for this particular case . number of 1's are 49898 . :D
anyway thanks for your help.
One Does Not Simply
Update the rating quickly
i am new on codeforces.com and how add friend???
hacked by hackers
lashabuxo tell me why you made multiple accounts? http://codeforces.net/blog/entry/4924#comment-100414
i believe it's a way to get upvotes on his comments
Is there any rational reason to do this? :P
don't ask me :)
open someone's page and click the star on the right of the name
tourist lost his Codeforces Red Target :(
When will the editorials be available for this contest's problemset? Thanks in advance
As soon as it gets posted.
Wrong answer on test 65 on problem B, div 2. Don't you know what it is?
div 2,problem B: your submissions status and test 65:
when the Problem's Analysis will be placed ?
Although I liked the problems, I think problem C was a bit of a fiasco. On one hand the exact same problem has been given before in TopCoder, SPOJ, one Bulgarian competition (okay, no way to know that) and God knows where else. Thus many people had the chance to solve it in several minutes (I for one needed 9 minutes, and other people even less). Anyway, this happens (I know from bitter experience).
I also was happy to see the negative numbers (which means negative results are possible). This is another TopCoder trick I've felt for before — if you use memoization and you initialize your array with -1 (which is valid number in this case) you have a correct, but possibly too slow solution. For those of you who don't know it — if the answer to the problem is -1, then some of the states will be calculated over and over again and it can turn really slow. So I was looking for such solutions in my room, however most were using standard iterative dp (which is okay with that) and didn't have the chance to challenge anyone.
However, such a test was not present in the system tests, so some (possibly plenty) of wrong solutions passed.
The test is rather simple to create:
But, is there a way to use a smaller state (not 598x300x300) so that you don't get memory limit exceeded? Because if that can't be done then I guess that could justify the absence of such cases
Yes, sure. See my solution, it uses twice smaller state (if I initialize my dyn[][][] array with -INF instead of using additional array).
When I click the tutorial link, I can see a tutorial, but not in English. Why? The English tutorial has been released, I think.
You may change '.ru' to '.com' in link. http://codeforces.net/blog/entry/4982
Hello! I don't know where to post my problem so i'll post it here. I apologize if posting this here is wrong.
Well i have tried the problem Numbers(D div2, B div1) and i finally solved it. The source code is here http://codeforces.net/contest/214/submission/1974583
I get WA on test 10 (100 0 0 0 0 0 0 0 0 0 0). The strange thing is that when i run the code it prints the right answer on my computer. Here when i submit it, the answer on the same test is different and i don't get it why it does that.
Please help me to see what is wrong :(
In your code,
len
can be 0, so inComb[len - 1][j]
index goes -1 and so you get weird numbers from uninitialized memory, instead of expected 0 value.Thank you very much :) I finally got AC. I guess i missed that -1 index.