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
Краткость — сестра таланта :)
"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
А теперь всех кто поставил + ждет бан =)
.
Short announcement :D great!
Let's hope for short problem statements too.
but it was long problems :|
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!!
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 Morphy was so bored when he wrote this blog :/
Upvote just for the amazing text :D
No Delinur as problem translator?
Как боженька смолвил.... ;)
Auto comment: topic has been updated by Morphy (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
God
Whole 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!
Morphy 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?
ZzZZzzzZZZZZzzzzzzzz is the true MVP of this contest!
Wow, first time I see my name on the comment :)
This must have been painful.
У меня 228 за А
I am sure lot of C are going to fail :)
why?
calculating LCM with long long should overflow
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 somehow came out to (N-2)^2
My 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 :D
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.
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.
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 thant.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://mirror.codeforces.com/contest/592/submission/13990910
what is the correct output?
It seems that many people made this mistake at problem A. :)
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
Психанул
P.S. Еще и А упадёт.
Ну у тебя это хоть не официальный контест:D (Хотя я и не пытался взламывать)
Is the solution for problem E the number of triangles over points (ri - c, wi - 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...
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.S I am not mathlover :)
Wrong...
use long long
Nooooooooooooooooooooo!
no you got overflow answer bigger than to fit in int
Don't forget about limits. 54319*54319=2950553761
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 :)
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 :)
TOO MANY OVERFLOWS in this contest :|
Codeforces Round #-328481999481
AKA
Codeforces Round #OVERFLOW
Codeforces Round #328 — Halloween Special: Overflowed Overflow
XD my submitions for Div 2 B!!!
1- (n-2)^2
2- n^2 — 4n + 4
XD XD!
Верно ли, что задача D решается за O(n*log(n))? Почему может быть TL на 9-м претесте?
я решил(ну еще, правда, не отправил, тк на контесте не успел) за O(n)
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 Morphy (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
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
Насколько корректно в задаче C не принимать ответ 1, а вместо него требовать 1/1?
На 100%, поскольку просят вывести ответ в виде несократимой дроби
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 Morphy (previous revision, new revision, compare).
I'm not sure why my solution for C is wrong..
My source is here. http://mirror.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 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).
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?
У меня тут уже минут 40 систестирование висит на 100%. Это норма?)
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
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 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.
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 -- local
pic 2 -- online judge
P.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!
Медали в посте подтолкнули на мысль о том, чтобы добавить возможность получать achievements(медали за места, n взломов за контест, решил все задачи div 1, и т.д.) в профиль. Или хотя бы чтобы призовые места где-то кроме рейтинга отдельно фиксировались. Кстати а за призовые места в div2 дают какой-то приз?
Нет, но система достижений здесь присутствует. (Пусть и не на самом codeforces)
Глянь сюда
Интересно! Спасибо.
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 ≤ 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 = 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) = 3
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 ?
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?
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.