Три промаха друг за другом, и вот я мигом вернулся в желтый цвет...
Раунд Codeforces Round #183 пройдет в воскресенье, 12 мая, в 17:00 MSK (21:00 CST). Сразу после раунда Google Code Jam Round 1C.
Авторы раунда:
- Yuzhou Gu sevenkplus (Задачи B и E)
- Yuping Luo roosephu (Задачи A и D)
- Jiatai Huang CMHJT (Задача C)
Тестеры:
YuukaKazami, havaliza, Velicue и я.
Мы благодарим Геральда Агапова (Gerald) за помощь и советы по задачам, Delinur за помощь с переводом задач на русский и MikeMirzayanov, разработавшего такую мощную платформу.
Настоятельно рекомендуем Вам просмотреть все пять задач, хотя бы одна Вам обязательно придется по нраву.
И еще кое-что. В этот раз будет динамическое распределение баллов по задачам, тем не менее задачи расположены в порядке предполагаемой сложности.
Удачи!
Great!! I think it will be a great contest while the setters and testers are very good. Thanks for your soon post :)
Not in midnight in Japan(and other far east Asia and Australia) Great!!!
Codeforces Round #183?
Fixed.
Are you sure in number of this round? Think, it should be 183.
Sorry for such a silly mistake ... /w\
Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.
Haha noone even mentions Div2 A and Div2 B problems :D
As you can guess, DIV 2 A, B is set by me ... /w\ ......）。。。
I think the problemset is easier but much more interesting this time..
Who set the problem for Div.2
Am I right that original statements will be in english?
Of course they're English.
Actually they should be in Chinese..:)
Maybe Chinglish lol~
Why this blog was not on home page ?
The first time I can participate in
Hmmm contest time changed? 6AM in California...
Why time is non-standart?
There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.
Thank
It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.
xiaodao's photo there >_<
I wondered why comments by MinakoKojima got so many negative feedback?
A question : is MinakoKojima (Feihu Tang) boy or girl?
I thought the name is a boy's, but in his(or her) photos shared above it's a girl....
You can see that her name is 唐菲蝴(beautiful butterfly Tang),then everything goes right.
She's really a girl, believe me.
I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)
давненько не было динамического распределения ^_^
It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.
Спасибо за контест! Всем высокого рейтинга(правда такое невозможно :) ) и удачи!
=w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T
в задаче B может быть 2 дата быть раньше чем 1 ?
посмотри на второй сэмпл
Получать в div1 клары по поводу задач div2 — это баг или фича?
Не баг и не фича. Просто это так. Более того если ты во время контеста просто будешь находиться на сайте, то тоже будешь видет клары.
Вопрос не только в этом. Это я сам уже понял. Сегодня меня заинтересовало, зачем в контесте отображать клары по задачам, которые не имеют к нему отношения (div1 D — div2; div2 B — div1). Уже, кажется, сам догадался, что это вызвано особенностями самой системы.
Подозреваю, что для приведения этого в более логичный вид — надо многое в системе переделывать, так что обойдемся:(
Ну представь, что ты начал решать контест но пока ничего не послал. Тогда тебя невозможно отличить от человека, который просто читает посты на сайте. Ты отличаешься только тем, что зарегистрирован на контест.
Захожу я в контест, смотрю "Вопросы по задачам", читаю то, что там написано. У меня там отображается одно и то же для обеих дивизионов, все клары для всех 7 задач дня, а не только клары по тех 5 задачах, которые были именно в этом дивизионе.
Я об этом "отображении". Прошу прощения, если сначала не совсем понятно выразился.
А понял. Ну это нехорошо. Но дело в том, что сообщения со всплывающим окном заведомо делаются общими и не несут связи с дивизионом. В этом и проблема.
У меня сразу при прочтении возникла мысль, что клар к div1 В и из-за ошибки в переводе слова "data" речь идёт не о данных, а о датах .
are there any mistakes in sample tests in problem B div 2?
Congrats for making unrated contest.
Who told you?
I hope you joke
Sir, this ain't April the 1st.
The contest was perfectly prepared and tested :D
Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.
Same here. I don't know why this is incorrect...
The sad part is that a lot of people solve it and I don't even know how to interpret the statement — should the rectangle be the closest to (x;y) or lexicographically minimum..
I spend a lot of time to guess — but i still don't know why... Sent clar, let's wait
I sent one an hour ago. Guess what the answer is? You're right, "no comments" :)
For me, they said, that my answer is not optimal..
Did they explain, why?
I sen't another clar 15 minutes ago, still no answer. UPD: Got an answer : We need first maximize the sub-rectangle, then take the lowest distance.
Damn, missed the word 'maximum'. Thanks, man.
because you should select biggest rectangular possible
Thanks for the answer. I feel like a total loser.. Ah, anyway, this will be a good lesson for my future contests.
From the problem statement . . .Your task is to find a maximum sub-rectangle on the grid (x1, y1, x2, y2). . . .
Missed the round — no mail?
Check spam folder.
Translation please? :o
wow wow clars, be easier)
Как нормально решать С?
How to solve Div2 D?
first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0
Когда хакал, у чувака было время выполнения 2.6 секунды, а в задаче ограничение 2 секунды. Хак не защитали. То есть это ок, да?
Какая задача? Какой взлом? Если что, в задаче 304A - Теорема Пифагора II ограничение по времени 3 секунды.
Видимо да ._.
Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.
python lol)))
У меня вопрос к тем, кто готовил задачи. Вы вообще свои условия читали? Вы хотя бы картинки смотрели в них? Мне весь контест приходили клары, которые заставляли меня открывать браузер и проверять, не взломали ли меня. Зато по злой иронии (я пока что не знаю почему) взломали мое решение по C за 15 секунд до конца, а нотис об этом я получил через 15 секунд после конца контеста. Задачи, в общем-то, неплохие, но уровень подготовки контеста оставляет желать лучшего. Особенно порадовал клар по задаче второго дива. Спасибо, будем чуть больше знать про даты.
UPD. Простите, поторопился с оценкой качества задач. Ниже написали, что задача D решалась популярной статьей из wiki. Набор задач после такого вряд ли можно назвать неплохим.
I'll just put it here. http://en.wikipedia.org/wiki/Cyclic_number
Кстати, у меня после успешной попытки взлома переходило на английскую версию сайта. Устраните проблему, пожалуйста.
I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.
http://en.wikipedia.org/wiki/Cyclic_number
no comments
Объясните, пожалуйста, а почему у всех проходят (по крайней мере, претесты) такие простые решения по С?
Почему не может быть так, что если бы удалим одно число, это повлияет на много пар, в которые оно входит?
Because of so many mistakes, I strongly think this round should be unrated.
if so, this will third continuous unrated contest :)
I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.
Не знаю как в английском варианте, а в русских условиях количество ошибок было больше чем в моей контрольной по матану на первом курсе!
Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?
this is called dynamic scoring
It's dynamic scoring
What a funny round!
Сегодня я узнал, что такой код
под Java 6 и 7 на CF в запуске работает 5 секунд :(
Я о существовании такой гадости узнал после одного из онсайтов :(
Тогда хватит это терпеть!
Давайте вспомним этот пост
Great round, interesting problems. :-)
The problem is nice,but clarifications too disturb.Waiting for next round.
My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...
an O(n^2+ans*k^2+a_max ln ans) solution was expected.
Sorry, I mistook the analysis of my order... My solution was your order, thank you.
I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...
Try to use array instead of vector, it speed up performance of my code dramaticaly in this problem.
Oh, thank you for your advise.
Nice problems. A lot of maths, but It's enjoyable. :)
Intereting problems!
The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".
What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?
System testing of Div.2 was very bad.it was finished , but final standing was not ready!
Div.2 A
My code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....
TvT
Check out mine 3706566. I think problem is in
ceil()andfloor(). Got AC replacingfloor(c)with(int)c— 3712951. I would like to say : Authors, How about increasing time limit to 4s ? but it's too late. I have already got my Wow you have +67.i too used ceil() function and TLE...
It would be better that you check your solution in custom test before submitting....
Долой 31й тест в задаче B див2! "сколько между ними дней включительно"
Только что с права видел ссылку на разбор. Но когда кликнул попал на свой профиль. И всплывающее окно, что недостаточно прав. Мне кажется, что это бага.
Нет, просто разбор случайно опубликовали и потом сразу скрыли в черновики.
Автор убрал блог в черновики
ORZ failed div.2 A
For Div2 C, now I understand why I could not find any formulas for even values of n..
Weak pretests :(. B-Wa 11 because of mixing up n and m.
Wow constraints were really strict.
My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...
http://codeforces.net/contest/304/submission/3706514
Are you still sure that's because of floor()?
Well I did some tests:
Using floor: http://codeforces.net/contest/304/submission/3713082
With a cast: http://codeforces.net/contest/304/submission/3713854
843 ms with cast
1609 ms with floor()
But it doesn't mean that solution with floor can't be accepted
my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...
Are you sure your solution is your own, not copied from others?
Screencast: http://youtu.be/XWsPoC4p-EY?hd=1
add music))
How to get full test cases for: http://codeforces.net/contest/304/problem/E?
Thanks!
Check the submission of Ents : http://www.codeforces.com/contest/304/submission/3710988
In the submissions large input data are cut.
you can't get large test cases
Такого со мной еще никогда не было. Я хотел взломать решение dilutedream а. За 23 секунды до конца вбил тест подумал, что он не корректен. Подправил его и снова сделал взлом. У вот теперь я вижу, что мой первый взлом оказался удачным, а во второй раз за одну секунду до конца я взломал kingofnumbers. :-)
Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:
wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'
This doesn't look like a correct probability, does it?
I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.
All tester's program have different solution so you know
the model solution of E is wrong...it has precision problem.
the setter is trying to fix it... but still rng58'solution seems has precision problem too...
actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.
I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:
int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }
My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).
Currently I guess it's impossible to solve this problem precisely under the given constraints.
That is really bad.
I think this round should be unrated to you QAQ.
yes, if his solution is realy correct
Yes, they can.
tourist's solution has no precision problem, but it run in O(n^5),maybe too slow. (it run 1890ms,barely in time:) )
I optimize it and work out an O(n^4 logn) solution,I guess now it is ok:3716717
In attempt to make my Java version go through the time limit (without use of
if (l[i] <= L && r[i] >= R)elimination) I gradually optimized it and after succeeding I also found out that Gena's (with or without your great asymptotics improvement) solution can still be noticeably optimized. :)Initial version: http://codeforces.net/contest/303/submission/3716717
With two code optimizations: http://codeforces.net/contest/303/submission/3718523
Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.
So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible.
Thanks for the notification!
I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE （the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.
It seems that my solution's running time doesn't depend on the actual test case as long as li ≠ lj, ri ≠ rj and li < rj for all i and j. A gap of 110 ms is not big enough, though :)
Your optimization is nice, thanks! Now the problem is really solved.
I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.
Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)
We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.
My appologize for this situation. And great thanks to tourist for the notice!
Can you write tutorial for this problem?
Задача D div1 во время систеста имела 56 тестов, сейчас там есть как минимум 57, и некоторие accepted решения не проходять етот 57 тест.
It seems I solved 303C - Наименьший модуль with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.
Is there any testdata which challenges the program or I calculate the complexity wrong?
Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.
Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.
EDIT : The proof I have post is wrong. See the comment below.
Please correct me if I am wrong, but I am not getting the proof.
When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.
You are right. Sorry for having post a wrong proof.
No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.
I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.
If you get the proof using the above logic please let me know.
If
, then 
or just 
, where S = 0 + 1 + ... + n - 1 = n(n - 1) / 2. So, there must be 
. But when n is even, 
.
Where S=0+1+2+3+...n-1=n(n-1)/2
Thank you, fixed.
there must S = 0 mod n. But when n is even, S != 0 mod n. I do not understand the above statement. Could you please elaborate more. Thanks
When n is even, S = n * (n — 1) / 2 let n / 2 = p which is smaller than n S = p * (n — 1) Clearly, S in this case is not divisible by n.
But also when n is odd. The sum formula stays the same. or I am getting this wrong ?
Ahh Now i get it. S = n(n-1)/2 this sum is divisible by n because S/n = (n-1)/2.
Now if n-1 is even then n-1 is divisible by 2. else if n-1 is odd(n is even) the sum is not divislbe by 2. thus not divisible by n.
this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.
for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1
Why is that? How do we come to this?
I had the same doubt. But I guess it is expected that we try the obvious permutation first and observe that its the required one. When N is odd having the permutation
0 1 2 3...N-1
0 1 2 3...N-1
gives a permutation of required category. While it has been proved above very nicely that for N-->even there won't be one
Стоит tourist-у написать комент, как он получает кучу плюсов :)
For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.
Check the wikipedia article, it also contains a proof
How to solve div2 E-Minimum Modular? Thanks in advance.
We check that "if we choose m to modulo, we can do the array satisfies conditions?" for all integer m until we find m from (n-k).
Answer ≤ 106 + 1 because if we choose 10^6+1 for m, obviously it satisfies condition.
When we search about m, all we have to do are research about multiple of m and get the array of "Which pair of integers are same modulo m". If the size of array exceed 10(
), give up search.
In this solution, the order is O(N^2+a_max log a_max+k^2 a_max) because O(1/1+1/2+1/3+...1/a_max)=O(a_max log a_max).
Similar solution of mine in Java (3754545) gets TLE. I think time limit is very tight for java solutions. Any thought?
Replacing ArrayLists to Arrays makes it much faster. I got AC. Lesson learned.
Thanks.
When will the editorial be published? I really want to know how to solve Div1E...
The editorial has been published, but It is doesn't have solutions for Div1 D and E http://codeforces.net/blog/entry/7641
Thank you so much! I'm going to continue to think about Div1E.