Добрый день, Codeforces!
Рад сообщить, что в это воскресенье, 8го ноября в 19:30 MSK состоится Codeforces Round #330 для участников обоих дивизионов.
Задачи для вас уже не в первый раз с удовольствием придумывали и готовили Александр fcspartakm Фролов и я, Данил Сагунов. Мы говорим спасибо координатору Codeforces Глебу GlebsHP Евстропову за существенную помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon, Марии Delinur Беловой за перевод условий на английский язык, а также Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование и прорешивание задач раунда.
Каждому из участников раунда будет предоставлено два часа на решение пяти задач. Мы постарались сделать задачи разнообразными и интересными, и поэтому настоятельно рекомендуем прочитать все задачи во время раунда. Разбалловка, как и всегда, будет объявлена позднее.
Желаем всем удачи и высокого рейтинга!
UPD. Еще раз приносим свои извинения за задачу Cdiv2/Adiv1 — авторское решение неправильно работало в случае нечетных n. Мы очень надеемся, что остальные задачи контеста оказались (или окажутся в дорешивании) для вас полезными и интересными.
В любом случае, хотим поздравить победителей раунда:
Победители первого дивизиона:
победители второго дивизиона:
Разбор задач можно найти здесь.
UPD. Задача Cdiv2/Adiv1 была исправлена, и теперь имеет то условие и решение, которое предполагали авторы. Задача вернулась в соревнование и доступна для дорешивания.
you used to be red :D
You used to be purple :D
It's not funny when it's told to you, isn't it?
No man, I didn't meant that I was joking with him because he said that in his previous round see the first line of this post
http://mirror.codeforces.com/blog/entry/20657
I didn't know that. Sorry.
I like your problems... not too easy not too hard. thank you.
NOT thank you because unrated...
Проверьте ссылки на контест в рассылке, пожалуйста. При нажатии отправляет на Round 326.
Finally we have Div 1 after A long time.
It seems the queue has been empty lately, time to
push():-)queue.pop() :D
I think not. Doesn't the last contest seem like Div1?
We all agree with you :D
Dude !! last contest was almost a Div1 contest !! :P
It will soon be a full month between DIV I rated contests. Has that ever happened before?
the link for registration (in the email) has a problem I think!! it's not important I just wanted you to know. :) that's it: http://mirror.codeforces.com/contests/587,588
Thanks for your contest!
The comment is hidden because of too negative feedback, click here to view it
You can't trick russians that way :P
You could've made here as a link to your comment.
The links in my email seemed to be incorrect.I clicked
Codeforces Round 330,but it went to http://mirror.codeforces.com/contests/587,588"We wish good luck and high rating to everyone!". I may have believed that a week ago, but after explaining how the rating works it is clear high rating to everyone is impossible.
Почему никто никогда не напишет "настоятельно рекомендуем не читать все задачи". Всем бы стало интересно — "а почему?", и они бы пошли читать =)
That is my time to be purple.Ok gays! if you want to have a good luck and increase your rating please thumb up me, and you will be lucky!
gays? :|
Last contest before regional Acm Icpc 2015.
Good luck and have fun!
KEYBOARD WARRIOR !
how can i register for the todays contest round#330 (div.1)?
hack a div 1 account :P
Only Div 1 contestants can register for Div 1 contests.
New contestants are only allowed to div. 2 contests. Once you have managed to gain a rating of >= 1900, you are allowed to to enter div. 1 contests.
So simply join a few div. 2 contests. If your're an excellent programmer you'll be in div. 1 in no time.
You're missing 12 more red figures
hope this would be my last div2 contest :D
ha-ha:D welcome again!
thanks :D :P
I can't take this contest because of school exam :( !
life is not fair !
I can't take school exam because of codeforces contest :D
Life is fair!
I dream your life! ;D
i cant do my homework for codeforces contest
and ... fair unfair i dont now
Scoring will be announced later.....ammmm maybe after the contest :D
Where is scoring distribution??
today's contest also seem's like div1 contest..... how we solve ????
Well , this time it's not so hard (at least as last round). :D. But i don't say it's easy too.
"Div 2 problems" ...
These kind of problemsets are a disaster! Such an easy A, then relatively much harder problems. Why did you wish us high rating? You knew that's a a lie.
Nope B is ok.
Try to solve C then!!! :|
I am trying. :) I am weak in game theory and i have solved C only one time before.
Crap :( Unrated round.
So, round is unrated!! Let's discuss solutions before they cahnge their mind :D
why this hard contests ??? is there a revolution in the divisions ??? :_( please a div2 usual contest !!!
I guess there should be Div. 3 contests, if Div. 2 continues being so hard.
Div. 0 contest :)
What terrible problems... perfect round to make unrated.
I think problem Div1A is really nice.
I was confused by the statement, but it seemed like a nice problem. Take a look at Div2/B though — absolute nightmare.
If i did it then it's definitely easy! :P
You must wait for systests before claiming you did it. By the way, how did you do it? I thought 10^8 might not be correct complexity.
You didn't do it right, though. 14152835
Yea :P. Now it's right after checking one more corner case a_i = 1 and b_i = 0.
ахахахах, смешно ......
ну едрить кудрить
Unrated round >.<
в кой это веки CF уж точно не будет лагать под конец))
Не угадал.
Why UNRATED contest because of one problem ??? This time I solved 2 problems and they did this.
this is wrong! just do not count the C part! but why it has to be unrated?
Simply not counting the problem wouldn't be fair to the people who spent a lot of time on it.
are u fucking serious? well imagine someone spent a lot of time for C, solved it and then BAM 'time well spent'. yea great idea
Высокого рейтинга желаю :)
After long time i was going to get under 1k rank and now it's unrated! :( Well now i am waiting next contest. :D
"Unfortunately, we are too tell" — the english is stronK in this one :)
Think first, what would be your situation while getting such type of pressure! Can you think yourself in the place of authors?
It's funny though isn't it? :). Btw these last 2 rounds reminded me why i stopped competing on codeforces long ago... Nothing has changed, hard to understand statements and problems not suitable for div2.
a unrated round after 1:30 hours. really?
Think about the chances of finding out that your model solution is wrong. There's only one: a contestant raises a valid question.
Of course, realising that it's not your solution that's wrong (as a contestant), but a model solution, requires actually writing something that passes pretests — and not moving on to the next problem. How many people would do that? In addition, it requires realising that what you submitted is totally wrong. That makes the chances even lower.
It requires a lot of coincidences. 1:30 can even be quite early, I'd rather expect the error to be found in comments after the round.
Why didn't authors stress their model solution against n·2n solution?
Maybe they did, but the small test data weren't strong enough?
What makes you think the smallest counter example is small enough for that algorithm to be feasible?
Looks very reasonable that the minimal counter example has the length <= 20.
I agree, but my point is that you can't hypothesize that they did not stress-test their solution when you have no idea what the counter example looks like.
This is the right question. I modeled that the task is unsolvable with any greedy algorithm that I came up with using my minimax bruteforce solution as a etalon and a couple of hard test cases, but still was trying to find some "quirk", because didn't even consider a possibility of a wrong problem.
Why didn't authors did it...
You the contestant.
Well, perhaps that explains why I found Div1A to be so hard...
An unproven greedy strategy can mess up your codeforces round :p
That's why I recommend the authors to discuss the solution with me before the contest starts! ;)
ZLOBOBER COME BACK PLZ!!!
this is the second bad contest of new coordinator. (just two good rounds) :( UPD : sorry GlebsHP
Please Zlobober
Best of the best of the best : Zlobober
In a few rounds, new coordinator gonna quit :(
replying your own comments ?
I didn't know that a rule "Cannot reply your own comment", Thanks for the Tip :)
there is no rule. It just seems like you are schizophrenics :( (nice image by the way)
No, it just makes you look like a noob that doesn't know what the "edit" button does.
Please be polite and patient. First contests are the hardest ones, mine first days were also very nervous, sometimes I've been really close to have an unrated round.
What you do is the worst possible action. Haters' comments like yours only increase the pressure, and make harder for everybody to hold a normal round. Just imagine how stressed will be the next contest authors. So please show some respect to the platform and to GlebsHP and be patient.
+1 to Zlobober. This failure is also our failure as well. We didn't notice that on the presolving stage of the contest, so whoever wants to speak bad about new coordinator feel free to equally share your rage between all of us. More of that, working with GlebsHP is very nice. We will try to be more thoughtful next time and do our best to avoid these mistakes. Shit happens :(
In Hong Kong, I am doing this contest in MID-NIGHT and at the morning I need to go to school. And I still participate because I want my rating increase. Now this round is unrated... Really?
do this contest in MID-NIGHT too
next time you ought to participate for contest, not for rating, and you will not upset :)
What do you mean by this?
"We wish good luck and high rating to everyone!" ha? Could have become top10 if rated. Why not be rated for a part of the contestants?
Dude, clam down. If you deserve it, you'll get it in the next contest. Be patient ;)
Aw.. I solved (Div 1) D, was hoping for a lot of points. But I understand that making the round unrated is the right thing to do.
I'm so sorry!!!
Same here :/
Если у меня прошли претесты на задаче С в див2, то я 100% не правильно решил?
Распиши алгоритм, толпой скинемся на контр-кейс
1) Сходить все ходы первого игрока: отъедаем заданное количество точек с краев, минимизируя максимальное расстояние между оставшимися точками
2) Сходить все ходы второго игрока: съесть все точки кроме крайних
Это неправильно?
And now this contest is unrated :(
Now that problem C is removed, did anyone find something wrong with the logic behind explanation of test case 2? It doesn't seem right to me somehow :(
test 2 was ok i guess
Good time to practice hacking.
I wish it was still rated. Those who solved Div 2 A and B quickly will lose out on good rating :(
rating is not everything, nor should it be the only motivation to code. just got swayed by emotion after the announcement so yes the decision should be fair to everyone :)
plus the round writers have worked hard for this and they must have felt bad too. anyway, waiting for the editorials :)
Почему нельзя все-таки оставить контест рейтинговым, просто не учитывая баллы за задачу C?
потому что это нечестно по отношению к тем кто решил или пытался решить С, потратив на нее уйму времени!
Seriously, round unrated!!!!, i can't believe it, after 1:30 hours in competition, this is a disaster[contest:330]!!!
wtf! cf had a lot of cool contests in these years!! how many of them gon wrong? NONE!! lets forget this brown day and v8 4 more cool contests.. and by the way, your a NewBie, just thank cf and fuc*OFF :D
this is not fare! make it rated!
Fare??
Does the model solution fail on this test by any chance?
Ah, so this is the countertest?
I was a bit confused since things change a lot as the game progresses. During the contest, the first thing I came up with was apparently the same as the model solution, but I also had this countertest and got stumped and gave up. I proceeded to pass pretests on D and C (with some trouble).
I guess I still haven't solved D in an official contest then... I still learned some stuff I guess :D. Lessons: deques and queues have a much larger memory overhead than vectors. return printf("1\n") works locally but not on CF. Sometimes things that seem too hard actually are XD
What would the optimal solution for both players be? I'm not sure what they mean by "optimal" by both players.
The solution here should be 1.
Answer is presumably 1; the first player will remove 5 (or 1, whatever), then whatever the second player removes the first player will be able to get a result of 1 (e.g. if the second guy chooses 2, then the first guy would choose 1). Similar thing with the case I was trying to figure out how to deal with:
The point being that both players have a ton of on-the-fly adjustments they can make.
Thst is the hack!
Congratulation !
What is special about this case? I couldn't come up with any solution (not even remotely close), so I'm not really sure.
Are you using a set by any chance?
So if this is actually the counterexample then I guess the offical solution was saying "ok, we can let the first guy do all his turns first" (i.e. you want max(arr[n-1-turns+i]-arr[i]) where turns=ceil((n-2)/2) is the number of turns the first guy gets) or something similar.
If it's in main(), you can use return printf("1\n"), 0;
By convention, main() should return zero on success.
Yeah I know that. I always do it with the 0 but today I forgot and it still worked locally -> learned to check that.
Were all the solutions of participants incorrect, too?
Maybe solutions which passed pretests are false, but solutions which fails pretest are true? :D:D
a black day for codeforces ...... (mabye brown)
Все жду, да никак не дождусь контеста по химии.
I assume we are free to discuss solutions if it is unrated.
How to find the count of integers which start with b[i] and are divisable by a[i] in some range [a[i],pow(10,k + 1) -1] ? Anyone can help here please??? :)
I assume we shouldn't brute force, there should be an elegant solution to this.
My idea for B is : count possible numbers for each of the n/k positions. then answer is the product of the (1 + count of possible numbers) for 1 <= n/k
A tip for the problem setter : It's better to say "If ... start 'WITH' instead of 'FROM'
Find lower bound -> 'from' if divisible, from + (x — from % x) if not. Then find upper bound which is simply (to / x) * x. Now the number of divisors is (to — from) / x + 1
Another terribly contest! The idea of tasks ( first four tasks are great ), but guys:
The tasks are pretty hard for div 2 round.
The fourth task again some physics ?!
Bug in the third task, I am really interested what it is. I can not understand that two purple, one orange and two red coders didn't find mistake in the problem.
Why I can not hack solutions with smaller matrix size than it is needed in the first task( many users put matrix [100][100] instead of [100][200])?
4th task is not physics, point on circle can be described in terms of coordinates of circle-centre and angle (and angle depends only on time)
the same at 4
>physics
I don't think this word means what you think it means. A cycloid is a mathemathical curve; while I see a lot of analogies with physics, they didn't help at all and I solved it as a purely programming problem.
You're given an implicit relation between something proportional to the answer, t (the answer is tV / R) and some parameter p which you can freely change: φ(t, p) = R(t + sin(p) - sin(p + t)) - L = 0. Find the minimum t.
Binary-search. Since t - sin(p + t) is non-decreasing in t for any p, if φ(t0, p) ≥ 0 for some p, then the min. t is at most t0; otherwise, it's more than t0. For fixed t0, sin(p) - sin(p + t0) attains all values in the range
, which makes the binary search condition easy to check.
Where's the physics? Though I agree that it's too hard for div1 B.
Problems involving rotational motion like these arise a lot more in physics than in pure mathematics or computer science, and I believe that is where the confusion may have stemmed from.
Ok. I can agree with you. I didn't have full solution for the fourth task and you are right.
The previous round had similar idea for the fourth task. I think physics task, which can be solved by math (geometry) and binary search. For me previous one was more interested.
BTW:
Did anyone has right solution for the C d2 (A d1) task ?
allllekssssa Same happened with me.Someone had made an array of size[107][107]. So I gave n=100,m=100 and gave all the values as 1. Surprisingly, it gave Correct Answer which was 10000.I wrote that contestant's solution on my machine and gave the same input but a miracle happened. It gave 10000 here too. I failed to understand the sorcery:P. So as a last ditch, I put some 0's in between instead of all 1's. The correct answer was 9998 but his program showed 10000. Hacked it with this input and succeeded. But curious to know, what had happened the first time? Shouldn't the code Segfault?
I thought the same. I am not big expert for C++, but I think that program use some extra memory and change size of array.
spent one hour on the C --> :CНаш контест был хотя бы рейтинговый
Вот да
Он хотя бы был без багов
С багами :)
Да хороший у вас был контест. Просто cf не успел выдрессировать пользователей под задачи такого рода, тут другие в ходу. Учить ДО надо вперед HLD, это всякий здесь знает. Но ДО знают очень немногие)
PS Я вот вообще не понимаю, как это возможно — заготовить к моему решению В контртест, чтобы на eps = 1e-6 падало, а на 1e-7 нет)) Там же нормальные люди вообще нипочем даблов использовать бы не стали)
Сколько сложных и незнакомых аббревиатур (ДО, HLD)
Такое чувство, как будто на ЕГЭ пришол
ДО — дерево отрезков, HLD — heavy-light decomposition.
Если отбросить задачи выше Cdiv2 — то от ЕГЭ действительно никаких отличий. А я как раз с той стороны заслонки и говорю.
When you realize that your rating will decrease, but then contest become unrated
The opposite happened to me :(
Vice versa, this is me.
I dont remember last time i was able to solve C (Since last 3 contest).
Please don't make this round unrated , for the first time i solved div1 D during contest
please make this round unrated because div1D gave MLE on #59
Shouldn't contestants decide whether or not they want this round rated? If there was a poll I think many would still prefer for it to be rated. And if more than 80% (or different fraction) of people want it to be rated then it would be. However, now it's too late since probably many have stopped writing and left after announcement.
NOPE, CAUSE ITS SURE GOING TO BE 50-50
Well, at least then you would end up with a feeling that you made right decision by making it unrated contest.
This must be upsetting for coordinators and problem setter too.I think we should support them and have a little faith in them. :)
Agreed, the number of posts saying "I hate you" is too much. Mistakes are bound to happen anywhere, and today's one incorrect model solution is small compared to the thousands of interesting problems that Codeforces has given us.
I can only imagine how much effort it took him to write 8 problems and then only to see the contest to go in vain. Announcing it unrated must have hurt him more than anyone!! If not anything then he gave community 8 new problems to solve!! So less hate comments please
How to solve div2 B ?
Wait.. :)
for each a_i count how many numbers are divisible by a_i in the rang 0 to 10^k-1 . Then find how many of these numbers fall in the range of k-digit numbers starting with b_i . subtract it from previously counted numbers. The multiplications of these numbers for all i is the answer (mod 10^9+7) .
Nice explanation. b_i = 0 was a exception.
I didn't do any extra checking for b_i=0 . I passed the system test. What will be the exception, could you tell?
It depends on method of finding numbers that fall in the range of k-digit numbers starting with b_i. In my method it will give WA for b_i = 0.
Compute the number of possibilities for the i-th group of digits, then the final result is the product of all those possibilities.
To compute the number of possibilities for the i-th group of digits, you can count the number of integers j so that 0 <= j*a_i < b_i*10^(k-1) and add the number of integers j so that (1+b_i)*10^(k-1) <= j*a_i < 10^k.
I hope this is clear :)
so there I was... having solved B (hopefully) , thinking about how I may finally have a 1500+ rating or maybe even get a change of color and bla bla .... suddenly this notification -_-
I am never gonna get a good rating :'(
when do you people have time to make this stuff?
How unlucky can a person be? if you want to find the answer,I say [user:http://mirror.codeforces.com/profile/fsps60312].I didn't see a person that be more unlucky than him/her. :-/
Контест сделали нерейтинговым... А я-то думал, почему я не могу придумать решение на C?
I also wanted to point out that statement + input of Div1C is horrible. Seriously, WHY is the input given in rectangle? Combined with some vector explanation which I couldn't understand, I just stared at the problem statement for about 30 minutes.
Maybe in order to make a reasonable legend.
it's still not
Правда, что авторское выдавало неверный ответ на одном из претестов?
да, это правда.
How unlucky can a person be?if you want to find the answer,it's enough to know who is [user:http://mirror.codeforces.com/profile/fsps60312].I didn't see anyone more unlucky than him/her.
How unlucky can a person be?if you want to find the answer,it's enough to know who is fsps60312.I didn't see anyone more unlucky than him/her.
Если авторское решение работает неправильно на тесте, не включенном в претесты, то почему нельзя оставить контест рейтинговым и переписать авторское, считая, что претесты такими и должны были быть?
А как же взломы?
Значит автор не учёл какой-то вариант. Следовательно тогда будут люди, которые тоже его не учли, а будут и те, которые учли. Тогда они решали разные задачи с разной сложностью => контекст не справедливый.
Эм нет, они решали ту же задачу, просто те кто не учли решили неправильно, но претесты прошли. Все дело только во взломах.
Если вы послали неправильный код и он у вас прошел претесты, очевидно, что это дезинформация участника. Как минимум поэтому нечестно
Очень часто бывает так, что неправильный код проходит претесты.
И вообще считается, что слишком сильные претесты — это плохо
На то они и претесты
Просто, вполне возможно, что при правильном понимании условия задача или нерешаемая, или не на 1500 балов (Например я не знаю как отловить случай n= 5 a = {1 2 3 4 5} Ответ: 1. Если знаешь, расскажи
кстати, судя по всему, что ее вообще исключили, даже из дорешки, задача некорректна
Минимакс отлавливает всё, только вот не с 2 <= N <= 200000 за 2 секунды.
Хмммм... Мое решение дает ответ 1, но оно не проходило претесты...
Во-первых, если решение проходит один тест(пусть и с подвохом), это не значит, что решение правильное :)
А, во-вторых, как я понимаю, авторы подразумевали тут ответ 2
Разве не оптимально воину вначале стереть 3, так как дальше как бы лучник не ходил, в конце расстояние останется 1.
Кодфорс чет скатился
what is the hack for div1 A?
I'm still confused by problem C. Is it asking 'given n points, remove k of them and make the smallest rectangle which encloses them'? Why are the magnets described as rectangles, then?
just for lulz
Yes. Probably because magnets are rectangle in real-life.
Can you please explain in a detailed way what modeled solution was and why it's wrong? Because I was really sure about my solution for Div1A.
Can you describe your solution?
I guess everybody printed the minimum value of a[i + N / 2] — a[i] in sorted order :))I'm not sure at all about this solution but I hate the fact that in the latest contests div1A is much harder than some other problem or div1B is very strange and mathemtics problem. D was pretty ok, C also(even though that the task description was very ambiguous
Consider the follow case:
Printing out
a[i + N / 2] - a[i]will get wrong as the answer should be 1 instead of 2.The first step is to ban 5, and if the second ban is 2 (or 3), just ban 1 (or 4). And it is easy to see that banning 1 or 4 in the second ban will get the result of 1 as well. (reverse the banning if the first ban is 1)
I got with a greedy/bruteForce solution, after you sort the set, in the optimal game the first player will move just in corner sides. So he with (n — 1)/2 turns needs to maximize some distance from the preffix set and from its suffix, the remainder distance after to maximize will be the answer.
code: linkYour text to link here... Does any one have a counter example of this??
Same as the case mentioned above(?)
Input this case to your solution gives 2 while the answer should be 1:
What about this one http://pastebin.com/fmV6DTvw ? I didn't manage to submit during the round because it disappeared after some time.
In the case:
your program gives 31 while the answer should be 6? I wrote this solution in time complexity of O(n!) and this should be correct.
The possible first bans will give the following results: (so the first guy should ban 100)
1: 31 (as the second guy should ban 130)
7: 31 (as the second guy should ban 130)
100: 6 (as the second guy should ban 130)
130: 31 (as the second guy should ban 7)
131: 30 (as the second guy should ban 7)
the n should be even
Why?
How to solve problem D?
If the wheel moves n meters then the pin moves n meters around the circle. Reduce this movement to an angle alfa between 0 and 180 degrees. this is how much the pin moves from start to finish. You want to maximize the distance in the x-axis made by this angle. This turns out to be 2*(alfa/2)*r. So the answer is tentatively n-2*(alfa/2)*r divided by speed. But notice that this implies we moved less than n meters, so alfa is actually smaller than before. Just plug in the new values and do the same process. If you do this enough times you will be really close the the real answer.
Nevermind, that won't work. It times out on test 3. I found a new method with binary six that gets me all the way to test 8, but then it becomes unable to reach sufficient precision.
Didn't have the time to pass send to the pretests but this works at least for test 1 : I used the equation of a cycloid. x(t)=r*(v*t/r — sin(v*t/r)) Then I use ternary search on d between 0 and r*pi with the start at x=d and the finish at s=d+(f-s).
To compute the function to minimize (tfi-tsi), I have a solver that uses binary search.
UPD : sorry, WA 4, not precise enough apprently, maybe its just a wrong implementation I don't know.
:/
Give me back my up vote :/
come and get it! (بیا بگیرش)!
wait... I'll come for you tonight ;)
How to do Div2C?
just a bad contest...
why do you write comments in your stupid language when every one here are from different nationalities!!!
do not be rude.
This comment has been deleted cause of technical reasons :/
You are stupid more.
You can be more polite.
he is stupid for doing that but you cant say any thing you want to this language
Unfortunately, we are too tell, that there was a mistake in a model solution for problem C. We will remove the problem from the round and the round will be UNRATED. We sincerely apologize for this happening.
UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED
do you see UNRATED?
How to solve problem Div1 D (REQ)? There are 168 primes up to 1e3.
There are 78498 primes up to 1e6.
For 168 primes we can build Segmet Tree. But what do for others?
I have N * sqrt (N) * some constant around 7(maximum number of primes in the decomposition of a number smaller than 10 ^ 6)
does it run in time limit?
According to his submission history, his solution ran in 2979 ms (barely below the 3s limit). I implemented the same thing (but with more overhead since I used prewritten code) and received TLE on pretest 9 (test 30, after some optimizations).
There was an announcement in the beginning of the contest about the time limit being changed (presumably increased) to 3 seconds, but I'm still unsure about whether this solution was intended to pass. I think the time limit should either have been stricter (to avoid these solutions) or more tolerant (to make optimization of constant factors unnecessary).
I just spent 30mins optimizing my solution and it finally passed. I had to change my factorization from O(sqrtU) to O(number - of - primes - below - sqrtU) which is just ridiculous. My guess is that constant optimizations like these weren't intended, and the time limit is just still too strict.
UPD: Maybe we were supposed to factorize numbers in O(logU) using smallest prime table, like TimonKnigge suggested. That seems more reasonable.
I actually precomputed the first prime factor and the next divisor of each number in times
and O(U), respectively, but nonetheless received TLE on test 30.
I won't try to optimize this solution since I now know that a better one exists, but I guess optimizing my implementation of Mo's algorithm would make it pass, too.
My theory was that the segment tree solution (which I referred to as "my solution", I wasn't specific enough, my bad) in pair with first prime factor optimization is the intended solution and shouldn't ever TLE.
Using prime factor optimization on Mo's (like you did) proves nothing since the dominant complexity is still
. On the other hand, using it on the segment tree solution removes the square root factor completely.
Oh, I see that now, sorry.
I only commented about precomputing the next divisor (as opposed to repeatedly computing it every time), though, because it would have slightly improved the complexity from
to 
, where p(x) ≤ 7 is the number of prime factors in x — and this seemed to be important for geniucos's Mo-based solution to pass. Of course, the specific amount of time spent during precomputation doesn't really matter, since the bottleneck lies elsewhere.
my solution didn't pass system test with such complexity
I had 2979 ms out of 3000=))))Try to optimize small stuff
Good =)
What did you do?
Mine is MO's algorithm + modular inverse + the fact that:
phi(x) = x * P(1 — 1/div) -> where div is each unique divisor and P() is product.
Note that phi(range)=prod(range)*{(p-1)/p for all p such that p divides at least one number in the range}. This is like DQUERY on spoj, since we want to know if a prime occurs 0, or >0 times. Use a BIT with multiplication. If sort the queries offline, and sweep over the left endpoint l, and for each prime multiply a[i]*(p-1)/p where i is the first occurrence of p>=l, we can solve the problem in
Note:
where pi are the prime divisors of n. I stored the ai in a segment tree so I could query their product quickly.
Next, notice that each number up to 1e6 has much less than
primefactors, which is about 20. So, for each ai, store its prime divisors, and for each prime divisor, store the next number to the left that also has this prime divisor. Then, for each number ai that has a prime divisor p such that ai is the first number with prime factor p, multiply segmenttree[i] with (p - 1) * p - 1.
Then sort all queries by left end points in increasing order, and simply query the segment tree for the answer, and whenever the left end point leaves some position i, for each prime factor p of ai, find the next occurrence of p, say position j > i, and multiply segmenttree[j] with (p - 1) * p - 1.
Complexity: calculating the smallest prime divisor of all numbers upto 1e6 is
for U the upperbound on the ai, then factoring each number and maintaining the next occurence of each prime is 
, sorting all queries is O(Q) (for each position you can just store all queries with a left end point on that position), and lastly, updating the segment tree for each left end point is 
, resulting in the beautiful complexity:
Accepted submission: 14153688
my persistent segtree gave MLE on #59 and MO's algo gave TLE on #30 , idk what should i do
.
На самом деле задача Div.1 A мне понравилась, было интересно её решать. Так что в любом случае спасибо авторам за раунд :)
4 клара на четыре задачи в первом диве. Раунд интересный, но столько багов..
I am curious about the solution of Div2.C = = .I think lots of time , but still didn't come up with a good key.
Кто-то доказал что А — NP-полная?
Если да, то интересна дальнейшая судьба задачи? Ее с позором вышвырнут из архива КФ?)
Нет, попросят ilyakor написать первое и последнее решение на SSE
"there was a mistake in a model solution for problem C."
Was the problem solvable and only the judge's solution was wrong or was there a mistake in the problem statement making it unsolvable?
no one knows..
I saw some people had solved it before it was removed from the Standings, so they might know whether the problem statement was ok or not.
why this greedy wont work for problem c? simply sorting the points...remove the corner points,by finding the minimum value of a[i+rem]-a[i] for i=0..n-1-rem, where rem=n-n/2-n%2+1
I love Itachi
>mfw WA on pretest 4 on div1C
I couldn't submit anything last 20 minutes. It said page was blocked. You should have just let us keep writing the contest, if you want to make it unrated after the contest that's fine, but not being able to submit code makes me sad.
That moment when you spend one hour on D, succeed the test after finding out a stupid mistake, and it is 30 seconds too late to submit.
At least I did my first ternary search :)
UPD : happy to see a failure ont test 4 anyways
Lesson learnt: NEVER EVER use inbuilt pow function in codeforces. It behaves weirdly.
Can you show us why?
Sure:
Accepted: http://mirror.codeforces.com/contest/595/submission/14150524
Pretests Fail: http://mirror.codeforces.com/contest/595/submission/14150122
Huh. I've never seen that before, my submission got through fine using
pow. Then again, I do have four WAs on Div. 2 B.I'll be using a custom function from now on. C++ is weird. Thanks!
obviously. Pow is for float numbers. If you use it for integral values they got casted to float type and you get precision errors.
P.S. It has nothing weird with codeforces, go on and see the docs on C / C++.
I think its because of precision issues with floating point numbers. pow is a floating point function so such issues happen. Eg: pow(21, 14) gives me 3243919932521508680
use pow(21.0,14) always that you want calculate in C++ a^b write pow(a.0,b)
Emm, seems to not work correctly on my computer,
Still the same answer
Use powl() instead and see if the problem still persists ?
The same happened to me. But you were smarter and confident about your algorithm and figured out the problem.
I thought "Maybe the second pretest is not the given example and my algorithm is wrong". Two lessons learned in my case.
Like this if you gave up on the round because problem A seemed too hard.
Like this if you're too dumb to realize A is too hard and got pretests passed with ten-lines solution.
Just skipped it and solve other problems
Will this round announcement get fewer upvotes than the last round? (Last round has 120 upvotes currently)
(int)pow(2,10) in CF is 99，that makes me WA....
Conclusion：pow is poisonous
Actully 4th task is not about physics. A model of moving can be described like this: let start point be ( - b, 0), start be (0, 0). Start angle of point of circle is a (that's the angle between line centre-point, and line Ox).
One can see, that if we want to get finish in time tres, than we should take such a, that
where b = r * cos(a). It can be done through some mathematical analys: inequality is equivalent to
Using derivative, we can get, that
after this we simply use binary search on $t$. By problem condition, a should be in range [0, 2π], but I haven't proved it. Anyway, this solution passed pretests, so it's not far from truth.
Yeah, I know that you can derive it yourself. But derive it yourself by pen and pencil you will need at least 10-15 minutes(of course if you know derivative,how to compute arc length and cosines). The person who will Google "trajectory of point on wheel of bicycle) it will lead him to cycloid(wiki) where all your formulas are written.\n Since it is 80% of problem I think it is unfair.
We even don't need to use a derivative for finding max(a * cos(φ) + b * sin(φ)). One can see, that
so there is an $\alpha$, for which
so, $\sqrt{a^{2} + b^{2}}$ is maximum (and, obviously, it can be reached)
and something wrong with tex on CF, I don't know why my message wasn't parsed normally
You mistyped the last bracket: "b^{2}{" instead of "b^{2}}".
Could someone please check why the above solution gives WA for Div-2D. I have done the same thing mentioned in this comment but I'm getting WA on test case 8. Link to my submission.
Thank you
Thank God.. It's unrated :)
No worry for rating and Failed System test.
Верните мой 2010 с нормальными званиями, бета-раундами, дивизионами и с нормальным распределением рейтинга((
+228 рейтинга было бы (((
Как ты это подсчитал?
плагин же сделали
Hey guys , the wrong model solution caused a single round to be unrated, didn't cause the world war III to start!!!
I believe GlebsHP did his best to prepare the round, but he is after all a human, and no human is free from mistakes.
furthermore, this is not the first round which is made unrated because of wrong model solution in codeforces, it happened before with former coordinators, even in topcoder same situation happened before, please don't mix between what happened today and GlebsHP being a new coordinator.
"even in topcoder." So you're saying that topcoder is recognized as a better platform than Codeforces.
I agree with you! GlebsHP has my support (if it is important to someone :D). I only worry about really bad estimation for level of tasks.
when you are going to set a contest you have to check it 2 or 3 times at least to dont have this kind of mistakes if you cant or wont dont do this at all this isnt ww3 but its not that simple
Div2 B using c++ pow -> WA Changed pow to own power function -> AC
DDDDD:
The pow func in C++ sometimes cause trouble because it assumes numbers as floats and the return value gets wrong sometimes while working with ints in code
Same thing happened to me previously and left me in confusion :]
It's so annoying -.-
Worst of all, this isn't the first time this happens to me. I never learn :D
Что там с задачей А, собственно, не так оказалось?
http://mirror.codeforces.com/contest/595/submission/14159310 Why does this give me compilation error?
It compiles perfectly in my computer with g++
How is it possible?
M_PIcame from sky or what? :PI don't know, I only copied the code and compiled without errors or warnings. It seems that some compilers are including M_PI while other aren't. I've never used it...
Visual Studio 2013 knows M_PI if u were included cmath
I saw some cases where M_PI is not defined, it could be a reason
I manually defined pi and it still gives compilation error.
I've found this, as example of what you are saying:
Your text to link here...
Yes, I too feel so he should be back!!
Making Div2 ocassionally hard is a good practice indeed !! Adding maths problem reduces my fear from maths problems though I binary searched my answer :P !
But when I see this regularly I loose interest !
That is why ZLOBOBER was good... But respecting the coordinator there might be some reasons as to why rounds these days are becoming hard!
But I think my rank only depends on how fast I code Problem B . If I cannot I get a bad rank! Only a few people solve C making the ranks totally based on speed and in my opinion it should be balanced on Speed and Problem Solving!
and more problem solving. in this contest specifically every one solved b and no one solved c(actually d) and for me(my net was going crazy) it was bad lost.
Is Div.1 A solvable for the given constraints?
Edit:
I was only able to think of greedy solution for even values of n:
A will always remove a position situated on the boundary of the remaining array.
Now, whenever B moves, he can select the middle element from the remaining array, to ensure that he can select consecutive elements.
So, answer is min{x[i+n/2]-x[i]}.
will this give correct answer for n=even?
Yes. Let P(x,n)=min{x[i+n/2]-x[i]}. It is easy to show that P is not greater than answer — if the warrior doesn't care what archer does and delete all a[j] for j < i or j > i+n/2, the result will not greater than x[i+n/2]-x[i].
Let's prove P is not smaller than answer. After the warrior take turn, the archer can make P not smaller than it was before warrior's turn, by deleting the median of x.
For example: if x is 1 2 3 4 5 6, initial P will be min(4-1,5-2,6-3). If warrior delete 1, archer will delete 4, and x will be 2 3 5 6, P will be min(5-2,6-3), which is not smaller than initial P. If warrior delete 4, archer will delete 3, and x will be 1 2 5 6, P will be min(5-1,6-2).
Archer can prevent P from being smaller, and P for n=2 is answer, so initial P is (not smaller than) answer.
thanks for your explanation :)
Any ideas about why the statement "It is easy to show that P is not greater than answer" doesn't hold for n=odd?
I don't see how you implied this statement from n=even.
I make mistakes(in fact, I just did, for all the two hours), why shouldn't you? :)
If there's a probability for wrong model solutions of 0.01% for every round, the probability for it to ever happen in all the 330 rounds is 1-(1-0.0001)^330 ~= 3.25%
I have an experience in preparing a contest, and 0.01% seems to be too small const) It's closer to 1 - 5%, as for me.
The problems are quite interesting and the difficulty is fine. What a pity it is unrated. BTW, can anyone show me how to solve Div2 C/Div1 A? Even the algorithm for the wrong model is fine. I never know how to solve game theory problem
For warrior, I was removing first or last element (from remaining set), for archer second or second last element — depending on gap sizes at front & back. But I couldn't solve ties when front & back gaps were equal (it would require to iterate through all existing elements, to resolve ties), was getting WA on 6th pretest.
If n is even, min(a[i+n/2]-a[i] for i to 0~n/2-1) is the answer.
If n is odd, min(max(min(a[i+(n+1)/2]-a[j],a[j]-a[i]) for j to i+1~i+(n+1)/2) for i to 0~(n-3)/2) is the answer.
It can be proven by mathematical induction.
EDIT: Sorry, my odd solution was wrong too.
Code
How did you arrive at the result for n=odd? Did you try out for small cases like n=5,7,9 etc. and notice a pattern?
I tried to apply same mathematical induction to odd-case, but it was wrong :(
What is the counter test?
5
1 2 12 22 23
if warrior deletes 12, answer will be 1.
why did these past contests was ********
these past contests WAS?? WAS!!!!!!!!!!!!!
i typed half of this comment 10 minutes after the other half :)
BTW this one looks very similar to today's A: 377C - Captains Mode
positive point of unrated contests!
you don't have to wait for rating changes! :D
though Div 2 C got removed, could greedy be one of the approaches to it? like first sort the positions and then player 1 would try to delete positions from the end while player 2 would start from the middle?
What was the greedy approach for DIV2 C even if it was incorrect? I was not even able to get an answer for the second pretest? Please help !!
When will the editorial be published?
А где сейчас можно посмотреть условие задачи Div1 A / Div2 C?
Вася и Петя играют в игру "Рыцарь против лучника"
Сначала им нужно выбрать начальные позиции своих персонажей на координатной оси OX. Происходит это так. На оси отмечено N точек (натуральные числа). Вася и Петя вычеркивают точки до тех пор, пока их не останется 2 (т.е. кол-во вычеркиваний = N-2). Причем Вася играет за рыцаря, он силен в ближнем бою, поэтому при вычеркивании Вася старается сократить дистанцию. Петя же играет за лучника, ему предпочтительнее дальний бой, поэтому он старается вычеркивать так, чтобы расстояние было максимально возможным. Вася вычеркивает первым. Найдите расстояние между двумя оставшимися точками после вычеркивания, если оно происходило по стратегиям игроков (описано выше)
Формат входных данных В первой строке число N — кол-во отмеченных точек на прямой (2 < N < 200000) Во второй строке идут N координат точек x(i) через пробел (0 <= x(i) <= 10^9)
Формат выходных данных Расстояние между оставшимися после вычеркивания точками
Пример 1 Ввод: 3 1 3 6
Вывод: 2
Примечание: Здесь будет всего одно вычеркивание (N-2), которое сделает Вася. Он вычеркнет "6", тогда останутся точки 1 и 3, между ними минимальное расстояние
Пример 2 Ввод: 6 0 1 3 7 15 31
Вывод: 7
Примечание: 1) Вася вычеркивает 31 (т.к. между 15 и 31 максимальное расстояние) 2) Петя вычеркивает 1 (т.к. между 0 и 1 минимальное расстояние) 3) Вася вычеркивает 15 4) Петя вычеркивает 3 Остаются точки 0 и 7
По памяти писал, вроде ничего не упустил. Может название игры и имена другие) Ограничения вроде помню правильно
Время — 2 секунды Память — не помню
P.S. CF переносы исказил в тексте, прошу прощения. Но думаю, разобраться можно
Столько цинизма в комментах... Как будто тут не платформа для проведения соревнований, а не пойми что. Особенно обидно за GlebsHP. Да, раунд завален, возможно есть вина координатора. Но, как бы то ни было, нужно быть терпимым, не? Тем более, что бОльшая часть негатива исходит от 2 дива. Чет мне кажется, они не лучше бы справились.
Давайте не будем тут споры разводить. Косяки всегда случаются, да, но здесь вроде взрослые люди сидеть должны, и поведение также должно быть соответствующим.
Сейчас с большой вероятностью в меня минусы полетят. Ну да пофиг, высказался.
В задаче Div2 C/Div1 A есть какая-то с первого взгляда незаметная проблема из-за которой интуитивное решение: найти минимум в массиве из разностей a[k-i]-a[i] где k=n/2, не работает. Думаю что многие написали именно это. С первого взгляда всё достаточно просто. Допустим, оба знают где этот минимальный отрезок. Рыцарю выгодно вычёркивать числа внутри него чтобы гарантировать себе расстояние не больше чем длина этого отрезка, а лучнику выгодно вычёркивать числа за его пределами чтобы гарантировать что длина не будет меньше. Любой ход лучника за пределы или на границу отрезка вроде бы должен уменьшать ответ, ведь так он только помогает врагу. Любой ход рыцаря внутрь отрезка или на границу помогает лучнику исходя из тех же соображений. Это решение зашло на претестах. Но где-то что-то в итоге не так оказалось. Возможно что дело в неполной информации: мы не знаем как сходит соперник. Интересно почему это решение не работает и как правильно. Контрпример пока что построить не могу.
Всё нашёл. Если 5 точек подряд на одном расстоянии, то воину выгодно сначала убрать среднюю, а потом с той стороны, с которой уберёт лучник.
так уже тысячу раз в коментах закидывали тест: 1 2 3 4 5, первому выгодно взять тройку, и тем самым обеспечить ответ 1.
Поясните, пожалуйста, почему все пишут, что в этом тесте (1 2 3 4 5) первому выгодно брать именно тройку? А чем 1 и 5 плохи?
При тактике, которую использовало большинство сдавших (и, возможно, сам автор) ответ берется как min(a[i+n/2]-a[i]) по всем i. При этой тактике не удается получить ответ 1, удалив первую или пятую позицию. Сама тактика объяснена где-то выше
PLEASE HELP!!!
This is my code for DIV2 B https://ideone.com/eZXkMx
I am simply getting WA in test 2 where as it gives the right answer!!! And CF shows it gives WA! Why???
Casting double value of power to integer and expecting correct conversion? What about values as 999.999999, wouldn't it evaluate to int value 999?
But why it gives correct result in Codeblocks and ideone?
Because it's a different compiler, different cpu or different OS? Never cast floating values to integers, if you must — add 0.5 before casting. But in this case — you can just multiply by 10 until you get that power.
or write your own power
i had the same problem but in codeblocks gives wrong answer for me o_O
Yup, I had the same problem. Write your own function:
danilka.pro please elaborate on what the issue with Div2C have been.
I think it is no need to set too many queries in one test case in div2 Problem D. :P Because of this, I got TLE with my code using cin/cout. Anyway, it is lucky that this round unrated... haha
Div1 D looks too easy for that slot, Div1 B was too hard for that slot.
And Div1 A was impossible for the slot, apparently :P What was the statement about?
Binary search is too hard for Div1 B?
Judging by your 18 submissions to 549H — Degenerate Matrix, I'd say binary search is quite complicated :D
When solutions for problems will be published ? And when rating will be updated ?
This round is unrated, rating won't be updated
May be your Rating would be updated after the next CF round (if you participate!) ;) However, FYI, today's round is unrated.
Не смог понять: авторское решение по DIV2C дает другой ответ на одном из претестов?
Если да — вопросов нет. Но если роняющих автора претестов не было, то в чем принципиальное отличие от случая слабых претестов? Взломы? Думаю, что таких понимающих взломщиков было менее 1% от DIV2.
так задача NP-полная(вроде) – нечем проверять решения участников.
Это не ответ на вопрос, были ли роняющие автора претесты. Если не было таких, то отсутствие решения — частный случай простых претестов.
Так, т.е. в таком случае, по вашему, ситуация исправилась бы исключением из основной группы тестов, всех неугодных авторскому решению, и собственно проверка задачи на исходных данных, которые слабее заявленных?
Вы неправильно поняли. Речь была о простых ПРЕТЕСТАХ. Системные тесты бы все расставили по местам, поставив всем нули. Нет разницы между "простые претесты + наличие решения" и "простые претесты + отсутствие решения задачи".
У авторов нет решения для нечетных n, а если оно и есть, то явно по сложности не подходит A, что сбило многих участников. На 6-ом претесте был случай нечетного n, а у некоторых участников взломы с нечетным n не работали по причине неправильного авторского решения.
Hey guys, The codeforces says my code is failing on pretest. I check same pretest on my machine it passes. This is second time it is happening with me. Please help me why is this happening.
Don't use the pow function, it behaves incorrectly on codeforces.
Please less math problems next time. Math problems are cool, but not when they're the majority of the problems. Coding is more about algorithms than math.
Is that so hard, to always include maxtests in pretests? I have passed pretests with my
where k is max number of distinct prime factors, but it turned out that it got TLE on systests, because constant factor was too big. After some optimizations it passed, but this is one of main goals of pretests to prevent TLEs of solutions with should pass (OK, I agree that this was a bit higher complexity than intended one, however argument still stands).
I wonder why downvoting Swistakk is so trendy. I totally agree with him on this, my solution got TLE on systest 30, while after contest I changed barely anything and fit in half of time limit. I simply decided not to optimize everything, as they say, who doesn't risk doesn't drink champagne (or, in polish it's like "who doesn't risk doesn't eat"). In this problem there is a plenty room for improving time performance and I really don't understand decision of not giving at least one maxtest in the pretests.
Is it possible to solve div1A/div2C in this way: Binary search the answer, and check how many points need to be banned by the archer.
I submitted it in the contest but got a WA on pretest. However, it seems that this solution goes well for those countertest given so far.
Here is my code.
I thought the answer of
is 5
Yes, you are right.
Maybe there are different solutions to even and odd n.
I can see why your solution serves as a lower bound for odd n, but am having a hard time seeing that it is also an upper bound. Do you have a proof for upper bound?
P.S. I couldn't find a countertest.
Could anyone post Div1A problemset here please?
I solved the div2 D in pretest,but FST on test12 and get a Time Limit Exceed. I tried binary search and Newton iteration but not it didn't work. Could anybody help me? This is my code
Its feels kind of sad to me how this post got downvoted from >250 votes to 80 at the moment. Upvotes don't matter much in my opinion, but its downright disheartening to see people ignoring the kind of effort round writers put in preparing rounds. CF doesn't pay that really good and if someone has chosen to prepare a round is because he wants to contribute to the community.
my idea for problem B()--- lets take sample test #1--
n = 6, k = 2; what i will do is-
count all 2 digit numbers divisible by 38 ---
how?
lets take a look--
the last 2 digit number will be 99 or pwr(10,k)-1 and the last one digit number will be 9 or pwr(10,k-1)-1, so now what i will do?
i will divide (pwr(10,k)-1)/38 lets take result as x and i will divide (pwr(10,k-1)-1)/38 lets take result as x1 so (x-x1) will give me number of 2 digit numbers divisible by 38
but wait there is another condition i shud take care of that number shudn't start with b[i] or 7 so lets do it--- now there will be pwr(10,k-1) numbers starting with 7 but if i iterate through each and every number i wud TLE so what i'll do is i will take first number -- b[i]*pwr(10,k-1) and i will take last number ((b[i]+1)*pwr(10,k-1))-1 divide both by 38 and lets take result as x2 & x3 respectively, so numbers starting with 7 and divisible by 38 will be (x3-x2) ,substracting this result from (x-x1) will give me the desired result , now i will do same thing for all a[i]'s and b[i]'s and i will keep on taking product of each i's and finally output
point me if i am wrong anywhere
P.S. x,x1,x2,x3 are integer variables and u need to consider the 0 case too
You dont have to subtract the k-1 digit numbers, because they count as numbers that start with 0. Also take note that "0000000" is also a valid number and is divisible by everything.
Leave the mistake, Where is the Editorial?
My idea for Div1 A: (WA 6 during the contest)
Examine two cases:
n is even. Suppose both players have played their optimal game. Suppose that in the k-th move A picked xik and B then picked xik + 1. Group these moves into pairs (xik, xik + 1). Let lk = xik + 1 - xik. Note that in each step A can deny one of the pairs with his move. This means that B cannot get an interval larger than min lk with such a pair distribution. He is able to get it, too: when A denies a pair, B denies the second element of the same pair. Thus one pair will remain in the end of the game. Hence an optimal strategy for B is to distribute the xi-s into
pairs before the start in such a way that min lk is maximal possible. It is not hard to prove that the distribution 
is optimal (if xi-s are sorted).
n is odd. A similar argument works for A. Only now A makes the first move. Thus, A should deny one element and then devise a distribution into pairs (xik, xik + 1) such that max lk is minimal possible. Because after the first move, B denies an interval by his move. Similarly to the even case, A picks the second element of the pair after the move of B. Thus one interval remains. It is not hard to prove that after A makes the first move, the optimal distribution is (x2i - 1, x2i) (if xi-s are sorted and the one picked by A is excluded). Hence we should find the best element for A to pick in the first move. It is also easy to prove that this element should be one of the x2i - 1 (with an odd index). For this, we can calculate two prefix maximum arrays, say maxl[] and maxr[]. The array maxl[2i] stores the maximum length of the interval among the first 2i elements, if x1, x2, ..., x2i are distributed to the pairs as described. Similarly for maxr[2i], only it stores the maximum of the right side. The answer to the problem then is min(max(maxl[2i - 1], maxr[2i + 1])).
Can this be correct? Code here.
The idea is interesting, but this is also incorrect: in the odd case, sticking to pairs may not be the best strategy of A: to mix pairs but exclude the worst one may yield smaller answer.
Counterexample is this:
Answer is 3, not 15. (A has 3 turns, and he excludes 50, 125, 140)
Yep, you are right.
I submitted a code for div1A and got WA on pretest 6. I am wondering if this solution is actually correct. I think the answer is the maximum of the minimum distance between the rest points after deleting exactly floor((m-2)/2) points.
Oooops......So it seems not to work when n is even? lol
How about when n is odd? imho it must work when n = 3, and is likely to work when n = 5.
I have a bruteforce solution, and it seems that your solution gives correct answers for small odd n. (I tried it with n <= 9, and it passed more than 100 cases on my computer.)
100 cases? So few? In TCO final 2015 that just finished, Petr's 550 solution passed his 1000 randomly generated cases. He had to generate 9000 more tests, and the code only failed on "1 or 2 of them"
I'm not saying it's correct because of that. After all I only checked the case when n <= 9, which is way smaller than the actual problem :)
Why I become third?
Desactivate "show unofficial".
Someone became second in unofficial mode.
Wow, I see. Thank you!
brothers this was a good contests