Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Gerald's blog

By Gerald, 7 years ago, translation, ,

Good Day!

The next Codeforces round will start soon. It will be held by usual Codeforces round rules.

The author of today's round is Mykhailo Granik (Fcdkbear), he is listening the lecture at the Winter Kharkiv Programming School now. Great thank him for this contest!

The score distribution will be standart: 500-1000-1500-2000-2500.

Good luck to all!

• +121

 » 7 years ago, # |   0 Good Luck Every One!:D
 » 7 years ago, # |   -11 waaah, I hope, I could get better rank than last contest.. :D
•  » » 7 years ago, # ^ |   0 we all hope same thing will happen (to us), good luck ;-)
 » 7 years ago, # |   +19 Too bad, there's only Div. 2.
 » 7 years ago, # |   +8 I didn't find any other contest with his name as a problem setter.I hope to see some great problems and a brilliant contest. HF & GL.
 » 7 years ago, # |   +28 I hope I can get the good grades :) I am in China, so the local time in there is 11:30 pm. T_T but I still like attending the Competition like this to improve my Programming skills and English !
•  » » 7 years ago, # ^ |   +23 I know that feel, bro. I'm in Indonesia and its local time is 22:30.
•  » » » 7 years ago, # ^ |   +1 I'm vietnamese, the same time with you Ariza :D. So tired but may be I will learn some thing good :D
•  » » 7 years ago, # ^ |   +12 It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-
•  » » » 7 years ago, # ^ |   +6 I think it's better for you to hope to not sleeping at work. Trust me..
 » 7 years ago, # |   -9 Hello, can you please explain why on task C the answer to the first test is 25 and not 26?
•  » » 7 years ago, # ^ |   +11 becose you can reorder array (5,3,2) and get (2,5,3) ans=3*5+2*2+2*3; this is most most optimal way to get max ans
 » 7 years ago, # | ← Rev. 4 →   -15 I can't hack problem C due to file size restrictions, currently 256kb... This code:int main(){int i = 1;int n = 2 * 1e5;int q = 2 * 1e5;cout << n << " " << q << endl;for(int p = 1; p <= n; p++){ cout << i; if(p == n) cout << endl; else cout << " "; }for(int p = 1; p <= q; p++) cout << i << " " << n << endl;}generate a huge input (about 3.3 MB), it's a special input with maximum numbers for the queries and values N and Q, 2*10^5.Currently, there is no way for send this input, or the code generator... :( ... then, I can't hack solutions, that surely get TLE on the finals tests.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +6 this issue has been discussed many times.you should use generator.
•  » » » 7 years ago, # ^ |   +6 Not available, at least for this contest.
•  » » 7 years ago, # ^ |   +4 #include #include using namespace std; int main() { printf("200000 200000\n"); for (int i = 0; i < 199999; i++) { printf("200000 "); } printf("200000\n"); for (int i = 0; i < 200000; i++) { printf("1 447\n"); } return 0; } I sent this test to hack one solution of task C and got the incorrect test verdict with the message: FAIL Expected integer, but "#include" found (stdin) [validator validator.exe returns exit code 3]. Can someone say what's wrong?
•  » » » 7 years ago, # ^ |   +27 You submited it as test, not test generator. So it was got to validator as is. #include, which is first token is not an integer. Message informs you about it.
•  » » » 7 years ago, # ^ |   +5 There are tabs for that purpose ;)
 » 7 years ago, # |   +5 Nice problems, Unfortunately I misread problem B so that I didn't solve it until last 15mins.anyway I enjoyed the contest :)
•  » » 7 years ago, # ^ |   +5 yeah, same here. but still a good contest with clear problems.
 » 7 years ago, # |   +7 I submitted problem C a lot of times, but every time judge gave Wrong answer on test case number one. As test number one is same as given in the sample input , I checked on my computer. It was working fine.I could not even run my code on custom test because Custom test did not work properly and issued an error : Form elements must not have name or id of "submit".Could anybody tell me what the problem could be ??
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 did you make sure that you give your variables and arrays initial value 0 ?
•  » » » 7 years ago, # ^ |   0 All the arrays were globally declared. I am only using the indices of the array on which I am overwriting data.Do I explicitly need to make all the global variables zero ??. I think they are zero by default.
•  » » » » 7 years ago, # ^ | ← Rev. 4 →   0 I don't know why this is happening to you,but sometimes I face the same problem so I give zero value to arrays and it will be solved
•  » » » » » 7 years ago, # ^ |   0 I am not able to use custom test due to error "Error: Form elements must not have name or id of "submit".". It gave output 21 on the test case no one as shown in the final tests. I really do know why it showed output 21 ??
•  » » 7 years ago, # ^ |   +3 In your compare function, what happens if a.value != b.value and a.type != b.type?
•  » » » 7 years ago, # ^ |   +4 Oh yes, this is where the actual problem lies. It was somehow working fine on my computer. Thank you very much :)
•  » » 7 years ago, # ^ |   0 I suggest you to test your code on custom test to see how it works on CF Compiler. I faced the same issue earlier and they told me to do it when I asked in clarification.
 » 7 years ago, # |   0 I think these problems are very good without problem statement of B. I'm not good at English, so I used translate system. But I couldn't understand problem B at all. I wish there had been an explanation for samples...
 » 7 years ago, # | ← Rev. 2 →   0 I DP problem C but it seems like there is a trick for this problem :(
•  » » 7 years ago, # ^ |   +1 this is not DP.you should see the indexes that has most frequent and assign the biggest numbers to this indexes.it's Greedy.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I have Solved it by using DP, you should see my code! :)
•  » » » » 7 years ago, # ^ |   0 maybe there is DP solution, but I see that greedy is easier.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 You have one solution,how i saw(nhandi,kingofnumbers) and you are talking about different solutions
•  » » » » » » 7 years ago, # ^ |   0 I am not able to read his solution because of strange language but my solution is not DP!
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 non dp : for(int i=0;i<=n;i++){ w+=ct[i]; ct2[i]=w; }his dp : c[0] := 0; for i := 1 to n do c[i] := c[i — 1] + d[i];he just store what he found before in c[i]; while on the other hand (on non dp), we just need one variable w to store the previous value
•  » » » » 7 years ago, # ^ |   +3 It is the same solution for both of you, and it's greedy :)
•  » » » » » 7 years ago, # ^ |   0 Yes, it's not DP.
 » 7 years ago, # |   +12 It is the first time that I solve all the problems in a Codeforces Round! THX!
•  » » 7 years ago, # ^ |   +9 you should try div2 contest more often :D
 » 7 years ago, # |   +7 Here's an unofficial editorial: http://www.codeforces.com/blog/entry/6778Great round!
 » 7 years ago, # |   +45 OMG someone fake me
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 there is a different one letter :)
•  » » 7 years ago, # ^ |   +10 It's different in all letters, If you use a strict checker. :D
•  » » 7 years ago, # ^ |   +16 I think, they have to ban him
•  » » » 7 years ago, # ^ |   +7 What about your ID? XD
•  » » » » 7 years ago, # ^ |   +14 Someone took egor, I take that login name everywhere, but I couldn't do it here. So I liked someone has that number, so I took it too.
•  » » » » » 7 years ago, # ^ |   +8 me too me too~~~~~
•  » » » » » » 7 years ago, # ^ | ← Rev. 3 →   +8 You are fake!UPD: Oh, may be you aren't. tourist50216
•  » » » » » » » 7 years ago, # ^ |   +3 I can't believe that it's coincidence that new three users have similar names in one contest.this is not coincidence, this is happening on purposes.furthermore both have the same number 50216 !!
•  » » 7 years ago, # ^ |   +3 I always wanted to ask, does your nickname means anything or it's just random letters?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 What about this one(WJMZ8MR)?
•  » » » 7 years ago, # ^ |   +3 He is my schoolmate.
•  » » » 7 years ago, # ^ |   +6 Absolutely I'm not the real one :( (I hope I was.)
 » 7 years ago, # |   0 Can someone explain why my solution http://codeforces.com/contest/276/submission/3189675 gives output '141517992919' on Codeforces compiler and '9382' on my compiler (which is the expected answer)? I am using i686-apple-darwin11-llvm-g++-4.2 compiler.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 On this test your program produces /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/debug/vector:336: error: attempt to subscript container with out-of-bounds index 65, but container only holds 65 elements. Objects involved in the operation: sequence "this" @ 0x0x8058170 { type = NSt7__debug6vectorIiSaIiEEE; }
•  » » » 7 years ago, # ^ |   0 Where did you see this error?
•  » » » » 7 years ago, # ^ |   +14 I use the _GLIBCXX_DEBUG macro locally, it adds range checks and stuff to the standard containers.
•  » » 7 years ago, # ^ |   0 On my computer it also gives output 9832. I do not why this is happening. Same is happening with me in problem C with test case number 1. :(
•  » » 7 years ago, # ^ |   0 I have same problem with problem — C . My solution 3189369 failed on Test-3 ( According to Codeforces ) , But its giving expected 9382 on my pc( Ubuntu-12.04 ).When i tested here , its giving different result . Can anybody help me to point out errors in my code ..?
 » 7 years ago, # |   +3 Thanks for the contest, very nice problems, everything clear in the statement. I enjoyed this contest ;-)
 » 7 years ago, # |   0
 » 7 years ago, # |   0 My submission 3189731 failed for test 20. What's wrong with my code? On my pc it gives the correct answer.
 » 7 years ago, # |   0 the problems is very good for me
•  » » 7 years ago, # ^ |   -7 when will rating updated??
•  » » » 7 years ago, # ^ |   0 it is now
 » 7 years ago, # |   -21 Funny, the same algorithm gave me TLE in java but not in c++. java -> http://ideone.com/wkFEuE c++ -> http://ideone.com/fsUknS Good Codeforces, nice way of discouraging non-c++ coders on your platform
•  » » 7 years ago, # ^ |   +28 You have to know, that Arrays.sort in Java works in Theta(n^2) time for some arrays of n elements. Learn Java.
•  » » 7 years ago, # ^ |   +3 sort() in java might degenerate to O(n^2), if it applies on an array of primitive type
•  » » » 7 years ago, # ^ |   +1 So, should I use Integer wrapper? it does not pass either.
•  » » » » 7 years ago, # ^ |   +8 I recommend you to shuffle array before sorting.
•  » » » » » 7 years ago, # ^ |   0 Is there any method to confirm if shuffle will always lead to a better performance? Also what exactly could be the cases when the Arrays.sort() leads to O(n^2). I am asking as the description given on official Oracle page is quite blurry.This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
•  » » » » » » 7 years ago, # ^ |   +3 What is the probability that from a given worst case — order of elements, doing shuffle you will obtain the same order? The probability to win lotto is bigger than that :)
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 Theoretically you can still hit the worst case after shuffle, but the probability of this event is negligible. You can see the anti-Java-sort testcase generator here.
•  » » » » » » » 7 years ago, # ^ |   0 Actually, my generator is not working properly: recursion's depth is not maximal. There's a bug somewhere but I couldn't find it :(Nevertheless, it works about 2.5 sec. on Codeforces servers.
•  » » » » » » » » 7 years ago, # ^ |   0 :-(I still consider it a very valuable effort.
 » 7 years ago, # |   0 For problem B, what is the answer for "aabb" ? Below is what i feel, please correct me The first player can for palindrome "abba". He takes off 'a' Second player can form palindrome "bab". He takes off 'b' First player cannot for a palindrome and hence Second player wins. But correct official answer says "First". What am i missing ? Can some body explain how First player can win ?
•  » » 7 years ago, # ^ |   +4 The first can already reorder the string to a palindrome."If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins."
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 The first player can for palindrome "abba". He is a winner! Second — losе
•  » » 7 years ago, # ^ |   0 player wins if he CAN form a palindrome before deleting operation
 » 7 years ago, # |   -8 for problem D... can anyone tell the answer of input is 15 and 17..?
•  » » 7 years ago, # ^ |   +3 It's 31
 » 7 years ago, # |   -8 Why did this submission generate WA? 3186879
•  » » 7 years ago, # ^ |   0 You have a mistake.
•  » » » 7 years ago, # ^ |   0 Which one? because this one generate an AC 3187782
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Bad-bad bitsets? Visual C++ can't even compile this code.UPD "no operator found which takes a right-hand operand of type '__int64'"So, the problem is between long long and bitsets...
 » 7 years ago, # |   0 The author's Editorial in Russian : Codeforces Round #169
•  » » 7 years ago, # ^ |   0 Is there any English Editorial from the authors ??
 » 7 years ago, # |   +5 Screencast of me solving this round.
 » 7 years ago, # | ← Rev. 3 →   +14 Hi, I would really appreciate some help debugging my code to problem E. I guess my idea is basically something similar to other people solutions, here is a poor described sketch of it (I apologize for that): ... (if you want to read it it is on the previous versions of this post ;) )Edit 1:Got Accepted! After debugging for 5h I made some small modifications and it passed the tests.. I am too tired now to check what the error was, I need some sleep :p, I will check it tomorrow and update this post!Here is the accepted submission: ACCEdit 2:Found it! It was a very silly mistake (embarrassing), on naming who is the tail of the current branch. Thank you all and sorry for bothering :)
 » 7 years ago, # |   -18
•  » » 7 years ago, # ^ |   +8 English editorial was published 2 days ago. Please check my blog before making such funny jokes.
•  » » » 7 years ago, # ^ |   -8 Well then I am sorry, but you should put a link on official contest page as well.Anyway it was with funny intentions :)
 » 7 years ago, # |   0 Editorial (in English) available here
 » 4 weeks ago, # | ← Rev. 2 →   0 A is a nice problem!