### Morphy's blog

By Morphy, history, 6 years ago,

Codeforces Round #328 (Div. 2) will take place on October 31, 19:30 MSK, as usual Div. 1 participants can join out of competition.

Problem Setter: Morphy (Alei Reyes)

Coordinator: GlebsHP (Gleb Evstropov)

English to Russian translator: Delinur (Maria Belova)

Codeforces and Polygon: MikeMirzayanov (Mike Mirzayanov)

Hope you enjoy the problem set.

The score distribution will be announced later.

UPD. Score Distribution: 500 — 1000 — 1500 — 2000 — 3000

UPD. Problem Analysis is available

Congrats to the winners!

Div. 2

Div. 1

• +523

 » 6 years ago, # | ← Rev. 2 →   +59 "Codeforces and Polygon: MikeMirzayanov" wrong. MikeMirzayanov is a human he can not be codeforces and polygon. he is codeforces and polygon manager and creator.
•  » » 6 years ago, # ^ |   +33 Well , we aren't in English class :D
•  » » » 6 years ago, # ^ |   -7 it is not about english . in any language it is wrong.
•  » » » 6 years ago, # ^ |   +3 We are in logic class :)
 » 6 years ago, # |   +340 MikeMirzayanov is human.. Thank you, I always thought he was like this
•  » » 6 years ago, # ^ |   -56 А теперь всех кто поставил + ждет бан =)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -28 .
•  » » 6 years ago, # ^ | ← Rev. 2 →   -27 You were wrong because this Also cannot be "Codeforces and Polygon".
 » 6 years ago, # | ← Rev. 3 →   +80 Short announcement :D great!Let's hope for short problem statements too.
•  » » 6 years ago, # ^ |   +13 but it was long problems :|
 » 6 years ago, # |   -36 GlebsHP is our new co-coordinator, right? Congrats GlebsHP :)
 » 6 years ago, # |   +34 hope there is no Physics and Chemistry problems this time :))
•  » » 6 years ago, # ^ |   +13 What about biology?
•  » » » 6 years ago, # ^ |   +7 :P
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -7 maybe other subjects such as sociology and ... :|
•  » » » » 6 years ago, # ^ |   +3 How about history? I have history exam tomorrow.
•  » » » » » 6 years ago, # ^ |   -8 and literature and geography :|
•  » » » » » » 6 years ago, # ^ |   +11 implying humanities sciences are actually sciences
•  » » » » » » » 6 years ago, # ^ |   0 >look I know how to greentext>implying geography is a "humanities science"But I agree otherwise.
•  » » » 6 years ago, # ^ |   +10 I don't find anything wrong with this "Biology" problem: 579A - Выращиваем бактерии
•  » » » » 6 years ago, # ^ |   0 So irrelavant to programming!! even that problem doesn't need to know about biology, but in the last contest, we have problems which solved using physics!!
 » 6 years ago, # |   -17 In some countries October 31st is Halloweens Day. Hope to see some Ghouly questions?
 » 6 years ago, # |   -13 waiting and hope nice rate this time :)
 » 6 years ago, # |   0 short and good blog :) thanks
 » 6 years ago, # |   +10
 » 6 years ago, # |   0 is this your first time ?
•  » » 6 years ago, # ^ |   +23 Yes If he's any previous one , simply you will find a "Problemsetting" section in his profile :)
 » 6 years ago, # |   +42 It looks like Morphy was so bored when he wrote this blog :/
•  » » 6 years ago, # ^ |   0 Or he was too busy, maybe :o
 » 6 years ago, # | ← Rev. 2 →   +32 Upvote just for the amazing text :D
 » 6 years ago, # |   +32 No Delinur as problem translator?
 » 6 years ago, # |   0 Auto comment: topic has been updated by Morphy (previous revision, new revision, compare).
 » 6 years ago, # |   0 MikeMirzayanov is mentioned in announcement I guess ,no delay in closing ceremony this time :-p
 » 6 years ago, # |   0 Finally a nice short anouncement.
 » 6 years ago, # | ← Rev. 2 →   +13 at least for me I think longer round announcement with some words about authors like education, experiences, career,... will be better. and about problem statements I like short ones with little story I don't like statements like given x calculate f(x).
 » 6 years ago, # |   0 I hope that it will be a great contest and we will find out something about author's country
•  » » 6 years ago, # ^ |   +11 His country is Berland or Byteland. Neither of really existing ones.
•  » » » 6 years ago, # ^ |   +28 That moment when you realize that Berland is not an actual country.
•  » » » 6 years ago, # ^ |   0 And Byteforces it is.
 » 6 years ago, # |   +5 I will get lots of downvotes but I'll say it : I hope there will be lots of math in the contest !
 » 6 years ago, # |   +19 why the minutes before contest are like hours but the hours of duration of the contest are like few minutes?
 » 6 years ago, # |   -45 hello.who will help me to solve the questions of this contest
•  » » 6 years ago, # ^ |   +31 God
•  » » 6 years ago, # ^ |   +5 Whole community will be happy to help after the contest. :)
•  » » 6 years ago, # ^ |   +8 From the Beatles it sounds better... :D
•  » » 6 years ago, # ^ |   +7 Solve yourself. You won't get any benefit if you do like that.
 » 6 years ago, # | ← Rev. 2 →   +11 First problemset made by a peruvian coder in Codeforces :D!
 » 6 years ago, # |   +8 Morphy his nickname says math problems
•  » » 6 years ago, # ^ |   +6 And math problems we got.
 » 6 years ago, # |   +16 Am i the only one who didn't even understand the problem statement of problem C after trying it for 1 hour -_-
 » 6 years ago, # |   +3 I tried to send solution to A and forgot delete files and I got WA2. How it's possible that my solution passed first test?
 » 6 years ago, # |   +22 ZzZZzzzZZZZZzzzzzzzz is the true MVP of this contest!
•  » » 6 years ago, # ^ |   +44 Wow, first time I see my name on the comment :)
•  » » » 6 years ago, # ^ |   0 This must have been painful.
 » 6 years ago, # |   +16 I am sure lot of C are going to fail :)
•  » » 6 years ago, # ^ |   0 why?
•  » » 6 years ago, # ^ |   +3 calculating LCM with long long should overflow
 » 6 years ago, # |   0 The problems have been very difficult
 » 6 years ago, # |   +19 Terriblest C in my life :(
•  » » 6 years ago, # ^ |   0 C was a nice problem.... I actually enjoyed solving it.
 » 6 years ago, # |   +5 Problem C PreTest 11 :/ Kept failing on that pretest
•  » » 6 years ago, # ^ |   +2 That's because your LCM was bigger than long long's capacity
•  » » 6 years ago, # ^ |   0 Makes two of us.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Had the same problem, my lcm function returned negative values (overflow) for some big numbers.
•  » » 6 years ago, # ^ |   0 You get overflow while calculating LCM, I suppose.
•  » » » 6 years ago, # ^ |   0 too cruel :( why i am so dumb :(
 » 6 years ago, # |   +54 This was a very educational round.I learned like 20 ways to calculate N^2
•  » » 6 years ago, # ^ |   0 How come?
•  » » » 6 years ago, # ^ |   +21 Problem 2 was effectively a super glorified way of asking for (N-2)^2.When hacking solutions, people had all sorts of crazy lines that somehow came out to (N-2)^2My current favourite is 1+((n-3)*3)+(n-3)*(n-4)
•  » » » » 6 years ago, # ^ |   +1 Oh...haha!Poor guy, he must be thinking how come so many people already solved it so quickly :D
•  » » » » 6 years ago, # ^ |   +2 my was n-2+(n-3)*2+(n-4)*(n-3). I really like this formula.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 at first problem B looked impossible to solve and i was like "solved prob A and thats it for today!!"
•  » » » » 6 years ago, # ^ |   0 I used such an approach. Having seen some (n - 2)2 solutions I still don't know why it works :D
•  » » » » » 6 years ago, # ^ |   0 There is a nice explanation in the comments below. The main rays from 1 divides the plane in n-2 parts. Rays from each of the other vertices divide the parts into n-2 sub parts.
•  » » » » 6 years ago, # ^ |   +1 Haha, that was my line! :D
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I used that one, the idea is that the point 1, 2 and N create N-3 areas. All the other ones do N-4 so it's 3*(N-3) + (N-3)(N-4) + 1
 » 6 years ago, # |   0 How to solve D?
•  » » 6 years ago, # ^ |   +5 I almost got in time to solve it, missed a couple of minutes. My approach was: Clean up the tree, meaning we delete all the unneeded paths (if you draw your graph and then mark attacked nodes as red, unneeded paths are those which start at red node can't lead to any other red node). Sounds difficult, but computationally I just used a BFS starting from the nodes which are not attacked and which have only 1 child node. Find a diameter of the lefrover tree (this part is where I couldn't code the solution in time). Mark the nodes which the diameter consists of. Now start from one end, and traverse the nodes in the with the next dfs: first visit not marked nodes, calculating the distance on the way in and out, then visit the marked node, calculating the distance only once. Now the resulting distance is known, the starting node should be one of tho ends of the marked path (one with the lower index).I just haven't ever wrote a "find diameter of a tree" solution so I couldn't code the solution under the pressure.
 » 6 years ago, # |   0 Can anyone explain C, Wasted complete time in that one. I really cant wait for the editorial :p
 » 6 years ago, # | ← Rev. 2 →   +8 There's a point about C!Contestants which code with Python or Java which includes BigInteger option, could have solved this problem easily! Is this fair?!
•  » » 6 years ago, # ^ |   0 Yes, it is. You don't need the LCM(w,b), if it is bigger than t.
•  » » » 6 years ago, # ^ |   0 but you cant * if w and b are 10^18.
•  » » » » 6 years ago, # ^ |   0 For what do you need to multiply them?
•  » » » » » 6 years ago, # ^ |   0 to se if LCM(w,b) is bigger than t.
•  » » » » » » 6 years ago, # ^ | ← Rev. 7 →   0 So you don't know how to check it without direct multiplying?
•  » » » » 6 years ago, # ^ |   +1 k=a*b/gcd(a,b)Then, k=a/gcd(a,b); You can simply leave out multiplying it by 'b', and later multiply by b separately wherever needed. Hoping my solution passes
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Check if (b/__gcd(w, b)) * w give overflow first. If it does, then it definitely greater than t.How to do that: #define ull unsigned long long bool overFlow(ull a, ull b) { return ((a*b)/b == a); } 
•  » » 6 years ago, # ^ |   0 That is really easy to solve this problem without any big numbers. The only problem is to check a * b > max long long.
•  » » » 6 years ago, # ^ |   0 Even that is not a problem, you see. Hoping my solution passes.
 » 6 years ago, # |   0 respect for E. Came up with solution, but haven't managed to code it in time. Beautiful problem imho
 » 6 years ago, # |   0 Share your C hacks! Mine was 5000000000000000000 274177 67280421310721 for unsigned long longs, because the product of the last two numbers is precisely 2^64 + 1
•  » » 6 years ago, # ^ |   0 2 5 6, and the ans should be 1/1, some(including myself, got hacked) output X/1 where X > 1
•  » » 6 years ago, # ^ |   0 mine was 4801439824104652701 10000000000007 1000000007correct output: 1000000006/4801439824104652701
•  » » » 6 years ago, # ^ |   +4 unfortunately you weren't in my room and my wrong solution passed http://codeforces.com/contest/592/submission/13990910
•  » » 6 years ago, # ^ |   0 what is the correct output?
 » 6 years ago, # |   +18 if (minA < minB) cout << "A\n"; else cout << "B\n"; It seems that many people made this mistake at problem A. :)
•  » » 6 years ago, # ^ |   0 need <= got a WA from here
•  » » 6 years ago, # ^ |   0 I utilized it for hacking 6 solutions, but due to this missed C by a few seconds :) :(
•  » » 6 years ago, # ^ |   0 Wasn't this tested in the pretests?
•  » » 6 years ago, # ^ |   +5 Some people failed coding a O(n^2) solution. I've hacked with this test case ........ ..B..... ......W. ..W..... ........ ........ ..B..... ........ Because they didn't check the 'B' in position (7, 3)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I got 4 hacks using this :D ........ .W...... ........ ........ ........ ........ ......B. ........ 
 » 6 years ago, # |   0 Is the solution for problem E the number of triangles over points (ri - c, wi - d) that contain the origin?
•  » » 6 years ago, # ^ |   0 Yes, strictly.
•  » » 6 years ago, # ^ |   +5 Yes, I believe so. It's a pretty standard problem, so I already had code that solves the problem where it's not strict (see here: http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084 http://contest.usaco.org/TESTDATA/OPEN10.tricount.htm)
•  » » » 6 years ago, # ^ |   +5 Yeah I tend to fail whenever floating point issues are involved :PAlso looked for code online and didn't find it — did people submit any sub-N^2 sols for the TC? Didn't know about the usaco problem.
•  » » » » 6 years ago, # ^ |   +8 I don't think many people submitted sub N^2 (I did, since I already had the code). The usaco solution I linked also doesn't use floating point numbers.
•  » » » » » 6 years ago, # ^ |   0 Oh wait you don't need floating points here do you... Whoops thought you did due to some earlier idea I discarded. Ah I see ok this should work now thanks!
 » 6 years ago, # | ← Rev. 3 →   0 my way for solving C were that count the number of k and k' that ka + c = k'b + c then the answer is mul that to number of such "c" that it is min(a , b) — 1 that(non of a and b are not 1) is it true? i could not write its code in true way!
•  » » 6 years ago, # ^ |   0 i'm so stupid! i need just using lcm(a , b) instead of a*b!i won't become a programmer! :( ;_; !
 » 6 years ago, # |   0 What the hell does it mean to hack problems ? For no reason someone hacked my problem A,which is quite rude since I thought a lot at how to get it done.I locked my problems because I thought this is a way to show that I am sure of my solution,and I that's what I get...
•  » » 6 years ago, # ^ |   0 maybe you need to be more care about anwser's correctly
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 Well, getting hacked helps a lot of times.. its better to get hacked, and re-attempt, then to fail at the sys-tests.What a lot of people do , is only lock if they are pretty sure that their code won't go wrong on some boundary cases, or if their approach is completely right.I only lock, after I am pretty sure, or my codes have sustained some failed hack attempts.
•  » » 6 years ago, # ^ |   +16 It is a feature of contests in Codeforces. It just means that somebody looked at your solution, found a bug that was not being tested for in the pretests, and made your program fail to earn themselves points. You get to correct your solution when they do that (if you haven't locked that problem), so it benefits you, actually. If you submit a solution that passes pretests but has a bug, it will ultimately fail system tests assuming that the problemsetter has robust system tests. So being hacked is actually better than not being hacked, imo :)
 » 6 years ago, # |   0 How to solve Div2 B?
•  » » 6 years ago, # ^ |   +3 (n — 2)^2
•  » » » 6 years ago, # ^ |   +3 Why ?
•  » » » 6 years ago, # ^ |   0 what was your approach for above formula
•  » » » » 6 years ago, # ^ |   +3 I guess. I calculated for 3 .. 10 and it is correct ! :)P.S I am not mathlover :)
•  » » » 6 years ago, # ^ |   -6
•  » » » » 6 years ago, # ^ |   0 use long long
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +1
•  » » » » 6 years ago, # ^ |   0 overflow?
•  » » » » 6 years ago, # ^ |   0 no you got overflow answer bigger than to fit in int
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   +4 Don't forget about limits. 54319*54319=2950553761
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 The answer will be (n-2)^2. If you draw a few small samples, you will notice that the point 1 divides the area into n-2 sub-areas, and after performing the steps for all the verticles, each of these areas gets divided into n-2 further sub-areas . Hence, (n-2)^2.
 » 6 years ago, # |   +1 Just a combined contest!!!
 » 6 years ago, # | ← Rev. 2 →   +3 Div2-D today killed me. Spend 1 hour 30 minutes just to get WA on pretest 9. Is there anything special in it? I almost died with that.Anyway, why Div2-B answer is always (n-2)^2?
•  » » 6 years ago, # ^ |   +2 If you follow what the problem statement says, the polygon will be divided the n-2 triangles and each triangle will be divided to n-2 areas. So the number of total areas would be (n-2)^2
•  » » 6 years ago, # ^ |   0 What was your idea? I have got WA3 with this one: find two bad vertices with maximum distance.Find subgraph which have all bad vertices in it, and there is no outside. Answer is (2*(number of vertices in subgraph)- maximum distance between bad vertices).
•  » » » 6 years ago, # ^ |   0 Exactly the same with my idea. Don't know if this idea is incorrect, or there's some problem with my implementation.
•  » » » 6 years ago, # ^ |   0 I think it should be (2*(number of EDGES in subgraph)- maximum distance between bad vertices), which is always 2 less than what your algorithm would answer. But I might be wrong, because that would give WA for the sample tests as well, and I suppose you tried those, right?
•  » » » » 6 years ago, # ^ |   0 Yeah I meant edges.Thanks
•  » » 6 years ago, # ^ |   +32 killed you ? that's cute
•  » » » 6 years ago, # ^ |   0 Got killed 44 times? Scary...
•  » » » 6 years ago, # ^ |   -17 fuckk them fuckk this autor
•  » » 6 years ago, # ^ |   0 I actually saw the pattern then went forward to write a small induction proof that says that the addition of a new point to any polygon with n regions will introduce 2n-1 new regions.And we know that n^2 + 2n-1 = (n+1)^2.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 No.Actually, the first vertex is special — it creates (n — 2) polygons. The second vertex and the last ones also require special treatment. They both create (n — 3) new polygons.All the rest vertices add (n — 4) polygons each. And there are (n — 3) of such vertices. That means these ordinary vertices create (n — 3) * (n — 4) polygons in total.So, you get the formula: (n — 2) + 2 * (n — 3) + (n — 3) * (n — 4) = (n — 2) * (n — 2)
•  » » » » 6 years ago, # ^ | ← Rev. 5 →   0 I had to convince myself with that formula by drawing.When I meditate long enough over that picture, the formula becomes obvious :)
•  » » » » 6 years ago, # ^ |   0 In your statement n => number of vertices In mine n=> number of polygons in the ith step. Adding the (i+1)th vertex introduces 2*n-1 polygons. Again n=>number of polygons in ith step.
•  » » 6 years ago, # ^ |   0 I actually dint have time to code it but I guess the right answer is to find the MST connecting the attacked cities and apply the twice around the tree algorithm and then somehow find the shortest path in linear time
 » 6 years ago, # |   +1 Competed after, like 5 contests due to some or the other reason for missing them. Felt so good :) Got A hacked, but still, I'm happy to be able to compete today :)
 » 6 years ago, # |   0 Here is my strategy for CLet w <= b We can find lcm(w,b)What is the number of multiples of lcm(w,b) <= T say x.Now extend x by b to get y = x+b.If y <= T we do x+=w-1. //add w-1 more numbers else x += T-biggest multiple of lcm(w,b)Finally if w>1 x+=1print x/TIs this correct?
 » 6 years ago, # |   +19 TOO MANY OVERFLOWS in this contest :|
•  » » 6 years ago, # ^ |   +27 Codeforces Round #-328481999481AKACodeforces Round #OVERFLOW
•  » » 6 years ago, # ^ |   +9 Codeforces Round #328 — Halloween Special: Overflowed Overflow
 » 6 years ago, # |   -6 XD my submitions for Div 2 B!!!1- (n-2)^22- n^2 — 4n + 4XD XD!
 » 6 years ago, # |   0 hope everyone gets high rating :)
 » 6 years ago, # |   +4 D — easier version of Problem 6 — KAMP from http://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf.
 » 6 years ago, # |   0 I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.
 » 6 years ago, # |   0 I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.
 » 6 years ago, # |   +43 Please start system testing. we all are waiting ! :(
 » 6 years ago, # |   +21 So. Era of long wait for System Tests and rating changes has begun.
 » 6 years ago, # |   0 Auto comment: topic has been updated by Morphy (previous revision, new revision, compare).
 » 6 years ago, # |   +6 please start system testing!!!!
 » 6 years ago, # |   0 TIL Python is a good language for competition programming.
 » 6 years ago, # |   +4 problem D is really nice! Had a lot of pleasure when solve it :)
 » 6 years ago, # |   +11 Oh please system testing, don´t let my solution for C, falls into the abyss :(
 » 6 years ago, # |   +7 Return TestsNotFound Exception()
 » 6 years ago, # |   +12 Return TestsNotFound Exception()
•  » » 6 years ago, # ^ |   +9 The System punished me and doubled my comment :(
 » 6 years ago, # |   0 Editorial before System Test :o
 » 6 years ago, # | ← Rev. 3 →   0 .
•  » » 6 years ago, # ^ |   +17 It will be soon. Sorry for delay.
 » 6 years ago, # |   +12 Waiting for systest got me like
•  » » 6 years ago, # ^ | ← Rev. 2 →   0
 » 6 years ago, # |   0 Problem analysis and not Editorial, Well that's a first!!!
•  » » 6 years ago, # ^ |   0 actually nothttp://codeforces.com/blog/entry/21185
 » 6 years ago, # | ← Rev. 2 →   -7 Thanks for the speedy editorial! :)
 » 6 years ago, # |   +7 Wrong answer on test 106? O.o
•  » » 6 years ago, # ^ |   0 You are really good....
•  » » » 6 years ago, # ^ |   +5 And you know, I got AC just by swapping some characters :|
•  » » » » 6 years ago, # ^ |   0 Strange.... I still can't send solutions.
•  » » » » 6 years ago, # ^ |   +3 Heeeyyyy, I've got WA106 too!:DD
•  » » 5 years ago, # ^ |   0
 » 6 years ago, # |   +3 I was so confused about my solution of C and D . System Test was so late that I wrote many random huge dataset for them and took high rated coder's code as AC solution . My code worked for them and got some relief . :D
 » 6 years ago, # |   +5 Please improve the problem statements, some of them were irritating.
 » 6 years ago, # |   0 Auto comment: topic has been updated by Morphy (previous revision, new revision, compare).
 » 6 years ago, # |   0 I'm not sure why my solution for C is wrong..My source is here. http://codeforces.com/contest/592/submission/13988182
•  » » 6 years ago, # ^ |   0 I compare using double to avoid overflow.. Is that a problem? Test 58 shows wrong answer, but it shows correct answer on my local environment..
•  » » » 6 years ago, # ^ | ← Rev. 6 →   +4 This is a precision problem. Note that in the failing testcase we have and t = lcm(w, b) = w * b. But multiplying w and b apparently introduces a floating point error that makes lcm(w, b) exceed t, resulting in the wrong answer.Here is the accepted solution: 13994692. I replaced the doubles with long doubles (and also fixed a bug in your gcd function). In general though, I would not recommend completely replacing integer computation with floating point computation, this problem can easily be done with integer arithmetic alone (e.g. by noticing that is equivalent to , and then after establishing that t exceeds the lcm you can safely compute it).
•  » » » » 6 years ago, # ^ |   0 Thanks. I've checked and I have one more question.I'm using MS C++, and if I choose MS C++ solution still shows wrong answer. But if I choose G++11, solution passes.Is MS C++ has a precision problem? G++ is more accurate?
•  » » » » » 6 years ago, # ^ |   0 See here, for some odd reason long doubles use 8 bytes in MS C++ (exactly the same as doubles), whereas G++ gives them 12 bytes (also 8 bytes for floats). Go to custom invocation and run this code with both compilers: #include using namespace std; int main() { cout << sizeof(long double) << endl; return 0; } 
•  » » » » » » 6 years ago, # ^ |   0 I still don't understand why 'double' works in G++, do not work in MS C++. They both using 8 bytes, but their precision is different?
•  » » » » 6 years ago, # ^ |   0 I've checked once again, just using 'double' instead of 'long double'. 'double' is enough if I use G++. MS C++ sucks...
 » 6 years ago, # |   +5 Why are the problems not up for practice?
 » 6 years ago, # |   +3 Problem C wrong answer test case 58 it's weird because my machine shows correct answer, but on codeforces output is different. and i am not using any built in functions . Any explaination?
•  » » 6 years ago, # ^ |   0 You have same problem with me... weird...
•  » » 6 years ago, # ^ |   0 I have the same problem on the same test.
•  » » 6 years ago, # ^ |   0 i changed double to long double and got accepted
 » 6 years ago, # | ← Rev. 4 →   -8 What is the maximum size of an int when using MS C++ on codeforces? This question pertains to this codeforces problem: 328 div 2 problem BThis code:  #include using namespace std; int main(int argc, char **argv){ int points; cin >> points; unsigned long long answer = 1 + (points-3) + 2*(points-3) + (points-3)*(points-4); cout << answer << endl; return 0; } produces an output of: 18446744072365138081 when given an input of: 54321 The correct answer is: 2950553761Yet.....This code produces the correct answer for all of the test cases.  #include using namespace std; int main(int argc, char **argv){ int points; cin >> points; unsigned long long answer = 1 + (points-3) + 2*(points-3) + (points-3)*(points-4); cout << answer << endl; return 0; }Last time I checked the maximum size of an int is much bigger than 54321.
•  » » 6 years ago, # ^ |   +3 points = 54321 (points — 3) * (points — 4) = 54318 * 54317 = 2 950 390 806 MAX_INT = 2^31 — 1 = 2 147 483 647 (points — 3) * (points — 4) > MAX_INT try this 1LL * (points — 3) * (points — 4)
•  » » » 6 years ago, # ^ |   0 Thanks!
 » 6 years ago, # | ← Rev. 2 →   +1 Is the round unrated? My rating change is gone.UPD: Sh*t, it's back :D
•  » » 6 years ago, # ^ |   0 I noticed the same thing--thought I was going crazy for a second.
 » 6 years ago, # |   +12 Problem C is a little unfair to C/C++ coder!
•  » » 6 years ago, # ^ |   0 There was a bit of discussion above. The general consensus is that BigInts aren't really necessary to solve this problem, you just need to be clever about how you handle your calculation of LCM.And if you know C/C++, and really don't want to handle big numbers, then learning a bit of Java shouldn't be too much of a stretch.Also there's that one datatype, __uint128_t, I think it was. Last I checked, there was actually no overload to print it, but you might be able to use it as an intermediary for holding large numbers. I haven't tried, so don't quote me on that last one though.
•  » » » 6 years ago, # ^ |   +7 Well, it's certainly easier to use python or java than c++ on C, and the main mistakes people made on the problem would not have been made to c++.Personally, after seeing the limit I immediately switched to coding python in Custom Invocation, and I think it would be better to have problems that don't require much additional thinking (algorithmic not implementation) for different languages.
•  » » 6 years ago, # ^ |   0 So either you learn how to handle big numbers, or you learn a new language. Choice is yours. I personally would go with the first , if the only reason to learn a new language is to avoid having to handle big ints :p
•  » » 6 years ago, # ^ |   +4 Search for "C++ BigInteger". There are some short & good implementations that you can use for contests.
 » 6 years ago, # | ← Rev. 2 →   +3 I still can't believe that I got the rank#2 >.< It was my best result >.< But I hope that I can pass the NOIP(a contest in China). If I can't pass it, I will keep away from OI. QAQ
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I am a Chinese Sophomore, but I don't heard the NOIP in high school. Now, I'm studying hard. Come on and good luck!
•  » » 6 years ago, # ^ |   0 Good luck!
 » 6 years ago, # | ← Rev. 2 →   +6 In the past contest, I tried to solve "Problem C — The Big Race", eventually, got wrong answer on test 58 However, I check my program with the test 58 locally, the answer is correct! I'm confused! Does anyone know why? Thanks!pic 1 -- localpic 2 -- online judgeP.S: I got AC when changed unsigned long long to long long Still do not why......
•  » » 6 years ago, # ^ |   +4 It is related with double's precision error.w*b is q, therefore a-q is zero, and sgn(a-q) should be 0 if there is no precision error.However, with how compiler optimize the code, result can be different within machine epsilon. That depends on compiler, even unsigned long long and long long can be different. In Codeforces environment, a-q might little bigger than zero, and it may occur wrong answer.Avoid using real number as possible as you can.
•  » » » 6 years ago, # ^ |   0 Thank you for your advice!
 » 6 years ago, # |   0 nice medals :)
 » 6 years ago, # |   0 I still can't understand the problem C , can any body explain it ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 M = min(w, b)G = gcd(w, b)L = lcm(w, b)K = t div LAll distances D, when Willman and Bolt tie have form D = k*L + r, where 0 ≤ k ≤ K and 0 ≤ r < M.Why it is true? Easy to see than for all D Willman and Bolt run for k*L meters. And for all another distance if M = w Willman run for k*L + w meters, when Bolt run for k*L meters.All possible D is k*L+r (except 0). How to find count of that? Let's imagine table, where row indexed 0..K, and columns indexed 0..M-1. And fill table with all possible D. Then one can see, than ans = M * K - 1 (for all rows exsept last)  +  min(t - k * L + 1, M) (for last row).Example: t = 10, w = 2, b = 3.M = 2G = 1L = 6K = 1Draw table 0 10 0 11 6 7 ans  =  2 * 1 - 1  +  min(10 - 1 * 6 + 1, 2)  =  1  +  min(5, 2) = 3
•  » » » 6 years ago, # ^ |   0 thanks , but i wasn't looking for a solution i didn't understand the problem it self , for example for the first sample why 6 is a tie ?
•  » » » » 6 years ago, # ^ |   +1 because both runners in same time 6 meters, and because of abyss no one can run more, so it's tie. Same thins for 7 — both will run 6 meters.
 » 6 years ago, # |   +15
 » 6 years ago, # | ← Rev. 2 →   0 During the contest, I got a solution for D but it failed on test case 3. I have debugged it with over a dozen small corner test cases, but I can't find the mistake that its making on the 3rd case. The 3rd test case's first line is 123456 123456, and my incorrect output says to start from node 1, but the correct answer is some other node which yields a smaller distance than what I output.Is there a special thing you must consider for this test case, and did anyone else have the same problem? If someone could help me with my code that would be great; it is fully commented at http://pastebin.com/m5yEa778. I also appreciate feedback on style, tips for simplification, etc.My method was (as far as I can tell) equivalent to the official solution. I remove all unnecessary edges, then find the two farthest nodes from the root in different subtrees and use the one with smallest index to start (I assume this is the diameter).Edit: For some reason my browser arbitrarily italicized parts of this text; is there a way to fix this?
 » 6 years ago, # | ← Rev. 2 →   -8 The rating chances were awkard, imo. Div 2 rank 1 got a delta of 200 and Div 1 rank 2 got less than 100 beating lots of red targets ... And Div1 rank 1 seems to had get a negative delta getting the best rank possible. How does this exactly works?Edit: Ok, I realized my blunder! stop downvoting! :(
 » 6 years ago, # |   0 Interesting problems,thx
 » 6 years ago, # |   0 Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...This is my humble opinion, but i think others will agree.
 » 5 years ago, # |   0 Problem C should add a test data: 5*10^18 5*10^18 5*10^18 though my buggy code can get an Accept, but when it running with 5*10^18 5*10^18 5*10^18, it will result to Outside the range of int64.