Всем привет!
Раунд Codeforces #172 состоится в воскресенье, 10 марта, в 19.30 по московскому времени (23.30 по центральному поясному времени).
Это мой второй раунд на Codeforces. До этого я готовил раунд вместе с YuukaKazami. В этот раз самые сложные задачи приготовил Jiatai Huang(CMHJT), другие приготовили я с Yuping Luo (roosephu).
Наши тестеры — sevenkplus, YuukaKazami, OpalDshawn и pashka.
Сердечно благодарим Геральда Агапова Gerald Agapov(Gerald) за помощь и советы по задачам, Delinur за помощь в переводе условий на русский и MikeMirzayanov, разработавшего такую мощную платформу.
Я хотел бы лично поблагодарить сообщество Codeforces, вдохновлявшее меня на самые плодотворные идеи последние два года. Хотите – верьте, хотите – нет, но позиция Codeforces в китайском сообществе ACM укрепилась по сравнению с прошлым годом. Насколько мне известно, самые сложные задачи вошли в домашнее задание зимнего лагеря по подготовке к нашей национальной олимпиаде по информатике в этом году.
Также благодарим watashi, ftiasch и xlk. Ваши предложения и замечания очень меня вдохновили.
500 — 1000 — 1500 — 2000 — 2500.
Распределение баллов по задачам будет стандартным в обоих дивизионах.
Эти задачи немного полегче, чем в прошлый раз, но мы все же верим, что расправиться со всеми пятью задачами будет непросто даже закаленному международному гроссмейстеру. Задачи будут самые разнообразные. Советую просмотреть все пять задач перед тем, как реализовывать.
UPD:
Соревнование закончилось, поздравления победителям:
Div1:
Div2:
Поздравления tclsm2012, кто решил задачу D!
Нам очень жаль al13n, в вашем коде задачи D есть ошибка ... и Jacob, ваше решение задачи E проходит большую часть тестов, но на самом деле оно не правильное. Расскажите нам свое решение.
Very early announcement! Excellent!
QAQ..
123
ymm
Believe me . It will be a very interesting round. So , good luck and have fun
you have no chance to attend this contest. look at me!!!!!!! = = TAT(it's terrible to zhuangbi)
... No .. The problem has been substituted ... Actually he didn't know what the finally problem it is. ..
So you mean that he is going to participate???
Uw...That depends on himself ..
Surely I will not participate......
Ooooooooch , man ~ Are you crazy?
They are saying that the hardest problems were created.I think it's going to be interesting!!!
I think it will be interesting round with 9 creators :)
... Only setters and testers have saw the problems.)
What about translator?!:) She translated and she didn't see the problems?! WOW...Perfect:)
Well, you are right .. Delinur isn't going to participate the contest after all .. We'll try our best on the confidential work of the problems, to ensure the competition run fairly. You can trust us on this point, seriously ~~ ... )
Thx...I hope that in this contest will not be users like xiao_dao or xiaodao_50216 like previous contest (I mean rng_50216) :)
... And like peter50216?
Noo...i didn't mean peter50216 and rng_58...I mean only rng_50216...He registered 39 hours ago...before Round #171...
Maybe 4 problem-setter
... Why not participate ? .. (I am definitely sure you will lost your red handle after this round.) Uw, actually we are short of men right now... How about helping us test one or two of them? (′▽`〃)
MinakoKojima: you should protect your solutions:
these solutions are look very similar:
On codeforces: 3158774 3157931
3216871 3216492
On codechef: codechef1 codechef2
Micro Mezzo Macro Flation -- Overheated Economyhaha I love C too.That's how you announce a serious contest, not 2 hours before the competition! I wish everyone did the same.
it seems i am the only one holding a yellow handle among all the problem setters..lol
lol.. I think you can easily become red if you're willing to.
yes, maybe, but not this time, because he isnt participating :D
And you have created the hardest problem I've ever seen...lol
Because I'm the lost thing lol
your avatar ... Can't look directly <_<
I'm wondering if I miscalculated or scheduled time for this round conflicts with TCO qualification round 1C?
TCO round is scheduled for Saturday, not for Sunday.
Ouch... probably, I should sleep more. Thanks!
No , it doesn't . TCO round 1C is on Saturday March 9th and codeforces round 172 is on Sunday 10th March .
We intended to set on Saturday .. .
So is it going to be on Saturday which is today or on Sunday???
Why can't you read the topic before asking such questions?
or see the timer on top-right part of the page, which shows how much is left till the contest.
oh,I wasn't aware of this page because it's not on the top...
and the discussing members & testers seems very great!! I believe the round will be an interesting one
It would be an interesting contest :)
Привет всем!!!
ни одного комментария на русском языке...... значит я первый!!!!
Всем удачи! Повышения рейтинга! хотелось бы, чтобы задачи были различными, чтобы задачи были как на придумывание, с маленькими кодами, так и задачи с большими решениями.
Ещё раз всем удачи!!!
.
Big Fans !
I wish you can get fully accepted
Пишите по русскому!
I smell a lot of mathematics.
Hmm... Can you explain why?
He is right about that
Haha WTF ??? !
Picture
whahahah lol
I don't know it's my browser problem or nhandi graph really have logical problem ? btw it's a beautiful bug !
There is the same problem with my graph.
Wow you guys have interesting graphs!!!
and also ruban
I think anybody participate in code forces rounds #170 & #171 simultaneously have same problem . maybe for a little mistake in set history of code forces #170
Great! Wish we have a great night!
Wish you all one more "Share it!" in your profile page :)
ym..
Again 865 participants in Div 1. The record was not broken!:D
в 3 (див 2) задаче угол выражается целым числом или действительным?
В первой строке заданы три целых числа
Div. 1 A is boring...
Div. 2 C is boring, too...
Is it joke? Don't you know, that those problems are same?
why boring? I've spent about an hour without any result :(
But you had not solved it, right?
Could somebody explain me, how to solve it without formulas divination?
For example, you can divide shaded figure into 8 triangles.
I absolutely don't like this contest.
The problems were really hard. Didn't like this contest.
Should swap Div1.A and Div1.B
Well, I think B was harder conceptually to find algorithm, but A was harder to implement, and edge cases = annoying, also takes quite some time to solve on paper.
I think it's so hard for div 2
some ideas about D div 2 (B div 1)? I wrote rmq and rmq1 for the second maximum, but i didn't invent something faster than n*n*logn...
I think author's solution has O( n * log( 10^9 ) ) complexity
There is easy O(n) solution using stack to find first next greater number for each number.
What a shame, I thought it is O(n^2) and didn't solve this problem...
me too ! :|
There's an O(N) solution based on all nearest smaller values. I think it's a shame the constraints weren't higher.
10^5 is enough to forbid O(n^2) solution
I was thinking about this too, but N^2 for N = 10^5 is too slow for sure...
I use only one rmq, each time fix a max, find second max in left and right, then recursively on each side. which gives O(n * log(n) * log(n)) algorithm. http://codeforces.me/contest/281/submission/3284484
Problem Standard in DIV-2 was A,B,D,E,E :S
more like A,C,E,E,E i think
nearly solved B at the end, maybe if 2 or 5 more minutes :(
B wasn't so difficult, you can try all bs from 1 to n-1 in limit...
in my solution, i try from n to 1, so that it will replace the previous denominator if it has same rate of error
here is my submission which is accepted (after the contest :P) http://codeforces.me/contest/281/submission/3284962
Correctly is A, B, D, D, E.
Мне почему-то не пришел попап, что мое решение взломали. Баг был тривиальный, и я бы его скорее всего исправил. В чем может быть дело?
I love xxx :))
I think this contest had too much mathmatical problems :|
Nice problems, thanks for the contest. I almost solved C, but maybe next time...
My C was almost correct, I had to try to solve it immediatelly after B and not try to solve D first...
It's the first time I send my uncompiled code in DIV2 A Time -> 1:12 :D
Keep us informed.
Big useless images make me cry.
Why doesn't system test start?
Soon ...
Codeforces, you are drunk.
Извиняюсь за оффтоп.
Да, я писал об этом здесь
Думаю, это все из-за кнопочки "Поделиться"? Кстати, как в неё попасть?
Ээээ, по-моему вполне достаточно быть не настолько пьяным, насколько пьян CF:)
Странно, я открываю график, навожу курсов на точку контеста, всплывает окошко с инфой и "поделиться". Я тащу курсор на ссыль и окошко плавно исчезает. ЧЯДНТ?
Просто надо успеть:) Вот пример.
too much mathematics, A (div2) is nothing but a fun, and others are harder for div-2 contestants.
Div2 B is rather easy
isn't it a ternary search problem?
No need, you can try every denominator and binary search to find the numerator.
i did it, and get wa on 6th pretest, then i checked for numerator, numerator+1, numerator-1 for every denominator. i m sure of getting system failure :(
or you can calculate numerator directly in O(1)
It was not necessary,easy math in O(N) :)
A bruteforce setting the denominator and approximating the numerator in small iterations passes the test.
CODE
why system test is not stated yet? a lot people are going to have system failure on B (div-2) i guess.
В-div2 — это тернарный поиск ?
я бинпоиск отправил, претесты прошел:)
А как ты делал ? У меня идея была такая — для каждого знаменателя от 1 до n считать тернарником минимальное значение модуля, а потом из всех выбрать минимум.
Да, нужно было перебирать значение знаменателя искомой дроби, а числитель, при фиксированном знаменателе задается единственно, что позволяло решать задачу за O(n)..
систесты не прошел:) WA тест 33
перебор по знаменателю спокойно проходит. Числитель при известном знаменателе находится по простой формуле.
UPD. систесты прошло
Я тупо перебрал знаменатель. числитель выбирал один из int((i * a + 0.0) / b) и int((i * a + 0.0) / b + 0.5) сравнивал если меньше погрешность запоминал числитель и знаменатель. Самое главное если погрешность равна, а знаменатель меньше запомнить опять числитель и знаменатель.
Как обычно вопрос — что за 3-й тест в C div2?
Поворот на 0,90, либо 180 градусов.
Это у меня отдельно обрабатывается...
а return не забыл?
printf("%.8f", w*h);
Ой опять я идиот...
Как всегда в единственном случае задачу запорол — return не поставил...
если 90 будет тест то у тебя if(a==90) { printf("%.9f", h*h); return 0; } на тест 1 2 у тебя даст ответ 4 а надо 1
Всё норм, я заранее поменял их чтоб w всегда меньше h было
http://codeforces.me/contest/281/submission/3283862 (((
Interesting, systests didn't start and I moved from 255. to 254. ...
The problemset is a little bit easier than last time. I wonder how hard the problems were last time.:D
Even tourist solved only A&B....
No, he did A B C in 33 minutes and is 7th.
Edit: Sorry, I talk about current contest.
I think it's harder than last time, this time the Problem E is too hard to have an correct solution,but the Problem C is simpler.
Good problems! tnx! :)
I hope, there won't be 50 tests in A div.2, or else the system testing will be too long. For such a trivial problem 10 test cases are more than enough.
This is the hardest contest i ever participate... But i like the Problem Div.2 B.I spend almost two hours with so excitement.(Though i can't solve it yet.)
Just enumerate the denominator....you can calculate numerator quickly...O(deno) You may find it interesting if you have noticed Python's Fraction.limit_denominator method...O(log deno)
Fraction.limit_denominator fails the tests :(
http://www.codeforces.com/contest/281/submission/3278048
maybe you can try Fraction(x, y) to construct a fraction x/y
Accepted :| "Easy come, easy go" :'( Thanks alot
Thanks for interesting problemset, but it was hard)
Oh damn, my E solution failed on test 101...
I'm so sorry...Your solution was totally wrong but accept all the random testdata...So I generated the test 101...
Turns out you don't need to be a contestant in order to challenge solutions. ;)
He is responsible for the problem E bcz the writer is in hospital ...
In fact I'm one of the testers lol..I've mentioned it but got too much negative feedback so it's hidden T_T..
Can you explain then what kind of test is that (testing log doesn't show much)?
Just random data with N=6000,B-A<=1000...I didn't have thought I could make your solution WA but finally I did it..Thanks to my random data generator..Your solution got 3 WA in 10 with this kind of data.
Hm, let me get this straight — you've added a test to fail Jacob's solution during or after the contest?
During ... actually we want let him know about that during the contest but we can't ... His solution seems strange for us ..
Did you add test 52 for problem C too?
No..
I only make 50 tests for Problem C.I think the test 51&52 is add by challenge.The successful challenge will be check by system and if the hacked solution can pass systest, then that test will be added
I misread your answer, sorry.
Please forgive a tester without experience..Next time I'll make data not too weak...T_T
I think it's not good to add tests using participant solution.
Believe or not,we have prepared 4 data by this generator and rest by weak generators,and he passed them all.But when we use this generator for 6 more data,he got WA in 3 of 6...This is my first time to prepare problems for CF,I only made 12 large data in 100 T_T...
.. Did you have a gmail?. I'll send it to you as a gift :)
I think the challenge work is up to contestants, and if a tester like you challenge someone, you should at least show him a message during the contest warning that you've challenged him. Seems to be kinda unfair.
So If a wrong solution didn't get challenged then it would be considered the same as the correct one? I think it is more unfair. the basic rule in Contests like CF or TC is that the solution should be CORRECT to get the scores, if the solution is indeed wrong, then it shouldn't passed of course. You may think that the test data is weak. but It is really hard to consider all possible algorithm to generate all anti-test. As today's case, his solution is indeed an wrong greedy. A experienced coder like Petr will find this is wrong and won't try that, but if some one simply come up with it without proof and accepted, isn't that kind of unfair?
Yes, you're right. But at least you should warning him during the contest, so he'll be able to see what's wrong or either find the correct solution.
Umm, we indeed thought of things like that but don't know how. but anyway the systems only says that he pass the pretest,that doesn't mean anything else.passing pretest also has the chance of failing.
Unfortunately there are a lot of obviously "wrong solutions" which pass system tests and got accepted. (See this, for example http://www.codeforces.com/blog/entry/5947#comment-113634 ) Of course one needs to be lucky to get points for those, but by challenging a particular one you don't give any chance to its author. Did you prove that all other submissions of all of the problems produce correct output for any valid test case?
What solution is considered to be correct is an interesting question. As I know, if we use only subset of a functional language, we can indeed prove that the outputs of it and the correct one are identical for all possible inputs from given range efficiently. We can even write a checker for this. However, for CF/TC problems and procedural languages I always thought that solution is correct if it passes system tests.
If wrong solution's passing is because of good luck then isn't wrong solution's being challenged because of bad luck?:) I apologize for this but I won't discard test 101.I believe rating second,learning first.Correct solution for E is magical and worth learning.Why don't we look forward to it instead of stuck in a wrong solution?:)
I'd like to do so but I can't..because I don't know how to touch with him..I apologize for our weak data at the beginning :) In fact this kind of data(N=6000 B-A<=1000) his solution can accept 7 in 10~
I'd like to know is this the first time when tests were added during contests or is it a common practise? Maybe it's a question not to you, but to Gerald
I think DIV1 B has weak tests too. just run 3284652 or 3283083 with test like this:
It's so strange for a contest with so many problem setters and problem testers (with high ratings) that has weak data in three problem out of seven. (Div1 B, C, E)
What is the problem with tests to the task C?
For me this is unfair. One could use a random generator with a fixed seed (say, 123467) and it is always possible to find a specific test to fail this kind of solutions. Solutions using randomized algorithms based on some random assumptions (say, there are less then 100 tests) do not have to work for 100000000 tests you can generate on your own using full contest time and prepared generators to fail them.
We're so sorry about this ...... )
That doesn't make sense. If you're sorry, then you think you did something wrong. If you did something wrong, correct it. Is no one able to correct the results in this special case, considered unfair by many members, maybe majority?
If you're sorry, then you DON'T necessarily think you did something wrong.
people often say they are sorry when they learn someone who they just asked after had died for example )
Yes, you do think you did something wrong. In your example you did that accidentally, and if you could, you would withdraw your hurting words. But you can't do anything, so you say sorry. Please don't limit yourself to saying sorry when you can revert something you did. Just do it.
Now I it's apparent that you made right decision and everybody's happy. You had little time to make this decision, but you did it right. Even Jacob would be unhappy to win with incorrect solution. So you needn't be sorry :) I am sorry for my harsh words.
Cool A solution BTW.
it's my fault... better to say my heart trouble..?
Див2 должен был быть 100 — 1500 — 3000 — 3500 — 5000
Да уж, в Div2 таких задач А уже давно не было, прям не интересно как-то видеть её было. Самое интересное что есть люди у которых она упала на систестах.
I hope the editorial be published soon, like the announcement!
What's up with B?
number of failed after test 10 ~ number of succeeded So, the thing is that pass rate for is well near 50%
Guys, is 10^-6 realistic for Python float?
my God, hash somehow blowed the text up!
So, the thing is that pass rate for is well near 50%
How to calculate eps in Bdiv2?
I tried to use 1e-12 as EPS, but solution was challenged. Without EPS handling solution passed system tests.
In order to avoid using float number in problem B(div2), you may can use stern-brocot tree, I think.
Or just implement your own fraction class.
Oh, okay
bugs in topological sort.
-74 in round #171 and your overall rating increases. lucky :)
http://www.codeforces.com/profile/Obaida
see last 4 contest in my rating graph!!! (funny BUG) :P
Who added test 52 for problem C? It doesn't look like prepared test case and it failed 4 people including me, because of wrong calculation of a node depth in a tree. I don't think it was a main challenge in this task and it was the last test...
Well, I mean, the problem didn't say the edges had to go a certain way?
Yes, but I'm just interested if test 52 is one of the successful hacks or it was also added by organizers during the contest to make solutions of 4 people fail.
I think that it might be the successful hack made at 1:58:14, that was added to the system tests — what a fuc.ing bad luck...
Wait, does this work like topcoder such that successful hacks get added to the system tests?
yes.All successful hack would be added in sys-test.
tourist isn't codeforces target after this contest =(
hahahah
tourist rating also goes below 3000 in div 146. coincidentally writers was same.
@Admin ....my solution of D is showing Skipped final test....Is there any problem in system testing.?
problem b div2 test 33's answer is 1/1 but i think 2/2 , 3/3 , 4/3 are another solutions of it. :( a lot of contestants failed on test 33
If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.
why i forgot that????? :|
Why are you asking this question to ME? :D
WTF? this solution gives answer 4/3 on test#33 7 6 3 why it got AC?
UPD: Link: http://codeforces.me/contest/281/submission/3277121 UPD2: I compiled this code in VS 2012
What solution are you talking about?
can u tell me the meaning of Skipped final test.?
Waiting for comprehensive editorial from you, MinakoKojima ^_^
I don't know what to say... just look at this link : http://codeforces.me/bestRatingChanges/220401
[user:xiaoda] why is it showing skipped in final testing?? please reply..
Try to send a personal message
I didn't know ... > < 。。。
Great Problems , Fantastic Contest , Amazing System Tests , Brilliant Announcements. :)
Спасибо за хороший контест. Настолько сильно "угадыванием" я не занимался уже недели 3, если не больше.
Жду на разбор, чтоб понять решения второй и третьей задачи. Во второй написал что-то, что "должно работать, иначе бы ее не сдавали так хорошо", но все еще не понимаю, почему это работает)
А для третьей так ничего и не смог придумать, в результате написал решалку, подождал 20 минут, пока она нашла решение, и послал его с мыслью "да ладно, действительно?". Тоже понятия не имея, почему оно работает:)
А на контесте я включил режим "Я везучий, я не хочу доказывать задачи, я хочу в первой пересекать все со всем и строить выпуклую оболочку".
Кстати, мб я старомодный и отстал от тенденций, но какой-то слишком оригинальный проблемсет сегодня получился, в плане соотношения сложности и числа решений для задач. Первая задача что-то не похожа на 500.
А что за решалка такая магическая?)
Если решают за 10 минут — значит, кодить там от силы минут на 5.
Если кодить минут на 5 — значит, решение сравнительно простое. С очень небольшой вероятностью там prewritten, но тогда я уже хотя бы видел эту задачу раньше. Остаются 2 варианта — или динамика по дереву, или что-то еще проще, просто какая-то зависимость от параметров самого дерева, которая не дотягивает до самой примитивной динамики.
Первая мысль была — так как нас интересует состояние всего дерева в конкретный момент, значит, какая-нибудь тупая динамика вряд ли. А умную динамику так быстро не пишут.
Следовательно, должна быть какая-нибудь простая зависимость между данными о дереве и ответом. Будем искать ее, как функцию от всего, что можно выдрать из данного дерева или каких-нибудь его частей (у меня там было число листьев, высота, число внутренних узлов, размеры поддеревьев, глубины листьев, глубины вообще, средняя глубина и т.д.). Прикрутим к этому симулятор самой игры, который будет хотя бы примерно оценивать реальный ответ для данного дерева (сыграв сотню-другую раз), и генератор небольших деревьев для тестирования, и выберем все более-менее подходящие решения, которые у нас получатся — дальше можно проверить их более детально, или же попробовать "доказать" угаданное решение (я был слишком занят первой задачей, чтобы это делать).
Если это не секрет, могли бы Вы показать код своей решалки? Это похоже на чудо, что таким методом удается решать задачи.
Извините, но нет:) На самом деле, такой метод больше подходит для различных задач оптимизации — изначально я привык использовать его для этого. Но и для АСМ-задач иногда помогает.
Поразительно, мне всегда казалось, что программа не успеет найти за адекватное время ответ) Ты предполагал ответ как сумму дробей, у которых в числители линейная функция от всевозможных характеристик и в знаменатели, а далее перебирал сами коэффициенты в них?
Я перебирал несколько самых вероятных способов генерации зависимости (к примеру — просуммировать, использовать поднесение в степень, использовать произведение нескольких параметров, максимум из них и т.д.), дальше надо просто найти паттерн и коэффициенты.
Кстати, здесь можно поднять вопрос по поводу того, разрешено ли во время матча использовать дополнительные вычислительные возможности в любых количествах. В данной задаче оценочная функция не слишком долго вычисляется + само решение получается простое. И, если повезет с рэндомом, то вот так за 20 минут можно его найти на своем ноутбуке:) Но мог ли я использовать для вычислений что-то супер-мега-крутое, или какой-нибудь админресурс, если у меня есть доступ к таким возможностям и это ускорило бы перебор раз в 15-20 или еще больше.
Понимаю, что такой вопрос не часто актуален — вот такие задачи, немного чаще — задачи с возможностью прекалька... Но все же? С одной стороны, при беглом просмотре правил я ничего такого не нашел. Да и контролировать это нереально:) С другой, мне это кажется не слишком спортивным. Ведь ставит участников в ощутимо неравные условия в случае наличия таких задач.
У меня вопрос чисто из интереса: можно ли задачу B Div.2 решить как-то через дерево Штерна-Броко и/или ряд Фарея? Полчаса уже голову ломаю.
I have an answer about test case#31 B Div2 (99997 99999 99996):
Why the answer should be 49999/50000,
if 49998/49999 is a better result, and is "nearest" to 99997/99999 ???
just try to use calc, and you will see it:
99997/99999 = 0,999979999799997999979999799998
49998/49999 = 0,999979999599991999839996799936
49999/50000 = 0,99998
You're right.
I think if this round will be retested a lot of solutions will get accepted, and my too.
Nope)
99997/99999 — 49998/49999 = 0,000000000200006000140003000062
49999/50000 — 99997/99999 = 0,000000000200002000020000200002
You're wrong, dude.
Can someone explain in details how problem D div2 is solved ? Thank you.
Avoid floating point calculation totally, use long long etc i.e. x/y < a/b iff x*b<a*y peform binary/ternary for AC.
I was talking about D :)
lol,you can use stack to get next max after a number using stack.O(n) algo.
I solved it choosing the 'easy' way, ommiting any special XOR properties. We can see that there are only O(n) candidates which we should check e.g. pairs (f, s) such that TwoHighest(l..r) = (f, s).
Let's get some f and find the nearest, higher s on the right: f<s && S[f]<S[s] && s is minimal. Then there cannot exist such s' > s that some TwoHighest(l..r) = (f, s'), because if range (l..r) contains both f and s', then it contains s, but f<s && f<s'. Analogically for the right->left way.
For each number, we find nearest higher number on the left and right. Then check every candidate(pairs (i, right(i)), (i, left(i))) and print the maximum result.
How to find nearest higher number on right(left): Have the stack A after proceeded(0..f-1) numbers(top(lowest)->down(highest)). When we get S[f] = x, we look at A, erase every S[s] < x and set Right[s] = x.
wow i only solved A for 498 points (should have solved B too, i made a very silly mistake) and my rating increased by 140! my sincerest thanks to whoever assigned the new ratings! :) :P
Aren't they assigned automatically?
i'm not sure, but my point was thanks to the administrators who are in charge of assigning ratings after contests, as my rating increased drastically after solving just one problem!
Just curious, is there also an O(n) solution if in div2.D, the "lucky number" of S[l..r] is defined as the xor of the maximum number and the minimum number in S[l..r]?
Curious about it too.
http://ideone.com/vix2hL
Sadly, on the contest I didn't see O(n), I was writing inner loop with break on bigger number found. 5 minutes after contest i've wrote this 67-line(it was simply real_i before, and it was O(n^2) on 6 1 2 3 4 5 6 test).
Sorry for bad grammar in ideone comments. I think I should go to bed nao~.
Uh, I've misread question, sorry.
I guess minimum xor maximum is O(N^2).
Suggest this input: 6 1 2 3 4 5 6. You need to xor 1 with 2 3 4 5 6. Then you need to xor 2 with 3 4 5 6, then you need to xor 3... You can't skip any of them.
I thought about this too. But I wonder if there are any mathematical properties can be explored in XOR operations to improve performance.
I think xor in this problem is like "function of two args, returns some predictable number, which is not really dependent on size of args". So large_num xor large_num doesn't allways equals large_num, and you need to cound all xor's to get the answer.
But if there's some magical properties, it will be nice if someone explain.
I guess there's an O(n) solution, as my one was O(n) and failed test #13 which offered a special case.
Let's denote our two target values as Big and Small.
The idea is following: at first assume that there are two numbers in the whole sequence with different positions of the first '1'in the binary form. Then the two target values should differ in that 'first-1' position. That means, that the Big has to have the first '1' at the same position as the max value of the sequence does. That means that we should look for the Big only among such values, and the Small among the rest. So, we just take the sequence as a set of intervals [ Big?, Small?, ... , Small? ] and [ Small? , ... , Small?, Big? ] and check every one of them for linear time. Total length of those intervals is less than 2n.
The last case, which I personally failed, is when all values have the same 'first 1'position. In this case.... well, at least one could subtract a corresponding degree of 2 from each one start again.
You can reference my code, it's rather short)
1D's TL should have been 3s..Then the obvious O(k^2logn) solution would get TLE.
tutorial for 1C,1D and 1E in Chinese https://www.13331.org/420.html
Chinese..... = =|||||
Well the contest was great!!! Thanks for the problem setters.
He is an iranian : http://codeforces.me/bestRatingChanges/6073 Faghat bara inke ma ham ye commenti dade bashim .... :D
Разве в задачи В div2 в первом тесте не должно быть 1 2 ???
Нет!!!
2/5 к 3/7 ближе чем 1/2.
3/7=0,42857142857142857142857142857143
2/5=0,4
1/2=0,5
There's also an issue during testing:
The Problem D has the correct solution O(mklogn) , but the constant is not small. It also has an small constant approach O(mk^2logn).
During test I suggest that the TL shouldn't be very large because the O(mk^2logn) solution may pass it.
But indeed the difference between slow Java O(mklogn) and fast C++ O(mk^2logn) is minor. So if we want Java solution passed, we can't keep C++(mk^2logn) solution TLE. As a result, some competitor passed it by an straight forward O(mk^2logn) solution, which is not really expected.
So you should set k <= 100 and increase time limit and no problem...
Edit: Or you should stress test it until you find such a test that it gets TLE.
Actually during the contest,only liouzhou_101 got AC. not too bad..
Above all, Orz Shenben WJMZBMR && Chairman Fotile... I'm sorry for that my solution is O(m·k^2·logn) with highly optimized. In fact, I have no ideas about a O(mklogn) solution. Just waiting for the tutorial...
actually in standard solution,it takes O(logn) per update,O(klogn) per query. So limiting the sum of k to 10^5 would be ok.
Как решается задача C(Div2)? Попробовал разобрать различные ситуации, которые получаются в зависимости от угла. Похоже я что-то упустил. http://codeforces.me/contest/281/submission/3287389
Ну там всего два варианта — когда как на рисунке или когда трапеция.
if(a >= 135) a = 180 — a;
Что это? Почему бы не a>90?
Вот моё решение, если будет понятно...
http://www.codeforces.ru/contest/280/submission/3284642
Now, since some people were asking for my solution of E, I'll describe briefly the main idea.
First of all let's build a mechanical system that would solve the given problem. The system consists of:
Now the problem is to model this system and find its equilibrium. The key point is to add particles one by one. Apparently particles can only interact via hard links (item 3 in system description), so new particle can either drag some of the previous particles down or up, forming a "critical interval" (with difference between adjacent y's being equal to a or b). In my solution I simply iterate through the length of the critical interval to find the moment, when it stops interacting with preceding particles.
I honestly believe, that overall my solution is correct, but most likely I missed something when accounting for wall-particle interactions. There is an obvious question arising about uniqueness of mechanical equilibrium in the described system, but in my opinion there isn't any constraint that could lock the system in a local minimum.
Attention to this data:
Your solution gives correct answer:
But when n=3:
It gives wrong answer:
It seems you don't put forth your strength to drag first two particles down :)
I read your code and believe that without "derivative" it can hardly be correct..I insist that your solution was a kind of wrong greedy idea because you only focus on "critical interval",and it may not be always right.If I haven't understood your idea correctly,can you explain it again for me? Sorry for my bad English. (>_<)
BTW,I used to think your solution only works when all the delta is close to A or B,but it proves to be incorrect :) And your idea is a bit close to our correct one.
It seems I haven't properly dealt with the case when one critical interval shares one particle with another one. In that case verifying the equilibrium for that particle becomes more complicated.
Whatever,you are the hero in this round! :) Can you forgive me for what I have done?
From my point of view, that was absolutely valid in this particular case to do what you did.
Since it was a clear flaw in my implementation, that test should've been there prior to the beginning of the contest (just for the reason that it's clearly rather special case) as well as many similar tests (say, a test with answer "+a +b +a +b ... "). Your only fault was to rely on random test generator instead of manually finding some interesting cases.
It's so kind of you!Thanks!Now I feel much better :)
Fixed.
3314820
Well, I think the problems were very nice and easy to understand. Good job! ;)
Я — "Чак Норрис", я поднимаюсь, даже когда у меня -37 :D !! Картинка.
For div1 B...I tested the case#3 on my PC and the answer is correct,but the result is different on CF..
You can try comparing double numbers as fractions with equal dominators.
Div1..not Div2
На мой взгляд, распределение количества решивших по задачам раунда намекает на целесообразность динамической стоимости.
Но только не в такой примитивной форме, как сейчас.
Когда +-1 AC по задаче может половину таблицы перемешать.
Да, например, можно было бы соединить прямыми точки [0; 3000] [n/32; 2500] [n/16; 2000] [n/8; 1500] [n/4; 1000] [n/2; 500] [n; 500].
When will be the tutorial published?
Can someone give me a hint on problem DIV1 C (Div2 E)
I can tell you that the answer is the sum of 1.0/depth[v] for all vertexes in graph.
Why is that correct?
The answer is the sum of probabilities of direct removal of each vertex. Let's observe that in order to remove a specific vertex from the tree, you need either to remove it directly, or to remove one of its parents. All these choices are equiprobable, and their count is depth[v], so the probability of direct removal is 1 / depth[v].
why__ "The answer is the sum of probabilities of direct removal of each vertex." and why " the probability of direct removal is 1 / depth[v] but not 1/n
it is explained here.
If that is correct, then the answer to example #2 should be 1+1/2+1/3=11/6 instead of 2, right??
Edit: Forget it, I see my mistake now
Using mathematical induction, suppose, that it is valid for some graph, ExpMoves = Sum{1/deep[i]}. Let add a leaf with deep V. The added leaf can be choosed with 1/V prob. So in case of 1/V prob the answer is ExpMoves + 1. And in case of (V-1)/V prob the answer remains ExpMoves. So, expected moves after adding a leaf: ExpMoves' = ExpMoves * (V-1) / V + (ExpMoves + 1) / V = ExpMoves + 1/V.
How to solve E(Sequence Transformation)? I think I have found an O(n^2) dp solution,but got TLE on test case 8,how to opatimization
http://codeforces.me/blog/entry/6952
I'll tell you the method in detail, but you need tell me how to solve this .. ( ⊙ o ⊙ )
http://www.spoj.pl/problems/NOTOKNOT/
———————————————— Generally .. There are 2 different ways to solve this problem so far... One is use a datastrcuture to maintain the derivative function ... Another way is doing a dp algorithm base on a prove.