Всем привет!
Codeforces Round #201 пройдет в пятницу, 20-го сентября в пятницу, 20-го сентября в 19:30 MSK(23:30 CST)
Авторы задач: CMHJT и я.
Тестеры: error202, havaliza и tourist.
Мы хотим сказать спасибо MinakoKojima за обработку условий, Delinur за перевод условий задач на русский язык, и MikeMirzayanov за разработку мощной платформы для подготовки контестов.
Особая благодарность пользователям tourist и Gerald за их советы по задачам, теперь задачи расположены в наиболее правильном порядке.
500 — 1000 — 1500 — 2000 — 2500.
Будет использоваться стандартная разбалловка в обоих дивизионах. Задачи будут не очень сложными, но вам потребуется думать гораздо больше нежели писать код.
Удачи!
Thanks for the contest!
It seems that the problems will be very interesting.
Good luck to all participants!
Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.
Are you a bot who copy automatically comments with high number of upvotes? That's why you just used tjandra comment witout any reason? Edit: After looking at your previous comments, yes, it's exactly that...
Good luck to everyone.Thanks to XHXJ.
Compact and interesting statements wanted! Thanks! :)
Orz XHXJ ....
I will definitely take part in this round because UESTC_Nocturne has given me a lot of suggestions on my computer programming. Special thanks to you and Good luck to everybody. By the way,his nickname in pinyin is "xue jie"~~~~
ORZ...Good luck! God bless us!
oh ! 26 hours remaining ! I can't wait ! :-<
Thanks to the setter for preparing this contest :-)
If there're some tricky case, I hope all tricky case is put on the pretest, so if my code got accepted (pretest passed) it'll accepted too after system test.
Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.
So, What does hacking mean then?? All of solutions will be right and no one could hack another...
A small question, xiaodao...her help? ^_^
tourist!!!! Always be my super idol!!!!
Hope it to be an awesome round and Everyone enjoys it!
Sooo you say it is going to be the best tested round?:D:D
I apologize for my ignorance, but I always wondered what does UESTC stand for ?
UESTC
University of Electronic Science and Technology of China.
yes，It is very famous in China.
He asked if it was the best
UESTC_Nocturne CMHJT It's first time for you in prepare a Round ?
CMHJT have already set a few hardest problems on codeforces.(#172 D, E and #183 C)
UESTC_Nocturne has set lots of problems before but this is her first time on codeforces.
first of all thanks for your reply. Can i get some links for this problems :) ?
Reply not Replay :)
Good luck to everyone!Long time no coding in codeforces.
Best of luck to everyone , problems set by some of the best people in the arena , looking forward to it :)
first time to attend div1 I know it is so hard for me but good luck
minus
today and he will codeforces 201, and involves more than 3,000 people
Why I always got WA on #4 on D Div2?
someone push Start System Testing button please
Great round, thanks! Problems are interesting, indeed there was no need to write big solutions, except, maybe, problem B. Seems like it should cost 1500 instead of 1000 — it's the most hardcoding problem today =)
Why solutions are not visible even after the contest??
because system testing isn't started yet
Very great contest, problems were very intresting but not much hard. Could someone explain the solution of Div2.C / Div1.A? By induction I proved that if we have k numbers and there is no valid move, those numbers should be a, 2a, ... , ka, but couldn't find the complete solution.
Thanks in advance.
Try GCD to solve this kind of tests.
Let's denote g = gcd(a1, a2, ...an). It's obvious that every number in the end will be divisible by g. From other side, we can obtain g with Euclid Algorithm. Thus we can prove that resulting set is
. So the answer is 
, where amax is the greatest ai.
I think the worst thing and the best thing in the world may be you HAVE to skip a high scoring solution because you find a bug in it. :D
Спасибо за классный раунд! В дальнейшем буду ждать от вас еще контесты:)
had i seen the gcd part in C, it could have easily been my best! Hacked two solutions which made the same error as me. Good and false-motivating pretests!
After seeing the number accepted solution from the dashboard,it seems, in div-2 problem A is harder than problem B ... :(
Почему этот генератор теста в С неправильный ? Система отвечает что 2 пробела подряд в 12 строке.
А можно точное сообщение валидатора?
UPD Я кажется докадался. Вы посылали его как тест, а не как генератор. И в нем действительно два пробела в 12-ой строке.
Да, в самом деле этот тест содержит два пробела подряд в строке 12. Вы отослали исходник как тест, а не как генератор.
То есть, все остальное в этом тесте системе нравится? =)
Запускается два валидатора. Собственно валидатор, и проверка на well-formed. Там такая галочка в полигоне есть. Почему-то well-formed запускается первым, и это первое не well-formed место. Видимо порядок стоит поменять.
Видимо, стоит, потому что такие сообщения об ошибках несколько сбивают с толку.
Мне казалось, что если нажать на взлом, то видно какой тест сгенерировался. Из этого делается однозначный вывод мне кажется.
In problem D, the following phrase confused me:
Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.
Does it mean that our orders can depend on where the robot goes, as opposed to some set of orders fixed before the movement?
In the contest, I misinterpreted it as "the robot can receive orders only when it moves from the starting vertex", and that makes the statement controversial.
Yes, you can determine whether give a order to robot on every node it pass.
How did you solved A ? Thanks.
http://codeforces.net/blog/entry/8896#comment-146230
Thanks a lot. I didn't notice that comment.
it seems lots of people FST in problem C. :)
I hate TLE! I think an O(nlogn) algorithm should pass the system test.
However, it didn't change anything about this round being a good round.
my O(
(b - a + n) log n) solution works in 124ms.Yes, this is thanks to you.
I did not participate in this round,but i am glad to see so balanced and amazing problems thanks to UESTC_Nocturne.
I want to solve problemc C(div 1),I know only DP solution in O(n*(a-b)).what is correct solution?
each time choose such x_i that makes a-a%x_i minimal and a-a%x_i>=b. the correctness can be proved by the monotonicity of your dp function.
Tasks are very nice, especially A, C and D. (B is a coding task and it's fine. For E, I don't know the solution yet.)
I'm very luck to win this round by finding this trick in task C: x[] can have repeat numbers.
Thanks for the writers/testers!
Congratulation！For E, the standard solution is short, but need to find out something intereting, we will post editorial later and you can find details in it.
I've finally solved E in upsolving :) I had the idea during the round but didn't manage to deal with corner cases in time.
Here's my solution: http://codeforces.net/contest/346/submission/4523388
Hopefully long method and variable names make it understandable.
Oh, and congratulations on the victory!
When will ratings be updated???
Why is TL for problem C is only 1 second?
I wrote a solution in java during the contest and got TL (4522683). But when I wrote the same in c++ after the contest I got AC (4522630). This makes me sad.
There exists a subtle O(a-b+n) solution.Even written in java would get accepted.
Well, yes. The solution is very nice indeed. However I found an (a-b) log n solution and I settled for it, because I figured it's common sense it should pass and it didn't. There are other (a-b) log n solutions that do pass however, but have smaller constant or use less memory.
Did you intend to only accept the linear solution? If that's the case, why not give a-b <= 1e7 so people know the log n factor is too much?
No,most (a-b) log n program written in java got AC.
I guess you might forget that you need to sort xi or you use radix sort instead of quick sort.
Great contest!! Thanks to the problem setters and testers!!
Cool problems. Never had so many dumb bugs in a contest in my life :S
For example, in A, I computed the gcd, but forgot to divide by it, i.e. didn't do anything with it :D
How to solve C (div1)?
There's a apparently a linear solution, but an nlogn solution that passes in time (for example, my solution in the practice room) is this.
First, it's very important to make the given numbers unique, i.e. eliminate duplicates. Then you take each x_i and for every multiple of x_i between a and b (call it y) update best[a-y] = max(best[a-y], x_i) (I'll explain what best[i] is in a second). This whole thing is O(nlogn) (the worst case is when X = [2, 3, 4, ... n+1], because then you have the most multiples).
When you have that, then you process numbers from a down to b. For every such number (let's call it c), you want to compute the minimum number of moves you need to do to get to it from a (that's the 'minlen' variable in my code).
There are two options basically for each c. You either use the solution for c+1 and reduce a by 1, or you make a "jump". You store all the minlen values for larger c values in a Fenwick tree (or some such structure that allows you to do range minimum queries). Then you use best[c-a] to know what is the largest x_i that is a divisor of c. Using that x_i, you can get to c from any number in the set {c+1, c+2, ..., c+x_i-1} in one step. So you query the Fenwick tree for the minimum in that set, and increase that by 1.
HTH
My code prints output in pretest-1 in my PC BUT it prints no output in codeforces. Can anybody explain?
Nightmare。
can anyone explain me logic behind the solution of problem C of DIV 2 ? I have seen 1-2 codes , that is something i was thinking while contest, but still i am not able to get that solution. Can anyone please explain little bit ? thanks in advance.
Idea: In the end of the game all numbers printed will be
g 2*g 3*g ... MAX_NUMBERwhereg = gcd(a[1], a[2], ... a[n])This is actually not correct, though the answer with that assumption stays the same. Consider the case 2, 3, 5. Here g=1, but you can't make any moves, i.e. can't add 1 or 4.
I can add 1 = 3 — 2 and then 4 = 5 — 1.
Also, obviously we may get
gbecause of Euclid algorithm. After that we may get all the numbers up to MAX_NUMBER using- gAh, you are correct, my bad :)
I guess this is problem A from div1 (the Alice and Bob one)?
First, notice that it is never possible to get a number that is not a multiple of the gcd of all the numbers (let's call the gcd d). That's because if d divides both a and b, it will divide |a-b| as well. Therefore, you can divide all the numbers by d.
Also, you will never be able to get numbers larger than the max number (obviously), or lower than 1. Now, the key thing to notice that out of the remaining numbers from 1 to MAX, the numbers you can't get always come in pairs. That is because if you have three numbers a<b<c and a+b=c, you can't get either c-a or c-b. Therefore, the solution depends only on the parity of the number of missing numbers.
Edit: actually, you can get all the numbers from 1 to MAX (after dividing by d) -- see the answers above.
А я правильно понимаю, что при TL'е генератора тест просто недописывается? Просто у меня одинаковый генератор по задаче C на Джаве получал какой-то вердикт, что тест некорректный, а тоже самое на Плюсах проходило.
Генератор на джаве (взлом 79947): http://pastie.org/private/w4abbyu8u97kxpokaoptgg
Нет. Джава генерирует некорректный тест. В конце второй строки стоит
\n, а не\r\n.Было бы неплохо запоминать язык генератора(хотя бы совместно с языком сдачи, лучше отдельно). У меня сбрасывался на первый пункт.
Problem 346C - Преобразование числа has already been used on Baltic Olympiad last year link.
Sorry but .. what is the connection between this two problems? ..
And ... is there any website I can submit these problems?
The differences are that in BOI task you have to transform n into 0 (also there is many n's), you can use only second type operations and all x[] values are prime (but it doesn't really matter). When I saw problem C, I wondered that I just know the solution, which should also get AC.
I don't know if it is possible to submit BOI problems somewhere, but here are statement + test data + solution. So, it was possible to find the solution during contest, which is not so good, I think.
There are literally thousands or even tens of thousands of problems with solutions on the web. Sometimes duplicates will occur, there's nothing really wrong with that. Probably 99% of the competitors in this round never saw this particular BOI problem.
Since b is no longer always zero, there are more necessary tricks to avoid getting TLE.
Div2 D, had around 140 submissions , but only 10 got AC. Mine failed on #30 test case and cant seem to figure out a way around it. Any hints on how to solve it ?
You can do dynamic programming where the state (a, b, v) solves the subproblem where you're at index a in s1, at index b in s2 and the first v characters of virus are the suffix of the subsequence you've found in the prefixes of s1 and s2.
I assume many solutions failed on updating v. When you take a character (s1[a]==s2[b]), it is not enough to check if (virus[v]==s1[a]) and then either increase v or set it to 0. Instead, you must do something very similar to Knuth Morris Prat, i.e. there might be a smaller prefix of virus present in the new subsequence (i.e. the new v value may be smaller than the old one, but not 0). See my code in the practice room for details if you like.
4519236
Hacked by this test:
4520203
Accepted but wrong output for same test. I think CF should add hack tests to final tests like TC.
Problem A (Div 2): why "lexicographically smaller"? Simply "smaller".
When will we get Editorials for this Round? Nice Problem Set :)
it's up now http://codeforces.net/blog/entry/8903
Как решать задачу B(Div1), D(Div2)?
What deceptive pretests... originally accepting my brute force on E xD
This round was so good. "The problems are not so hard, but you need more thinking rather than coding" was true. Thanks for the setters :D
can somebody expain how to use KMP for tracing virus growth in DIV2 Problem-D
Когда выйдет разбор?
разбор/editorial на английском правда
not necesary at all , naive string matcing O(N ^ 3 * 26) for this problem , which is fast enough:)
can you explain how to define third dimension in dp corresponding to virus string
dp[i][j][k] , we'are at 'i' in string1 and 'j' in string2 and soltuion string has suffix with maximum lenght k , such that prefix of virus.
It was very intersting! Thanks!
The robot is so cute, isn't it?
I love this competition。