Привет, Codeforces!
18 февраля 2016 в 18:00 MSK состоится экспериментальный учебный раунд — формульный блиц ВолБИТ «Experimental Educational Round: VolBIT Formulas Blitz». На этот раз набор задач рекомендован для участников из Div.2.
Раунд будет нерейтинговым для всех участников. Соревнование будет проводиться согласно стандартным правилам ACM ICPC. У Вас будет 180 минут (три часа), чтобы решить 18 задач. После раунда не будет фазы взломов.
Наша основная целевая аудитория — начинающие и члены Div. 2. Все предложенные задачи могут быть решены без условий и циклов. Требуются только формулы. Присваивания и функции могут быть использованы для сокращения дублирования кода.
Темы задач:
- комбинаторика
- геометрия
- теория игр
- последовательности
- другое
Раунд подготовлен как часть комплекса мероприятий Вологодский БИТ, также как часть этих мероприятий проходили вебинары «Олимпиадное программирование с нуля на Java», посвящённые перечисленным выше темам. Записи вебинаров доступны на YouTube (на русском).
Раунд был подготовлен мной, Фёдором Меньшиковым mfv, Игорем Андриановым igand и Олегом Стрекаловским OSt. Особая благодарность Марии Беловой Delinur за вычитку и исправление условий на английском и конечно Михаилу Мирзаянову MikeMirzayanov за платформу Codeforces и Полигон. Полигон сделал чекеры и тесты для этого соревнования лучше.
UPD: Разбор задач завершён.
18 problems in 3 hours !!!! this looks challenging (1 problem per 10 mins).. especially in these topics .. can't wait ;)
You are welcome!
1 problem per 10 mins :)
10 minutes is not for coding !! It is for reading, translating, solving and coding :))
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.
Is it PrinceOfPersia's dummy ?
I asked from him ( PrinceOfPersia ) and he said no !
Just his fan
Сertainly, some common functions from standard math libraries can be used.
Yes, particularly
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. :-)
Pl?
Math.PI in Java
Math ,, 1 problem per 10 mins ,, sorry i’m out
it is unrated
i’m in :v
As a beginner, I can't express how excited I'm for this round. This, for sure, is going to be a memorable experience. :)
No, registration required ?
Registration will be open till the end of the contest.
It is good to see codeforces coming up with different types of contests. It really helps a lot.
//not Codeforces:)oeis.org may help in some problems but not required if you know combinatorics.
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.
include
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
solution B
Choose either one will solve your problem.
The contest name should be : Fast as Ferrari !
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.
Я уже привык, что на каждом контесте есть хотя бы одна математическая задача и бесит, когда их еще больше. Но 18... Слава богу, что не рейтинговый)
What do they mean by "this contest is unrated"?
Rating of the round participants will not change.
So ineresting!
interesting
oh.. I'm so careless Haha.
Hope there will be short statements...
Will the problems be sorted from easiest to hardest?
Somewhat. Different topics for different people have different difficulty, so it is impossible to sort a problemset from the easiest to the hardest.
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 .
for sure.
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.
Is there any way to get benefit from the Youtube's channel for non Russian speakers > ?
Probably only if someone will volunteer to translate.
If someone can make English subtitles for the videos, it could be of great help.
Currently I have my mid semester exams but I will take part in this contest ..
Same here! 18,19 and 20, and all three codeforces round are one these dates. :D
Все предложенные задачи могут быть решены без условийУ меня не получается решать без условий. Кажется, всё-таки нужны условия.
я полагаю, что имеются в виду конструкции if () .... Хотя мб это был сарказм)
Word "Education Round" without Edvard ... :)
And word "Education" instead "Educational".
I'll post the announcement of the Educational Round 8 soon :)
great :) your awesome man...
So interesting for me,but per questions only 10mins hahahahahaha I don't think I have enough time to read and code these problems!
Would you please help me by giving some good tutorial link about sequence and combinatorics??
At least
https://en.wikipedia.org/wiki/Combination https://en.wikipedia.org/wiki/Permutation https://en.wikipedia.org/wiki/Partial_permutation https://en.wikipedia.org/wiki/Arithmetic_progression https://en.wikipedia.org/wiki/Geometric_progression
thanks a lot for your kind help :)
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 ;)
How do people use oeis libraries in code? I have heard people who "use" oeis, but I have no idea how.
Using oeis as in referring to oeis during contest.
Well it sure comes in handy if you're really stuck.
10 minutes per question
Никто не заметил, то что контест начинается 18 февраля в 18:00, 18 задач и дается 180 минут?
mfv Is only Java allowed or any other languages allowed in normal round are also allowed because tutorial videos was focused on Java?
Any language is allowed.
Bannedaccount is a bot who is slowing queue.
MikeMirzayanov , any comments ?
Too many time :) More than hour before the end, but already 11 people solved everything.
It was designed for div2, not for red ones.
Not blaming anyone, just joking/showing off :) Actually in my opinion it will be very cool to have similar contest with div1 difficulty.
just do it :-)
Вот зачем сюда пихать длинную арифметику?( Вместо того, чтобы просто написать формулу, приходится думать, как делать деления и умножения вовремя, чтобы тип не переполнился =(
Ну и некоторые задачи гуглятся, а так норм)
У создателей соревнования не было ни одного решения с длинной арифметикой. Всё что нужно можно сделать некоторыми оптимизациями в 64-битном целом типе.
Очень много очень простых задач — отличный формат, если хочется посоревноваться, но не хочется сильно думать :) Я сегодня хорошо провел время, спасибо за контест :)
Спасибо за позитивный отзыв. :-)
Got L accepted 20s to the end of the round
Solutions of all problems if anyone is interested
Острый недостаток правильных решений в крови, срочно нужно принять немного Эдиториала
Эдиториал первых 9 задач будет через часик. Вторых 9 задач через несколько часов.
Хороший контест , хотелось бы побольше таких.
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?
Problemsetter's solutions use function with parameter n (3,4,5). It can be a part of the formula.
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).
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
I don't think it's precision issue. Looks like you need to change (c — a) to just c everywhere.
My holy pretty f**cking stupid bad!!:D
40 minutes couldn't understand my failure!)
By the way, word of advice: use std::complex for 2D geometry. Makes thing that much simpler.
Thanks for advise. Never used it.
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.
Why a drawing should describe all possible cases? It depicts one test.
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?
It should have been in sample explanation. Sorry.
Still, only 1 issue in 18 problems. It was damn well prepared contest! Thanks.
I looked at diagram and vaguely read the problem statement. Helped me avoid confusion for this problem.
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.
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.
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.
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), ...).
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
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.
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?
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.
"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"
"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.
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
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."
Now I can see it too. Thanks!
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.
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++ ;
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.
test 22 is not integer overflow. 2^63 > 8 * 10^18.
Thanks. My fault.
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.
Actually 263 is about 9 * 1018 so I believe you're wrong.
The first problem could be rephrased just to: "Output 25".
cap
No, because people like me had fun with coding fast exponentiation.
One ER after another. Wowie!!!!
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?
For big doubles, ouputting them via cout can lead to results like 1.23456e20. Try to do cout << setprecision(7) << fixed << answer;
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. :)
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.
First hour really tried to solve problems without loops and conditions. But N...
You were supposed to use Math.min and Math.max
ooooppssss....
Либо я не умею считать, либо ответ на 22 тест по Е неверный.
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;
The grid doesn't always look like the one in a drawing. Read the comments above.
great contest, i hope to see lots of this kind :)
Классный раунд, мне понравилось. Спасибо!=)
Hi guys, you can now register for tomorrow's contest. This week is just beautiful. Contest after contest. :)
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 :\ ?
Read Errichto's and others' comments above. The grid doesn't always look as the one in the picture.
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
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. 16148846
I 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. 16183742
The 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.)
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
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)
Задача E.
Ключевая часть "координаты центров двух сот" была вынесена в раздел "Входные данные". В основной части условия было сказано просто "соты с координатами".
И сбивающая с толку "поясняющая" картинка.
WHY? :(
Да, это идиотизм. Я вот могу придраться к условию:
Может сложиться впечатление, что выбор системы координат зависит от выбранного прямоугольника, так как описание выбора системы координат находится сразу после и в одном абзаце с выбором прямоугольника. Поэтому эту часть условия можно перефразировать в:
Это ничему не противоречит. И в таком случае, под это условие не подходит 5 тест:
0 0 2 0, в котором для x = 1 нет не одного шестиугольника, ну или вернее:Вы только представьте, что было бы, окажись подобная "ловушка" на раунде в системных тестах. :)
Are you going to write editorial?
Yes. Probably in two parts. It is in the process.
Thank you, I will really appreciate it. I am very keen on learning math.
Isn't it the most pythonic round ever hold? :)
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 -
4th approach: find formula on OEIS.
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.
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).
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.me/contest/630/submission/16187819
Any help will be much appreciated.
What about casting to double in printf and using f instead of Lf?
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?
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-double
to fix that, add
before your main(), and now you can use %Lf happily
Why does this fail?
http://codeforces.me/contest/630/submission/16189060
Because you used vector of size 2 pushing two additional elements, which makes it vector of size 4 ;-)
How can i solve the problem "Q"? Please explain it. Thanks in advance.
use math formulas
In problem E, Test case 22: 1 0 5 6
Why is the answer 18?
According to the figure the count is coming out to be 17.
see my comment here : comment
How to solve problem P ?
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.
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 16190755
thanks anyway
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:
Another (harder) way is to compute area of the white sector-like things and then subtract from the area of the circle.