MikeMirzayanov's blog

Codeforces Round #135 (Div. 2)
By MikeMirzayanov, 12 years ago, translation, In English

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!

  • Vote: I like it
  • +100
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I got report on my email about this round and there was writen that contest was held by rules of codeforces not dynamic scoring.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Good luck everybody! May the best will win! Let's hope for an interesting problem set and a lot of hacks!

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hints for problem D needed :D please help :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Use a heap to maintain all the gap each time we pop the longest gap

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are so clever ... I use segment tree to update the longest gap ...

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        STL is a better choice for C++.The maintain of segment tree is very complex.

        → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    It's not good for system because now you can read the task and not solve it, and return to this task later.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think systest is so slow today. Maybe it causes from to many testcase on problem B

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Slow system :(

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 abs

    long ints are 32 bits long, while long long ints are 64 bits

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    When you submit C++, write in C++: 2060835

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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<<test<<endl ;
    t++;
}
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <= p

or >= (p-d) and <p

confusing!!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i am getting TLE for Problem C.

here is my try: http://codeforces.com/contest/219/submission/2067867

i am trying to solve it with DP..

any suggestions to optimize it ???

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • 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)
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?"

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    #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

    → Reply