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: galois (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**

"Codeforces and Polygon: MikeMirzayanov" wrong. mikemirzayanov is a human he can not be codeforces and polygon. he is codeforces and polygon manager and creator.

Well , we aren't in English class :D

it is not about english . in any language it is wrong.

We are in logic class :)

MikeMirzayanov is human.. Thank you, I always thought he was like this

А теперь всех кто поставил + ждет бан =)

.

You were wrong because this Also cannot be "Codeforces and Polygon".

Short announcement :D great!

Let's hope for short problem statements too.

but it was long problems :|

GlebsHP is our new co-coordinator, right? Congrats GlebsHP :)

hope there is no Physics and Chemistry problems this time :))

What about biology?

:P

maybe other subjects such as sociology and ... :|

How about history? I have history exam tomorrow.

and literature and geography :|

>look I know how to greentext

>implying geography is a "humanities science"

But I agree otherwise.

I don't find anything wrong with this "Biology" problem: 579A - Raising Bacteria

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

In some countries October 31st is Halloweens Day. Hope to see some Ghouly questions?

waiting and hope nice rate this time :)

short and good blog :) thanks

is this your first time ?

Yes If he's any previous one , simply you will find a "Problemsetting" section in his profile :)

It looks like galois was so bored when he wrote this blog :/

Or he was too busy, maybe :o

Upvote just for the amazing text :D

No Delinur as problem translator?

Auto comment: topic has been updated by galois (previous revision, new revision, compare).MikeMirzayanov is mentioned in announcement

I guess ,no delay in closing ceremony this time :-p

Finally a nice short anouncement.

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).

I hope that it will be a great contest and we will find out something about author's country

His country is Berland or Byteland. Neither of really existing ones.

That moment when you realize that Berland is not an actual country.

And Byteforces it is.

I will get lots of downvotes but I'll say it : I hope there will be lots of math in the contest !

why the minutes before contest are like hours but the hours of duration of the contest are like few minutes?

hello.who will help me to solve the questions of this contest

GodWhole community will be happy to help after the contest. :)

please help me,please,please

From the Beatles it sounds better... :D

Solve yourself. You won't get any benefit if you do like that.

First problemset made by a peruvian coder in Codeforces :D!

galois his nickname says math problems

And math problems we got.

Am i the only one who didn't even understand the problem statement of problem C after trying it for 1 hour -_-

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?

Janbolat is the true MVP of this contest!

Wow, first time I see my name on the comment :)

This must have been painful.

I am sure lot of C are going to fail :)

why?

calculating LCM with long long should overflow

The problems have been very difficult

Terriblest C in my life :(

C was a nice problem.... I actually enjoyed solving it.

Problem C PreTest 11 :/ Kept failing on that pretest

That's because your LCM was bigger than long long's capacity

Makes two of us.

Had the same problem, my lcm function returned negative values (overflow) for some big numbers.

You get overflow while calculating LCM, I suppose.

too cruel :( why i am so dumb :(

This was a very educational round.

I learned like 20 ways to calculate N^2

How come?

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

somehowcame out to (N-2)^2My current favourite is 1+((n-3)*3)+(n-3)*(n-4)

Oh...haha!Poor guy, he must be thinking how come so many people already solved it so quickly :D

my was n-2+(n-3)*2+(n-4)*(n-3). I really like this formula.

at first problem B looked impossible to solve and i was like "solved prob A and thats it for today!!"

I used such an approach. Having seen some (

n- 2)^{2}solutions I still don't know why it works :DThere 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.

Haha, that was my line! :D

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

How to solve D?

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.

Can anyone explain C, Wasted complete time in that one. I really cant wait for the editorial :p

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

Yes, it is. You don't need the

`LCM(w,b)`

, if it is bigger than`t`

.but you cant * if w and b are 10^18.

For what do you need to multiply them?

to se if LCM(w,b) is bigger than t.

So you don't know how to check it without direct multiplying?

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

Check if (b/__gcd(w, b)) * w give overflow first. If it does, then it definitely greater than t.

How to do that:

That is really easy to solve this problem without any big numbers. The only problem is to check a * b > max long long.

Even that is not a problem, you see. Hoping my solution passes.

respect for E. Came up with solution, but haven't managed to code it in time. Beautiful problem imho

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

2 5 6, and the ans should be 1/1, some(including myself, got hacked) output X/1 where X > 1

mine was 4801439824104652701 10000000000007 1000000007

correct output: 1000000006/4801439824104652701

unfortunately you weren't in my room and my wrong solution passed http://codeforces.com/contest/592/submission/13990910

what is the correct output?

It seems that many people made this mistake at problem A. :)

need <= got a WA from here

I utilized it for hacking 6 solutions, but due to this missed C by a few seconds :) :(

Wasn't this tested in the pretests?

Some people failed coding a O(n^2) solution. I've hacked with this test case

Because they didn't check the 'B' in position (7, 3)

I got 4 hacks using this :D

Is the solution for problem E the number of triangles over points (

r_{i}-c,w_{i}-d) that contain the origin?Yes, strictly.

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)

Yeah I tend to fail whenever floating point issues are involved :P

Also 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.

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.

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!

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!

i'm so stupid! i need just using lcm(a , b) instead of a*b!

i won't become a programmer! :( ;_; !

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

maybe you need to be more care about anwser's correctly

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.

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 :)

How to solve Div2 B?

(n — 2)^2

Why ?

what was your approach for above formula

I guess. I calculated for 3 .. 10 and it is correct ! :)

P.SI am not mathlover :)Wrong...

use long long

Nooooooooooooooooooooo!

overflow?

no you got overflow answer bigger than to fit in int

Don't forget about limits. 54319*54319=2950553761

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.

Just a combined contest!!!

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?

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

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).

Exactly the same with my idea. Don't know if this idea is incorrect, or there's some problem with my implementation.

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?

Yeah I meant edges.Thanks

killed you ? that's cute

Got killed 44 times? Scary...

fuckk them fuckk this autor

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.

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)

I had to convince myself with that formula by drawing.

When I meditate long enough over that picture, the formula becomes obvious :)

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.

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

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 :)

Here is my strategy for C

Let 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+=1

print x/T

Is this correct?

TOO MANY OVERFLOWS in this contest :|

Codeforces Round #-328481999481

AKA

Codeforces Round

#OVERFLOWCodeforces Round #328 — Halloween Special: Overflowed Overflow

XD my submitions for Div 2 B!!!

1- (n-2)^2

2- n^2 — 4n + 4

XD XD!

hope everyone gets high rating :)

D — easier version of Problem 6 — KAMP from http://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf.

I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.

I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.

Please start system testing. we all are waiting ! :(

So. Era of long wait for System Tests and rating changes has begun.

Auto comment: topic has been updated by galois (previous revision, new revision, compare).please start system testing!!!!

TIL Python is a good language for competition programming.

problem D is really nice! Had a lot of pleasure when solve it :)

Oh please system testing, don´t let my solution for C, falls into the abyss :(

Return TestsNotFound Exception()

Return TestsNotFound Exception()

The System punished me and doubled my comment :(

Editorial before System Test :o

.

It will be soon. Sorry for delay.

Waiting for systest got me like

Relevant

Problem analysis and not Editorial, Well that's a first!!!

actually not

http://codeforces.com/blog/entry/21185

Thanks for the speedy editorial! :)

Wrong answer on test 106? O.o

You are really good....

And you know, I got AC just by swapping some characters :|

Strange.... I still can't send solutions.

Heeeyyyy, I've got WA106 too!:DD

hahaha

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

Please improve the problem statements, some of them were irritating.

Auto comment: topic has been updated by galois (previous revision, new revision, compare).I'm not sure why my solution for C is wrong..

My source is here. http://codeforces.com/contest/592/submission/13988182

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

This is a precision problem. Note that in the failing testcase we have and

t=lcm(w,b) =w*b. But multiplyingwandbapparently introduces a floating point error that makeslcm(w,b) exceedt, 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

texceeds the lcm you can safely compute it).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?

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:

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?

I've checked once again, just using 'double' instead of 'long double'. 'double' is enough if I use G++. MS C++ sucks...

Why are the problems not up for practice?

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?

You have same problem with me... weird...

I have the same problem on the same test.

i changed double to long double and got accepted

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 B

This code:

`#include <iostream> 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: 2950553761

Yet.....This code produces the correct answer for all of the test cases.

`#include <iostream> 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.

try this

Thanks!

Is the round unrated? My rating change is gone.

UPD: Sh*t, it's back :D

I noticed the same thing--thought I was going crazy for a second.

Problem C is a little unfair to C/C++ coder!

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

reallydon'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

printit, 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.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.

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

Search for "C++ BigInteger". There are some short & good implementations that you can use for contests.

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

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!

Good luck!

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

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.

Thank you for your advice!

nice medals :)

I still can't understand the problem C , can any body explain it ?

M = min(w, b)

G = gcd(w, b)

L = lcm(w, b)

K = t div L

All distances D, when Willman and Bolt tie have form D = k*L + r, where 0 ≤

k≤Kand 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 = 2

G = 1

L = 6

K = 1

Draw table

0 1

0 0 1

1 6 7

ans= 2 * 1 - 1 +min(10 - 1 * 6 + 1, 2) = 1 +min(5, 2) = 3thanks , 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 ?

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.

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?

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

Interesting problems,thx

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.

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.