PavelKunyavskiy's blog

Codeforces Beta Round #73
By PavelKunyavskiy, 13 years ago, translation, In English
Hello everybody and welcome to the first summer round - Codeforces Beta Round #73.

Today we are the authors of round: kuniavski (Pavel Kunyavskiy) and Zlobober (Max Akhmedov). Competition will take place in both divisions. Totally there will be 7 different problems with variations in divisions, 5 in each division. We hope everybody shows their best and solve as many problem as they can.

Thanks to RAD (Artem Rakhov) for the help and advices in preparing of the round,  Delinur (Maria Belova) for the problem translation and  MikeMirzayanov (Michael Mirzayanov) for such a great site.

GL & HF!


Tutorials: div1,div2

Congratulations to the winners

Div1 - ilyakor 
Div2 - peter50216

Some statistics. First sucsessful submits and hacks:

Div1-A Dmitry_Egorov 4:09
Div1-B ilyakor 13:05
Div1-C A_A_Lunyov 8:05
Div1-D hos.lyric 30:57
Div1-E rng_58 75:20
hack VArtem 26:15

Div2-A epizend 5:27
Div2-B random.johnnyh 19:15:29
Div2-C RomaFurko 11:31
Div2-D peter50216  41:18
Div2-E peter50216 54:00
hack  diogen 55:33
  • Vote: I like it
  • +198
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
wow 7 problems.. nice..!! :D
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Is DIV 1 .harder than combined  division previously.?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    May be.
    I think, it was at bit disbalanced: first two problems was simple, C was classical, D and E required a lots of code.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can anyone explain how Div1-C is solved ?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Its a direct Grundy problem, no special tricks or patterns or observations needed. I'm (almost) sure you know grundy :).

        Fill the grundy table g[0...N] and each g[X] means you have a game of X piles. Try all possible moves, i.e., all possible K such that X = a * K + (K*(K-1))/2 , which results in subgames {a,a+1,a+2,....,a+K-1}. The grundy of the collection of these subgames is ( g[a] ^ g[a+1] ^ ... ^ g[a+K-1] ). Some coders just iterated and found this value, but you can simply maintain a prefix xor on g[ ] , say pg[ ] and get it using pg[a+K-1] ^ pg[a-1] in O(1). g[X] = the mex among all grundy values reachable from X. Complexity is O( n . sqrt(n) )
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks for the reply. I'm familiar with grundy numbers, but I don't believe this problem is a direct one. Typically a transition in a game leads to another state of the same game, so we start by assigning grundy numbers to states (no xor operation is involved here) and then xor the grundy numbers once for the collection of initial games (an example is the knights problem here http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames). 
          While in this problem as each transition creates many states then we need to xor their grundy numbers to get the "combined" grundy number of this transition.
          → Reply
13 years ago, # |
← Rev. 7   Vote: I like it +12 Vote: I do not like it

I like to compete in Codeforces.
This round may be easier than past round (Div2). Normally, I solve only one problem during contest, but today i solve  3 problems
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve Problem D(Div 1)?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    There soon will be english version of analysis.
    Main idea is that we sort edges and add by groups in the graph, counting for each new edge all the paths that include it using DSU.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What is dsu? I've seen that tag on a problem before but have never heard of it. (I've even solved a problem with that tag before and have never heard of it xD although I think I managed to find another way around) 
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
   <code> 
    long long lcm ;
    int a,b;
    cin >> a >> b;
    lcm = (a/gcd(a,b))*b;
</code>
why does this overflows ?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Because at the time of computation (a/gcd(a,b))*b, the resulting type is still int.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    a=1000000
    b=999999
    gcd(a,b)=1;
    a*gcd(a,b)=1000000;
    a*b>2^31-1
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In pretest 3 for problem C, there is a voidddd which hasn't been declared, how should these cases be handled?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Unknown types is errtype
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it
      was it mentioned in the statement?
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        Yes, of course

         "An attempt to use the data type that hasn't been defined before that will also lead to the errtype."
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes: "An attempt to use the data type that hasn't been defined before that will also lead to the errtype."
        → Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Great set :) 
So stupid mistakes in my code but I loved the problems.. Thank you
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
One General Question :: Is it good practice to use long long all the way , because that way I will sure that there will be no overflows. But is it good/alright practice ?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Long long's are slower at about 3 times. So use it only when it's neccesary.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    long long's are much slower. You can get AC doing 5*10^8 operations with ints, but the same with long longs can get TLE. So you can do it if only you are sure, that your solution works fast enough to fit time limit.
    → Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
great round, unfortunately It wasn't possible to be in the contest for me, because of the time(it is school time).
By the way, the link to the tutorials is wrong.
greetings
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Quick suggestion for blog posts: when posts are translated from Russian to English, http://codeforces.net/ profile links should be converted to http://codeforces.net/ links.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    ... or (better) / links. They works with any pair domain name+ language
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Another comment: Sometimes when you try to hack a solution, you cannot see the entire line because it is cut off on the right. Maybe you should implement wrapping text around.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In Div-2 (Prob - C) ,
When I used scanf("%lld%lld",&a,&b); --- it gave me wrong answer.
But when I used cin>>a>>b; --- the solution was accepted!!

What was the problem? Anyone please reply.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Actually, it is often written as a note to problem description - "Please, do not use %lld ..."
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      But they had not written this as a note this time around!
      That wasted my 25 minutes :sob:
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Codeforces rejects solutions that don't match regular expression (for example, if C++ solution doesn't have "main", you can't submit the solution). Is it possible to reject solutions that contain "%lld"?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it
          it is bad idea because somebody can use
          #ifdef ONLINE_JUDGE
          #define A "%I64d"
          #else
          #define A "%lld"
          #endif

          to test solution on his own local machine without changes
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it
            Codeforces could replace all occurrences of "%lld" to "%I64d" :)
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Yes, this idea went to my mind too)
              → Reply
            • 13 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it
              It's also possible for Codeforces to give warning before submitting of C++ codes which contain "%lld".
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it
                It would be inconvenient to make one more click for each submission if one uses the defines above.
                → Reply
                • 13 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it
                  He can enable or disable pre-submission warnings in settings section :P
                  → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Hey. I can't see the tutorials via that hyperlinks. I guess there need some modification from http://www.codeforces.com/blog/entry/codeforces.com/blog/entry/2121?locale=en to http://codeforces.net/blog/entry/2121?locale=en . Isn't it? :P
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is it possible to start allowing hacks even in practice, like topcoder?

Concerning problem D,
I wonder if if final tests contained this type of a test:
We have a large tree with this structure -
4
1 2 1
2 3 2
3 4 3
It is a straight line tree with the largest weight edge at the bottom.
I m guessing final tests, skipped such a case. I could notice solutions without the use of DSU pass the system tests but fail this one.

Appreciate a reply.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I hope that in addition to this, we can actually see/download the test cases, instead of just seeing a number of '...'s at the end of large cases. Since sometimes I find my program can produce different results on my computer and on the site, I think this could be even more useful. Or maybe there is a way to do it unknown to me now?
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hey can anyone let me know how to register for beta round #74 div 2 as m a newbie???
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    you'll be able to do it later. wait for a half of day :)
    → Reply