MikeMirzayanov's blog

By MikeMirzayanov, 10 years ago, translation,

Hello!

Only few hours left before Codeforces Round # 135 (Div. 2). We are preparing the round in Petrozavodsk where traditional training camp for ACM-ICPC is going now. Today is a day of rest here, many participants gone to a trip to Kizhi. The main contest authors are me and Gerald. Special thanks to Aksenov239 who tested the round. Thank Delinur for translation.

The problems will be sorted by expected difficulty, the scores are dynamic.

Wish you fun round!

• +100

 » 10 years ago, # |   -8 I got report on my email about this round and there was writen that contest was held by rules of codeforces not dynamic scoring.
 » 10 years ago, # | ← Rev. 2 →   0 Good luck everybody! May the best will win! Let's hope for an interesting problem set and a lot of hacks!
•  » » 10 years ago, # ^ |   +2 Dfs from any vertex, then ansver for vertex is number of edges goes up in path from root to it + all other edges, that goes down
•  » » 10 years ago, # ^ |   +3 1) At start find the result for the first node using bfs. 2) Again, using bfs for all neighbor nodes result differs always in 1 (+ or — depending on direction of the edge) -> count result 3) After you counted result for all nodes I believe it's obvious
 » 10 years ago, # |   0 How to solve E?
•  » » 10 years ago, # ^ |   +3 Use a heap to maintain all the gap each time we pop the longest gap
•  » » » 10 years ago, # ^ |   0 You are so clever ... I use segment tree to update the longest gap ...
•  » » » » 10 years ago, # ^ |   0 STL is a better choice for C++.The maintain of segment tree is very complex.
•  » » » » » 10 years ago, # ^ |   0 +1
 » 10 years ago, # |   +1 Hi all , I have solved 4 problems (A,B,C,D), but i have spent about an hour for task B ,so couldn't get enough points: It will be fine ,that for counting points we use the time participant has spent ( counting from his/her first opening that task) , and not to use the time counted from begining the contest : Sorry for bad English :D
•  » » 10 years ago, # ^ |   -6 It's not good for system because now you can read the task and not solve it, and return to this task later.
 » 10 years ago, # |   0 I think systest is so slow today. Maybe it causes from to many testcase on problem B
 » 10 years ago, # |   0 I think the problem E should solve via Interval Tree. For each node in the tree, we store min parked space, max parked space, max interval length without parking and that maximum interval.
 » 10 years ago, # |   +6 Slow system :(
•  » » 10 years ago, # ^ |   0 Indeed..
•  » » 10 years ago, # ^ |   0 Now we must wait for rating. .
 » 10 years ago, # |   0 I used abs() function in my C++ code in problem B where it should get the absolute value between to long longs, but actually this caused a Wrong Answer in the final tests. When I removed the abs() and made it manually, it got accepted in the practice! How come something like this happen?BTW, labs() don’t work too.
•  » » 10 years ago, # ^ |   0 according to this site: http://www.cplusplus.com/reference/clibrary/cstdlib/labs/ labs takes a long int as a parameter, while you use long long ints. So does abslong ints are 32 bits long, while long long ints are 64 bits
•  » » » 10 years ago, # ^ |   +4 long ints are 32 bits long, while long long ints are 64 bits That is correct only for a certain set of compilers (including both compilers supported by codeforces), but in general this statement is not always true. 64-bit g++, for instance, has 64 bit long longs.
•  » » 10 years ago, # ^ |   +4 When you submit C++, write in C++: 2060835
•  » » » 10 years ago, # ^ |   +4 Oh I see, thanks a lot! :)
 » 10 years ago, # |   0 Here is my submission to problem B: 2054290. It gives correct output on my system as well as ideone (8JSXv). But it fails on codeforces judge (for test case 11). Is there some problem with my code ? Comments are welcomed!!
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 The problem is in using of pow() with integers. Try the following code in custom test: long long int a=10, t=1; while(t<3) { long long int test=(long long int) (pow((long long int)10,t)); cout<
 » 10 years ago, # |   0 in problem B, it says-- Print the required price — the maximum price that ends with the largest number of nines and that is less than p by no more than d. what does that mean??output should >= (p-d) and <= por >= (p-d) and
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 >= (p-d) and <= p
 » 10 years ago, # |   0 i am getting TLE for Problem C.here is my try: http://codeforces.com/contest/219/submission/2067867i am trying to solve it with DP..any suggestions to optimize it ???
•  » » 10 years ago, # ^ |   +3 Don't use recursion for dp. Do it iteratively. Avoid using pure cin/cout for large input data (use either c-style input (fastest way) or disable syncing with stdio)
•  » » 10 years ago, # ^ |   0 The problem is your DP complexity. It is 100000 * 26 * 26 ~= 10^8 in the worst case. One good point to think is "Do you really need a DP for all testcases?"
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 #pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") `Add this to the start of your code. Here is my submission which ran on 1934ms : 78488193