### PavelKunyavskiy's blog

By PavelKunyavskiy, 13 years ago, translation,
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 -
Div2 - peter50216

Some statistics. First sucsessful submits and hacks:

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

Div2-A epizend 5:27
Div2-B random.johnnyh 19:15:29
Div2-C 11:31
Div2-D  41:18
Div2-E 54:00
hack  55:33
• +198

 13 years ago, # |   +9 wow 7 problems.. nice..!! :D
•  13 years ago, # ^ | ← Rev. 2 →   +22 That means, that there will be totally 7 problems in both divisions.Each division has, as usual, 5 problems.
•  13 years ago, # ^ | ← Rev. 3 →   +9 It means that 3 problems will be common for each division.
•  13 years ago, # ^ |   0 Yes.
 13 years ago, # | ← Rev. 2 →   +1 Is DIV 1 .harder than combined  division previously.?
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 Can anyone explain how Div1-C is solved ?
•  13 years ago, # ^ |   0 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) )
•  13 years ago, # ^ |   0 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.
 13 years ago, # | ← Rev. 7 →   +12 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
 13 years ago, # |   0 How to solve Problem D(Div 1)?
•  13 years ago, # ^ |   +3 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.
•  13 years ago, # ^ |   0 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)
•  13 years ago, # ^ |   0 He means disjoint-set data structure. Try to guess how an abbreviation DSU is formed :)
•  13 years ago, # ^ |   0 Disjoint Set Union?
 13 years ago, # |   0         long long lcm ;    int a,b;    cin >> a >> b;    lcm = (a/gcd(a,b))*b;why does this overflows ?
•  13 years ago, # ^ |   +4 Because at the time of computation (a/gcd(a,b))*b, the resulting type is still int.
•  13 years ago, # ^ |   0 Silly me. :(
•  13 years ago, # ^ |   0 a=1000000 b=999999gcd(a,b)=1;a*gcd(a,b)=1000000;a*b>2^31-1
 13 years ago, # |   0 In pretest 3 for problem C, there is a voidddd which hasn't been declared, how should these cases be handled?
•  13 years ago, # ^ |   +1 Unknown types is errtype
•  13 years ago, # ^ |   -7 was it mentioned in the statement?
•  13 years ago, # ^ | ← Rev. 2 →   +4 Yes, of course "An attempt to use the data type that hasn't been defined before that will also lead to the errtype."
•  13 years ago, # ^ |   0 Somehow managed to skip it. Thanks.
•  13 years ago, # ^ |   0 Yes: "An attempt to use the data type that hasn't been defined before that will also lead to the errtype."
 13 years ago, # |   +3 Great set :) So stupid mistakes in my code but I loved the problems.. Thank you
 13 years ago, # |   0 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 ?
•  13 years ago, # ^ |   +1 Long long's are slower at about 3 times. So use it only when it's neccesary.
•  13 years ago, # ^ |   +1 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.
 13 years ago, # |   +3 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
 13 years ago, # |   +5 Quick suggestion for blog posts: when posts are translated from Russian to English, http://codeforces.com/ profile links should be converted to http://codeforces.com/ links.
•  13 years ago, # ^ |   0 ... or (better) / links. They works with any pair domain name+ language
 13 years ago, # |   +1 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.
 13 years ago, # |   0 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.
•  13 years ago, # ^ |   +2 Actually, it is often written as a note to problem description - "Please, do not use %lld ..."
•  13 years ago, # ^ |   0 But they had not written this as a note this time around!That wasted my 25 minutes :sob:
•  13 years ago, # ^ |   +5 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"?
•  13 years ago, # ^ |   +13 it is bad idea because somebody can use#ifdef ONLINE_JUDGE#define A "%I64d"#else#define A "%lld"#endifto test solution on his own local machine without changes
•  13 years ago, # ^ |   +4 Codeforces could replace all occurrences of "%lld" to "%I64d" :)
•  13 years ago, # ^ |   0 Yes, this idea went to my mind too)
•  13 years ago, # ^ |   -8 It's also possible for Codeforces to give warning before submitting of C++ codes which contain "%lld".
•  13 years ago, # ^ |   +1 It would be inconvenient to make one more click for each submission if one uses the defines above.
•  13 years ago, # ^ |   +1 He can enable or disable pre-submission warnings in settings section :P
 13 years ago, # |   +2 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.com/blog/entry/2121?locale=en . Isn't it? :P
•  13 years ago, # ^ |   0 Fixed.
 13 years ago, # |   0 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 -41 2 12 3 23 4 3It 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.
•  13 years ago, # ^ |   +1 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?
 13 years ago, # |   0 Hey can anyone let me know how to register for beta round #74 div 2 as m a newbie???
•  13 years ago, # ^ |   0 you'll be able to do it later. wait for a half of day :)