### mfv's blog

By mfv, history, 6 years ago,

Hello, Codeforces!

“Experimental Educational Round: VolBIT Formulas Blitz” will take place on February 18, 2016 at 18:00 MSK. This time the problemset is recommended for Div.2 participants.

The round will be unrated for all users and it will be held according to the standard ACM-ICPC rules. You will have 180 minutes (three hours) to solve 18 problems. There will be no open hacks phase after the round.

Our main target audience is beginners and Div. 2 members. All offered problems can be solved without conditional constructs and without loops. Only formulas are required. Assignments and functions can be used to reduce code duplication.

The topics of the problems are:

• combinatorics
• geometry
• game theory
• sequences
• other

The round is created as a part of Vologda BIT event, also as part of this event “Contest programming from zero in Java” webinars were held devoted to the topics listed above. Recordings of the webinars are available on YouTube (in Russian).

The round was prepared by me, Fyodor Menshikov mfv, Igor Andrianov igand and Oleg Strekalovsky OSt. Special thanks to Maria Belova Delinur for bugfixing the English statements and of course to MikeMirzayanov for Codeforces platform and Polygon. Polygon made our checkers and tests for this contest better.

UPD: The editorial is complete.

• +295

 » 6 years ago, # |   +17 18 problems in 3 hours !!!! this looks challenging (1 problem per 10 mins).. especially in these topics .. can't wait ;)
•  » » 6 years ago, # ^ |   +7 You are welcome!
•  » » 6 years ago, # ^ |   +252 1 problem per 10 mins :)
•  » » » 6 years ago, # ^ |   +19 10 minutes is not for coding !! It is for reading, translating, solving and coding :))
•  » » » » 6 years ago, # ^ |   0 I hope that you learned How to reading, translating, solving and coding less than 10 min for each problem ... Sample test + cout<< was enough for some of problems... It is need 10 seconds not 10 mins :)
•  » » » 6 years ago, # ^ |   -12 KPACUBO [user:KRACUBO]
•  » » 6 years ago, # ^ |   +1 You can see that in many of Div. 2 contests Problem A and sometimes B solved in less than 10 minutes by a lot of users ... So you can see that mfv said much times that the difficulty will be low.
•  » » » 6 years ago, # ^ |   0 Is it PrinceOfPersia's dummy ?
•  » » » » 6 years ago, # ^ |   0 I asked from him ( PrinceOfPersia ) and he said no !
•  » » » » 6 years ago, # ^ |   0 Just his fan
 » 6 years ago, # | ← Rev. 2 →   0 Сertainly, some common functions from standard math libraries can be used.
•  » » 6 years ago, # ^ |   +14 Yes, particularly sin, cos, tan, asin, acos, atan, PI sqrt, pow, abs Also bitwise shifts can be a part of the formula. There will be no need to use long arithmetic such as BigInteger/BigDecimal in Java.Maximum required types are 64-bit integer and 64-bit floating point.Contestants are allowed to use conditions, loops, long arithmetic, etc, but we hope that these constructs will not help. :-)
•  » » » 6 years ago, # ^ |   0 Pl?
•  » » » » 6 years ago, # ^ |   0 Math.PI in Java
 » 6 years ago, # |   +2 Math ,, 1 problem per 10 mins ,, sorry i’m outit is unratedi’m in :v
 » 6 years ago, # | ← Rev. 2 →   +20 As a beginner, I can't express how excited I'm for this round. This, for sure, is going to be a memorable experience. :)
 » 6 years ago, # |   0 No, registration required ?
•  » » 6 years ago, # ^ |   0 Registration will be open till the end of the contest.
 » 6 years ago, # |   +12 It is good to see codeforces coming up with different types of contests. It really helps a lot.
 » 6 years ago, # |   +58 #include #include #include // ANY COMMENT? 
•  » » 6 years ago, # ^ | ← Rev. 2 →   +89 #include 
•  » » » 6 years ago, # ^ |   -29 #include //not Codeforces :)
•  » » » 6 years ago, # ^ |   +2 oeis.org may help in some problems but not required if you know combinatorics.
•  » » 6 years ago, # ^ |   +3 We hope that Google and Wikipedia will not help. It is not easy to create good request when the problem statement is a legend, not in mathematical terms one.
• »
»
6 years ago, # ^ |
-14

# include

•  » » » 6 years ago, # ^ |   +16 it seems that Codeforces currently supports markdown. You may need to quote your include in a code block, or add a '\' in front of #, or it will regard your include as a title, and all we can see is just include.good example : solution A c++#include  solution B \#include Choose either one will solve your problem.
 » 6 years ago, # |   +18 The contest name should be : Fast as Ferrari !
 » 6 years ago, # |   +9 I think this is a great idea, and I will certainly enjoy this contest. The only thing I regret is the absence of an open hacks phase after the round end, I think this could be a good oportunity to learn about reducing error, and how to write stable formulas when working with doubles.
 » 6 years ago, # |   +3 What do they mean by "this contest is unrated"?
•  » » 6 years ago, # ^ |   +18 Rating of the round participants will not change.
 » 6 years ago, # |   +3 So ineresting!
•  » » 6 years ago, # ^ |   0 interesting
•  » » » 6 years ago, # ^ |   +5 oh.. I'm so careless Haha.
 » 6 years ago, # |   +25 Hope there will be short statements...
 » 6 years ago, # |   0 Will the problems be sorted from easiest to hardest?
•  » » 6 years ago, # ^ |   +4 Somewhat. Different topics for different people have different difficulty, so it is impossible to sort a problemset from the easiest to the hardest.
 » 6 years ago, # | ← Rev. 2 →   0 Hope to have Some Nice, Short & Easy to Understandable Problem Statement . Because A short & well understandable Problem Statement can make a sense of a Nice and Quick solutions .It would be better if you set the Problems according to their Difficulty Order .
•  » » 6 years ago, # ^ |   +3 for sure.
 » 6 years ago, # |   -13 I hope it will be interesting, thanks for the round :)
 » 6 years ago, # |   +5 I want to mention about competition time. When the organizers set time 18:00 MSK, our local times shows 17:00 which is our end of the business day. I know there is no chance to set for every country, but I just want to tell you :( sad story.
 » 6 years ago, # |   +3 Is there any way to get benefit from the Youtube's channel for non Russian speakers > ?
•  » » 6 years ago, # ^ |   +2 Probably only if someone will volunteer to translate.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 If someone can make English subtitles for the videos, it could be of great help.
 » 6 years ago, # |   -13 Currently I have my mid semester exams but I will take part in this contest ..
•  » » 6 years ago, # ^ |   0 Same here! 18,19 and 20, and all three codeforces round are one these dates. :D
 » 6 years ago, # |   +11 Word "Education Round" without Edvard ... :)
•  » » 6 years ago, # ^ |   +3 And word "Education" instead "Educational".
•  » » 6 years ago, # ^ |   +5 I'll post the announcement of the Educational Round 8 soon :)
•  » » » 6 years ago, # ^ |   0 great :) your awesome man...
 » 6 years ago, # |   0 So interesting for me,but per questions only 10mins hahahahahaha I don't think I have enough time to read and code these problems!
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 thanks a lot for your kind help :)
 » 6 years ago, # |   0 Hope that it is going to be a good 10 mins per problem contest filled with just import things from using the Wikipedia, google and OEIS library ;)
•  » » 6 years ago, # ^ |   0 How do people use oeis libraries in code? I have heard people who "use" oeis, but I have no idea how.
•  » » » 6 years ago, # ^ |   0 Using oeis as in referring to oeis during contest.
•  » » » » 6 years ago, # ^ |   0 Well it sure comes in handy if you're really stuck.
 » 6 years ago, # |   0 bazar jok.
 » 6 years ago, # |   -32 10 minutes per question
 » 6 years ago, # |   +24 Никто не заметил, то что контест начинается 18 февраля в 18:00, 18 задач и дается 180 минут?
 » 6 years ago, # |   0 mfv Is only Java allowed or any other languages allowed in normal round are also allowed because tutorial videos was focused on Java?
•  » » 6 years ago, # ^ |   0 Any language is allowed.
 » 6 years ago, # |   +35 Bannedaccount is a bot who is slowing queue.
•  » » 6 years ago, # ^ |   +1 MikeMirzayanov , any comments ?
 » 6 years ago, # |   0 Too many time :) More than hour before the end, but already 11 people solved everything.
•  » » 6 years ago, # ^ |   +6 It was designed for div2, not for red ones.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +13 Not blaming anyone, just joking/showing off :) Actually in my opinion it will be very cool to have similar contest with div1 difficulty.
•  » » » » 6 years ago, # ^ |   +24 just do it :-)
 » 6 years ago, # |   0 Got L accepted 20s to the end of the round
 » 6 years ago, # |   +16
 » 6 years ago, # |   +110 I think that the difficulty was perfect was such a contest. Somebody above said that there was too much time — because 11 people solved everything in two hours. In my opinion it was fine and the contest shouldn't be harder.Problem Q (Pyramids) was funny for me. I calculated formulas for the first two pyramids and then I used the answer from sample to calculate the coefficient for the third pyramid. I guess it was intended but still very unusual.WA in test #22 in E (Rectangle with hexagonal cells). Here I will complain a bit. For me, the main problem was to understand the problem. For more than one hour I thought that one cell has the center in point (0, 0). It wasn't true and my solution gave WA on #22. Standings show that I wasn't the only one, Organizers, in my opinion you shouldn't put a misleading drawing in the statement. Drawings were awesome in e.g. problems P and Q. But here, you gave drawing to one of two cases — the one showed in the sample. Why wasn't it in the sample explanation section? I know that in problem P a drawing was related to the sample too, but the number of points n was the main part of the problem there. But here, in E, the drawing suggested that particular arrangement of cells. For sure I'm biased because I couldn't get AC for much time. Does anybody agree with me or was everything ok there?
•  » » 6 years ago, # ^ |   0 Problemsetter's solutions use function with parameter n (3,4,5). It can be a part of the formula.
•  » » 6 years ago, # ^ |   0 From the results it looks like that a lot of people googled formula for Q. In other case it's hard to explain why Q has more AC than O (last one is way simpler IMHO).
•  » » » 6 years ago, # ^ |   0 I faced to problem of preciion. Initialized points, assuming "center" of arrow as (0, 0), multiplication by rotate matrix and transposition. Still don't know where's fail
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I don't think it's precision issue. Looks like you need to change (c — a) to just c everywhere.
•  » » » » » 6 years ago, # ^ |   0 My holy pretty f**cking stupid bad!!:D 40 minutes couldn't understand my failure!)
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 By the way, word of advice: use std::complex for 2D geometry. Makes thing that much simpler.
•  » » » » » » » 6 years ago, # ^ |   0 Thanks for advise. Never used it.
•  » » » 6 years ago, # ^ |   0 I did google for formula in Q. At first I tried with (1/3) for all (out of assumption, assuming from the formula of cone). Then when the answers did not match, I had to google.
•  » » 6 years ago, # ^ |   -8 Why a drawing should describe all possible cases? It depicts one test.
•  » » » 6 years ago, # ^ |   +34 No, it doesn't have to cover all cases.Reading about hexagonal cells is very hard. Usually problems are much easier to understand and thus they don't require drawings. But here, drawing was crucial and likely almost all contestants used it to understand how coordinates work. It was in the main statement, not in the sample explanation. It wasn't said that it's the sample arrangement. So why shouldn't I assume that coordinates are like in the provided drawing?
•  » » » » 6 years ago, # ^ |   +42 It should have been in sample explanation. Sorry.
•  » » » » » 6 years ago, # ^ |   +50 Still, only 1 issue in 18 problems. It was damn well prepared contest! Thanks.
•  » » 6 years ago, # ^ |   0 I looked at diagram and vaguely read the problem statement. Helped me avoid confusion for this problem.
•  » » 6 years ago, # ^ |   +8 Wait... how come there is no cell centered in (0, 0)? There is a hole on the grid? It makes no sense to me.I am one of the people who can't get past test 22 and I'm pretty sure my solution is overflow-free.
•  » » » 6 years ago, # ^ |   +13 Apparently you could shift the whole "hexagon plane" a bit, so the centers are in cells like (1;0), (3;0) ... You should be oriented in which case you are by the input data, since it's apparently centers of cells only.
•  » » » » 6 years ago, # ^ |   +32 I always feel cheated when I find out that a cruical part of the problem was hidden in the input format rather than the statement itself.
•  » » » 6 years ago, # ^ |   +15 There is no hole but it's possible that centers are in (1, 0), (0, 1), (2, 1), ( - 1, 0), etc. (instead of (0, 0), (1, 1), (2, 0), ...).
•  » » » » 6 years ago, # ^ |   +13 Ok, thank you, now I get it, but I still don't see how could I have imagined that, at least from the English statement =p
•  » » 6 years ago, # ^ |   +29 Totally agreeing on problem E with you. Took me 8 wrong submits and an hour to get it accepted, and I wouldn't have understood my mistake if I hadn't read your other comment. Not very nice to put misleading pictures especially when the statement wasn't clear enough, in my opinion.Most of the other problems were nicely done though.
•  » » 6 years ago, # ^ |   +13 So according to you, there may be two arrangements for the hexagon? How can I get that from problem statement? I also got WA on 22 and not still understanding where the problem is . And if there are two arrangements which one should I produce output for?
•  » » » 6 years ago, # ^ |   0 I believe input data is supposed to be centers of cells only, but I'm not sure since the statement is confusing. I got AC assuming that, though, after 8 unsuccessful submits.
•  » » » » 6 years ago, # ^ |   0 "input data is supposed to be centers of cells only" This can't be true. Otherwise, how will you construct the cells for input "0 0 2 1"? It could be true though, if we had additional restriction like "It is guaranteed that difference y2 - y1 is divisible by 2"
•  » » » » » 6 years ago, # ^ |   +5 "0 0 2 1" isn't valid. It was guaranteed that the given four numbers represent "the coordinates of the centers of two cells.". Yes, it implied that y2 - y1 is divisible by 2.
•  » » » » » » 6 years ago, # ^ |   0 Oh , now I get it. It's written in the input statement. I had given too much emphasis on the drawing and did not read other statements very well.Well, I agree that the statement could have been written a little better. But in the end, I think its my fault I didn't read the statement thoroughly. This should act as a reminder
•  » » » » » 6 years ago, # ^ |   +23 Well they just didn't have such input. After my previous comment I actually found it written in the input section — "...the coordinates of the centers of two cells."
•  » » » » » » 6 years ago, # ^ |   0 Now I can see it too. Thanks!
•  » » 6 years ago, # ^ |   +5 Agree with you on E. Test case #22: 1 0 5 6 Expected result is 18."Orthogonal coordinates system is set up so that ..." It seems there are 2 ways to set up such system: one with (0,0), another one with (0,1). (0,1)-way gives the answer 18, (0,0)-way gives the answer 17.Please correct me if I am wrong.
•  » » » 6 years ago, # ^ |   0 My solution failed on that test too . centers could be shifted so it is not necessary that (0,0) is a center . (x1,y1) should be a center so you have to shift centers to achieve that. if(x1%2 != y1%2 ) x1++,x2++ ;
 » 6 years ago, # | ← Rev. 3 →   -6 For all those failing 22nd test in E: You can't just calculate (x2 — x1) * (y2 — y1). It will overflow even if you work with signed 64-bit ints (as possible value is 2 * 10^9 * 2 * 10^9 = 4 * 10^18 > 2^63).Disregard everything above, I was wrong.
•  » » 6 years ago, # ^ |   +5 test 22 is not integer overflow. 2^63 > 8 * 10^18.
•  » » » 6 years ago, # ^ |   +5 Thanks. My fault.
•  » » 6 years ago, # ^ |   +20 It's not true that 4·1018 > 263. I think that the reason for WA was to assume that (0, 0) is center of some cell. It wasn't true. So, misunderstanding the statement.
•  » » 6 years ago, # ^ |   +10 Actually 263 is about 9 * 1018 so I believe you're wrong.
 » 6 years ago, # |   +5 The first problem could be rephrased just to: "Output 25".
•  » » 6 years ago, # ^ |   0 cap
•  » » 6 years ago, # ^ |   +53 No, because people like me had fun with coding fast exponentiation.
 » 6 years ago, # |   0 One ER after another. Wowie!!!!
 » 6 years ago, # |   0 Can anyone help me in Problem B? I tried this code https://ideone.com/lgG2Tf I don't get it why my code is approximating the values?
•  » » 6 years ago, # ^ |   +1 For big doubles, ouputting them via cout can lead to results like 1.23456e20. Try to do cout << setprecision(7) << fixed << answer;
 » 6 years ago, # |   0 Hi! I think most of the problems were obvious! Maybe it doesn't help me to improve much, but actually it was a good collection of implementation! Thank you for the contest but I think it could be a lot better. :)
•  » » 6 years ago, # ^ |   +26 I don't mean to sound offensive but you solved 8/18, and the competition was anyway targeted at "beginners and Div. 2 members", so I think the problems' difficulty was fine, for their format at least.
 » 6 years ago, # |   0 First hour really tried to solve problems without loops and conditions. But N...
•  » » 6 years ago, # ^ |   0 You were supposed to use Math.min and Math.max
•  » » » 6 years ago, # ^ |   0 ooooppssss....
 » 6 years ago, # |   +25 I strongly doubt if the problem E is right or its data. See the test data 22 , it is obvious that the answer is 17 which is shown as 18;
•  » » 6 years ago, # ^ |   +1 The grid doesn't always look like the one in a drawing. Read the comments above.
 » 6 years ago, # |   +8 great contest, i hope to see lots of this kind :)
 » 6 years ago, # |   +6 Hi guys, you can now register for tomorrow's contest. This week is just beautiful. Contest after contest. :)
 » 6 years ago, # |   0 it was a exiciting contest :D
 » 6 years ago, # | ← Rev. 2 →   +9 my solution for problem E failed on this test 1 0 5 6 . jury's answer is 18 , my answer is 17 . submission : 16183842 . I can't count the 18 cells , does solution of judge gives wrong :\ ?
•  » » 6 years ago, # ^ |   +5 Read Errichto's and others' comments above. The grid doesn't always look as the one in the picture.
•  » » » 6 years ago, # ^ |   0 sorry , I didn't read the above comments . even during contest I didn't read the problem statement of this problem :v . I think I learned from this contest that I should read problem statement carefully next time :D
 » 6 years ago, # | ← Rev. 3 →   +5 It was a great and interesting contest, except I falled into an unexcepted gotcha.I'm a MS C# user.I kept getting Wrong answer on test 1 on problem B. 16148846I was totally confused and I put it aside. I passed it by rewriting my solution using Math.Pow.After the contest, I checked the record, and I was surprised to find that the dot became comma!OMG! I made a little change and I pass this one now. 16183742The culture differences sometimes can drive people mad (well, and sad).@MikeMirzayanov is there any way to fix this problem? Thanks a lot. (It's OK if C# users had to be careful for the following contests.)
 » 6 years ago, # |   0 I have submit problem E but in test 22 it turns out with WA. but when i saw test 22, i realized that my output number is correct and the correct output is 17 not 18
•  » » 6 years ago, # ^ |   +6 Refer to the tons of comments about it above, especially Errichto's — the grid doesn't always look as the one in the picture.(I wonder how many times I'll have to respond with such comment today)
 » 6 years ago, # | ← Rev. 2 →   +5 Are you going to write editorial?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes. Probably in two parts. It is in the process.
•  » » » 6 years ago, # ^ |   0 Thank you, I will really appreciate it. I am very keen on learning math.
 » 6 years ago, # |   +19 Isn't it the most pythonic round ever hold? :)
 » 6 years ago, # |   +45 The problem D — Hexagons! has the exactly same concept as SPOJ problem BEENUMS.http://www.spoj.com/problems/BEENUMS/It can directly be done by hit-n-trial(Approach 1). I have 2 interesting geometrical proofs/derivation for the end result.2nd Approach — 3rd Approach -
•  » » 6 years ago, # ^ |   +13 4th approach: find formula on OEIS.
•  » » » 6 years ago, # ^ |   +37 Or simply notice that the outer-layer of a hive of size N has 6 sides of length N, with 6 corner cells being in two sides and therefore you get 6*(N-1) for the outer layer in total. Then 6*1+6*2+6*3... is simply 6*(1+2+3...) = 6*(N*(N+1))/2 for a full hive (also add 1 for center cell).No need for anything complicated really.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 Sometimes, the journey teaches more than the end :) ! More so in an educational round :D ! That was the purpose of sharing the approaches. I myself had done it by pattern finding at the first place. And one more thing — in the SPOJ problem, the diagram is not given in the question — which becomes really painful to draw from the second layer onwards (12 hexagons, 18, etc).
•  » » 6 years ago, # ^ |   0 I just find a formula Co-Ordinated with Triangular Number 6 * ( n (n+1)/2)
 » 6 years ago, # |   0 I don't know what is wrong with my submission for problem B? It works absolutely fine on Ideone, but shows me WA here on test case 1 itself, with some "bizarre" output. I have absolutely no idea what is going on? Solution : http://codeforces.com/contest/630/submission/16187819Any help will be much appreciated.
•  » » 6 years ago, # ^ |   0 What about casting to double in printf and using f instead of Lf?
•  » » » 6 years ago, # ^ |   0 I tried to resubmit by doing this. The solution passed test case 1. But I still am not able to get as to why did I get such a strange output using Long Double?
•  » » » » 6 years ago, # ^ |   +5 Codeforces is judging on Windows, mingw for gcc complier.by default, it uses msvcrt.dll as c runtime library, which doesn't support %Lf.http://stackoverflow.com/questions/4089174/printf-and-long-doubleto fix that, add #define printf __mingw_printf before your main(), and now you can use %Lf happily
 » 6 years ago, # |   0 Why does this fail?http://codeforces.com/contest/630/submission/16189060
•  » » 6 years ago, # ^ |   0 Because you used vector of size 2 pushing two additional elements, which makes it vector of size 4 ;-)
 » 6 years ago, # |   0 How can i solve the problem "Q"? Please explain it. Thanks in advance.
•  » » 6 years ago, # ^ |   0 use math formulas
 » 6 years ago, # |   0 In problem E, Test case 22: 1 0 5 6Why is the answer 18?According to the figure the count is coming out to be 17.
•  » » 6 years ago, # ^ |   +5 see my comment here : comment
 » 6 years ago, # |   0 How to solve problem P ?
•  » » 6 years ago, # ^ |   +22 The goal is to calculate the area of red polygon below (the left drawing below), and multiply it by n. So, finding coordinates of four red points will be enough.One point is in the middle of the circle. We can assume its coordinates are (0, 0). One point on the circle can be (0, r) and the neighbouring one must be rotated by angle .But how to find the last point, the one lying on the intersection of two diagonals? Maybe it can be done easier but I found diagonals and then computed the intersection of two lines. To find diagonals we must get coordinates of green points from the second drawing below. It can be done by rotating vector (0, r) by something like and . My submission: 16168847.
•  » » » 6 years ago, # ^ |   +1 I thought of that solution, but I thought there must be a simpler solution than making coordinates and finding intersection point of two segments, and it seems there's actually simpler solutions as some solutions are only cin then cout like this one 16190755thanks anyway
•  » » » » 6 years ago, # ^ | ← Rev. 6 →   +40 Ok, I can prove it. It's not complicated to show that the red triangle below has angles α, 2α, π - 3α where . And side opposite to angle π - 3α has length r. We should use these values to calculate the area of triangle, and multiply it by 2n to get the answer.Let's consider any triangle with sides a, b, c and angles α, β, γ respectively (α opposite to a, β opposite to b, γ opposite to c). There are two very well known formulas: With them we can get:
•  » » » 6 years ago, # ^ |   0 Another (harder) way is to compute area of the white sector-like things and then subtract from the area of the circle.