Всем привет!
Мы приглашаем вас принять участие в Codeforces Round #198, который начнется в пятницу, 30 августа в 19:30 MSK . Авторами задач являются я и Linh (ll931110). Мы также являемся авторами Codeforces Round 191 (Div. 2). В тот раз участники были довольны задачами раунда. Мы надеемся, что этот раунд будет как минимум не хуже предыдущего.
Linh придумал задачи D2-C/D1-A и D2-E/D1-C. Я придумал остальные задачи. Мы надеемся, что во время раунда вы потратите больше времени на обдумывание решений, нежели на написание кода. Хочется добавить, что задачи раунда не будут требовать от вас написания сложных алгоритмов. Вместо этого, все они требуют креативности, сложных рассуждений и терпения. Да, главный герой раунда — Iahub, как и в прошлый раз.
Я хочу поблагодарить DamianS, Gerald и Aksenov239 за тестирование раунда. Без них работа по подготовке раунда была бы намного сложнее. Также, спасибо Delinur за перевод задач и MikeMirzayanov за отличную систему Codeforces и Polygon.
Желаем вам высокого рейтинга и удовольствия от решения задач!
UPD1 Будет использоваться динамическая разбалловка в обоих дивизионах
UPD2 Спасибо всем, кто участвовал. Я надеюсь задачи вам показались интересными. Кажется, мое предсказание, что вы будете больше обдумывать задачи, нежели писать код, подтвердилось.
Мои поздравления победителям.
Division 1
Division 2
- Azat_Yusupov
- angel_of_monkey
- molamola.
- iseriohn
- Mato_No1
- silver__bullet
- TheDude
- Nero
- khuebeo
- uc-nuts
UPD3 разбор (English)
can't wait to find out who's the main character in the problem statements :D
You call positive feedbacks yelling at you about that u couldn't manage to avoid naive solutions' passing E.
Seems legit.
Err... Spend more time on paper... Does that mean this round we should draw sth, like round 195? by the way,thanks for ur hard work!
Our teacher said that this test is made by XHXJ,really?
Is this an individual contest? How to know if a contest is team or individual?
All Codeforces Rounds are individual
I was dreaming for months a contest like this: no complicated algorithms, spend more time writing on paper than typing on PC.
Good luck every one:)
GooD Luck :D
YoooOOoOOoo leEeeeeTeR
GL && HF!!!
Tasks will be sorted by difficulty in increasing order, will they?
By difficulty in author's opinion
Как решается DIV-1A ?
Возьмём две точки: i и j (a[i]<a[j]). Понятно, что из всех перестановок после i сразу идёт j только в (n-1)! случаях. То есть разность (a[j]-a[i]) должна войти в ответ с коэффициентом 2/n (когда мы из i идём в j и наоборот). Также для выхода из нуля (a[i]-0) будет взято с коэффициентом 1/n.
Таким образом мы узнаём, с каким коэффициентом будет входить каждое из a[i]-тых в ответ.
Нужно посчитать такое: (сумма всех путей)/n!. Любое расстояние abs(a[i]-a[j]) будет встречаться в сумме всех путей ровно (n-1)! раз. Еще добавляем сумму всех a[i]*(n-1)! — сколько раз каждая точка будет следующей после нуля в начале пути. Имеем (сумма всех abs(a[i]-a[j])+сума всех a[i])*(n-1)!/n!. Факториалы сокращаются, в знаменателе остается просто n.
How to solve B div2?
For each 2 points I find maximum "left" and maximum "right" triangles(using that points) and sum them.
i calculate all possible triangle,
then try one by one lets call this one 'left', and check for other possible triangle which is share one of the same edge, and check if that the other triangle is inside the first triangle or not, and call this triangle 'right', then out = max(out,left+right)
but i got wa :( in pretest 2, anyone care enough to correct my code :) http://codeforces.net/contest/340/submission/4381739
Excuse me, How's the time complexity of your algorithm? I use an O(n^3) algo., but I got TLE. :( http://codeforces.net/contest/340/submission/4378019
I use an O(n^4) algo and got AC, but before that I use a convex hull for a decrease count of points.
Problems are little bit hard for div2 contesters, but I have to say, very interesting problems.
Спасибо авторам за сложный и интересный контест!
Couldn't completely write NlogN of LAS for problem-D in time, because realized it in last 5 minutes. So sad =( And fchirica was correct, implementation was easy.
You can use Patience_sorting.
Here is my code which passed the system test
set st;
set::iterator it;
for(int i=0; i<n; i++) {
st.insert(a[i]);
it=st.find(a[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;
So you are not satisfied by =(, ok TOT.
div 2 problems difficulty A D D D E !!
A E D D E!
yes , problem B more than 70% failed final test
why doesn't the system testing start ? :-/
I hacked more than 10 'A' solutions with this test case:
1 1 1 2000000000
Weak pretests , in previous contests TLE solutions did not get pretest pass
me too hacked 12 with same
Special Thanks for your great contest! I'm willing to take all the downvotes only to thank you personally! :)
I think there is some problem on div 1 problem D'time limit! 2 dimension segmeng tree and the 2 dimension tree array have a same time complexity O(m*logn*logn),but you make first TLE and last one AC..it is different from usual cf's problem.
i think you probably make some mistake about the time.
the time complexity of quad tree is O(n) is indeed.
!!!what?...i treat it as O(logn*logn) until now.=.=~..thank you~
Can "xianduanshu tao pinghengshu" get accepted?I do want to do so,but when I see the time limit I changed my mind.(sorry I don't know how to translate it into english)
I don't see the time limit at first....555...and after TLE by segment tree, i'm too native to believe that cf would not "卡常数"..so i didn't to write tree array at once.
Are you sure about it? every step at updata or query on my quad tree(just like kd tree) , the area became area / 2. So i think the number of total steps is log(n^2), time complexity is O(logn*logn). Why you say it's O(n).
I think it's O(N) for query(1,1,1,n)
Agree.Your code is not log(N) for each query and update.Unless I've misunstood your code.
Thanks every one. i know my wrong now!
O(log(n2)) = O(2log(n)) = O(log(n)), so there must be something wrong.
btw.
binary indexed treeorfenwich treeinstead oftree array:)Похоже, что lhyzjz поставил АНТИрекорд набрав -600 http://codeforces.net/contest/340/standings/page/102
Ну и хрен с ним
Не поставил...
http://codeforces.net/contest/300/standings/page/15
Классные задачи...!!! Спасибо авторам за контест.
Nice problems, really liked them. Damn E, declared the array of 1000 instead of 2000, else I would've gotten AC.
Very nice contest. Congratz to the organizers!
Problem B in Div2 was awesome.
Very nice problem set,and a very enjoyable contest overall.
great contest! great problem! thank you all!
Very cool problemset. I really liked D: At first glance I thought it was another Range tree problem. I almost implemented that, but luckily I remembered the author's comment that "all tasks don't require too complicated algorithms" :D
Edit: First time in congratulation list, yay ^_^
Помогите кто-нибудь, я в замешательстве.
Отправил решение 4377911. Вердикт:
WA 1. Проверил через запуск и выяснилось, что мой код выводит10 3вместо правильного22 3. В какой-то момент добавил строкуcout << ans << "\n";после строкиsum += a[i];. Тогда ответ выводился верно. При удалении той строки опять получалась лажа. В чем проблема? Заранее спасибо.UPD: Вспомнил прикольную штуку, у меня все заработало, когда я объявил переменные n и i в глобальной.
Я тоже не могу понять, сдал во время контеста решение 4374933. Получил WA 1. Сейчас вижу, что тоже на тесте из условия выдает 10 3 вместо 22 3.
Я пересдал это же решение на Visual C++, получил OK (4375227).
Только что выяснил, что все зависит от ключей компиляции. Если компилировать под g++ с ключами -O0, то выдает на претесте правильный ответ, если с ключом -O1 — неправильный.
Посмотри, у тебя не такая же ошибка? В своем коде я ошибку найти не могу.
Я не знаю ответа на вышепоставленные вопросы, я просто вставлю свои 50 копеек:
1) Кроме смены языка во втором решении (4375227) появился вектор. Может он как-то влияет на процесс оптимизации?
2) Первый код (4374933) просто не компилируется на сервере под Visual Studio 2010. Да что тут вообще происходит?
Вектор появился от того, что я просто уж не знал, что сделать.
Второе решение с вектором обладает всеми описанными свойствами — поведение программы меняется при изменении ключа оптимизатора. То есть вектор не при чем.
Более того, выяснилось, что если заменить строчку
на
то решение всегда работает правильно, независимо от ключей оптимизатора.
Похоже, это баг в gcc. Говорят, что в gcc версии 4.8 это уже не воспроизводится.
Ну в этом решении написано "long long A[n];", что противоречит стандарту C++; так что это вообще должно быть compilation error, но оно его скомпилировало и видимо как-то весело соптимизировало.
Про решение [JustCrazy] пока непонятно; надо бы посмотреть, что генерит компилятор, но у меня (на GCC 4.8.1) это не воспроизводится.
У меня есть решение без long long A[n] (то, которое на Visual C++ сдано), где используются вектора. Проблема там такая же.
Проблема не воспроизводится на компиляторе 4.8.1, этому есть уже минимум три подтверждения.
Похоже, мы оба натолкнулись на один и тот же баг в оптимизаторе gcc, который уже исправлен в версии 4.8.
А у кого-нибудь есть gcc 4.7 и 64-битная машина? Этот баг проявляется только для int64, так что битность процессора тоже может быть актуальна.
В первый раз вижу баг, воспроизводящийся простым циклом for, без рекурсии и всяких ужасов. Интересно было бы его исследовать...
Женя Курпилянский говорит, что компилятор при ключе -O1 вообще пропускает строчку sumpairs += A[i] * i — sum; То есть sumpairs просто не считается правильно.
У меня 4.6.2 и 64-битная машина.
Упростил код (выкинул все лишнее — gcd, сортировку и объявление массива длины n).
После рассмотрения генерируемого ассемблера выяснил, что оптимизатор почему-то удалил строчку "sumpairs += A[i] * i — sum" и посчитал только сумму.
P.S. Кто не знает если использовать g++ с ключом -S, то на выходе будем ассемлер-код.
Вот это получается, если заменить "+=" на "= sumpairs +".
Код цикла находится в метке L5 (в обоих версиях кода). Видно что во втором случае он гораздо сложнее :)
Да, правильность твоего решения в g++ также зависит от оптимизатора.
При компиляции с -O0 выдает ответ 22 3, при компиляции с -O1 — неправильный ответ 10 3.
То, что добавление cout'а влияет на ответ, однозначно говорит, что это оптимизатор шалит.
Посмотрите в дизассемблере, что там с циклом происходит.
Я, к сожалению, не знаком с ассемблером и не смогу это сам сделать.
Но похоже, что минимум 4 человека в контесте столкнулись с аналогичными проблемами.
I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!
DIV1-C can be solved in O(N), why constraints are so weak?
solution
So that O(N*N) solutions can pass too.
I suppose problem would be more interesting with larger constraints, so well-known derangement problem with n^2 solution shouldn't pass:-)
The O(n) solution is well-known, so smaller constraints wouldn't make it more interesting. Just make the imbalance between people who've seen it and those who didn't worse.
Интересно, с каких соображений автор поставил задачу В (div 2) на такое место, что ее стоимость осталась на 3000?
Awesome contest ! I loved the problems , they were GREAT . Thank you for this very well made contest :) !!!
Thank you authors for the contest!
I'm wondering what was the intended solution in Div 1 C, because one can use inclusion-exclusion principle to get to the answer, which is:
,where K is the number of places i where a[i] = i still can happen and F is the number of free places. Judging from post-contest reaction, most people used DP approach. Thanks to gen for knowing Latex.
Also, does anyone has any tips on Div 1 D without using any king of 2D structures? I believe one could somehow split it in 2 independent parts: rows and columns, but couldn't think of how.
For D div 1:
First you need to observe that the problem can be solved by using only operations of 2 types: Query(1,1,x,y) and Update(1,1,x,y)
By observing 4 relative positions of (u,v) to (x,y), you can solve it by using 2D Fenwick tree (which I hope is simple enough) :)
Yeah, maybe it was intended. But I just got a feeling from the pre-round author comments that there is some cool solution with no 2D structures at all. And that the long long as the values was designed to stop the majority of 2D structures from passing.
There is another simple solution. Let n be the number of free cells and k the number of those free cells in which we cannot put values equal to their position, but it can still happen. Let calculate such DP[n][k] = (n — 1) * DP[n — 1][k — 1] + (k — 1) * DP[n — 2][k — 2], if k > 1. DP[n][1] = (n — 1) * (n — 1)!, DP[n][0] = n!. One can see that we should calculate only values with constant difference between n and k, so there are only O(n) states.
Could you explain the formula? Because I've been trying to find some combinatorial interpretation of it, without success.
http://en.wikipedia.org/wiki/Derangement if somebody's interested.
How it was necessary to solve the problem of B div 2?
You have to fix one diagonal with O(N^2) and then with O(N) find the best points ( the ones that make the biggest area ) to the left and right of the diagonal . Overall complexity is O(N^3).
Thanks!
Is there no time limit scaling for slow languages (e.g Python)? Was something like that maybe discussed before on Codeforces? I just timed-out on div1-B using python (finding LIS in nlog(n)), but passed in 0.124 after retyping the code in C++ :(
Спасибо авторам! Наконец-то я фиолетовый!
http://codeforces.net/contest/341/submission/4375062
No reversely sorted test case!
The set [1] is an independent set alongside [2] and [3].
Some whining about the problems follows.
Problem B: it was 100500 times already, it's a shame to reuse this problem again.
Problem C: it is obvious for the ones who remember how to calculate the number of permutations without fixed points (or for the ones who do not hesitate to use Google/Wikipedia during the contest). Again, this problem appeared on a different contests 1050 times. And for the ones who do not remember the solution it is way harder, since they have to reinvent this dynamic programming.
Problem D: it is super-evil, since 2-d segment tree (with time complexity
is terribly slow (especially in Java), and 2-d Fenwick tree (with the same time complexity) seems to be the intended solution (at least, everyone got AC with it). Did the authors intend to make a problem with key idea in non-asymptotic optimizations?
Update: another complaint: seems that most of the Java solutions for problem A are easily hackable (with anti-java-sort test). Did not you bother to add such a test? It is very unfair, since one can be hacked with this test, and in the other room the same solution may pass. Anyway, as I understand, general guideline for tests is to kill as much killable solutions as possible, and it seems to be violated.
If somebody had been successfully hacked by such a test then it would have been added to final system tests.
As I know, there is no automatic adding of successful hacks to system tests on codeforces (unlike topcoder). And adding the tests selectively is even worse (e.g. see this).
Exactly in that contest I was the victim of a successful hack added to the system tests. The successful hack made by Arti1990 was added as a test 52 to the final tests of problem C.
Ouch, this probably means that tests are still manually added during contest despite the discussion initiated by Petr. Too bad :(
Anyway, IMO problem authors should not depend on this and at least try to prepair strong tests before the contest.
Sorry, maybe my previous post wasn't clear enough. Exactly in that contest which you pointed in your previous post (Round 172) the successful hack was added to the system tests.
Ah, I see, thanks for the clarification. IMO is would be better just to automatically add all successful hacks to systest, but it can explode testing time as a drawback.
It is strange that there is no warning like this in task D:
"Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier."
And I forget to use long long but passed pretest. :(
%lld works now in all C++ compilers used on CF
Hmm..then why not to remove this annoying time-consuming message that appears after submitting llds? Time, especially at the beginning of contest, is really significant for wasting it on reading unnecessary warnings.
I submitted the following code for A: http://codeforces.net/contest/341/submission/4374002 and got WA on pretest 1, with checker saying it received 0 instead of 22. Could anyone explain me why did my code print 0? On my laptop it prints 22, both with "%lld" and "%I64d". The logical part of the code is OK, as I got AC after simply deleting some macros and unnecessary #include's (code http://codeforces.net/contest/341/submission/4376745).
Check this submission: http://codeforces.net/contest/337/submission/4383657 x=5, output=55834574853 You are using %I64d to print int.
There is a #define int long long before main() ;). So that's not the problem.
http://codeforces.net/contest/341/submission/4383888
Now it's working, check #define int ...
Try to compile your solution with -O3 option
is -O3 being used on CF?
Codeforces use -O2 (Link)
We have the same problems. Probably, it is a bug in gcc, fixed in version 4.8. Codeforces use version 4.7.
Can somebody tell me why this code ( http://codeforces.net/contest/340/submission/4383684) is outputting 10 3 ,it is giving 22 3 on my laptop.
Try to compile your solution with -O3 option
no change in output , but what is wrong in the code ?
What is your version of gcc?
Ideone also giving correct output : http://ideone.com/py5h0L
Try reading and writing with streams (ifstream, ofstream, etc..). If you want where you got that 10 you can also try to print ar as the answer and see what codeforces tells you
I've replaced #define LL long long with this:
And now it gives 22 3
http://codeforces.net/contest/340/submission/4383966
yeah that worked! How can this create any difference :-o ?
I used
g++ -O2 main.cpp -S -fverbose-asmto get the assembly codes and it turns out that the var ans is not in it while it is in if usingg++ main.cpp -S -fverbose-asm.I found that this code when compiled with -O3 will output 10 (g++4.6.2). So it must be a bug in the compiler.
After reading the assembly codes, I found it ran like this:
Looks that was a great contest!! unfortunately I missed it...
I find that i cannot view any problem. when i click the problem title, the web give the alert telling me "can't find or parse problem descriptor". I know nothing about the exception, and anyone can give me the answer or one solution?? Thanks!!
tha same with you,sad!
same with you.
same with you..
What's the meaning when I got a "Hacked"? Ps:I am a beginner!!
Your submit has some defect, someone use a case make your code got a wrong answer.
Thank you! now I know it!
Very interesting round and thanks for challenging problems !
Yes! that was interesting ! thanks for problems :)