Всем привет! Соревнование Codeforces Round 174 будет проводиться в обоих дивизионах в воскресенье, 17-го Марта в 19:30 MSK. Задачи готовили abacadaea и я (scott_wu). Традиционно мы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач. Большое спасибо MikeMirzayanov за создание такого отличного сайта. Мы очень взволнованы, ведь это наш первый Codeforces раунд.
В этом раунде Вы будете помогать Фермеру Джону, Бесси, и коровкам. Мы надеемся, Вам понравятся задачи! :)
Распределение баллов по задачам будет немного нестандартное:
Div2 — 500 — 1000 — 2000 — 2000 — 2500
Div1 — 1000 — 1000 — 1500 — 2000 — 2500
Удачи Вам и приятного кодинга! Как обычно, чтобы сделать раунд более захватывающим, мы советуем прочитать Вам условия всех задач!
It's like USACO only with faster results! :)
Wow, finally some Americans.
The moment I saw FJ's name I said it should be Americans :D
... There are two 2000 in DIV 1 ! ...
... Maybe I should think twice before decide which one should be attacked first ... )
...There is only one 2000 in DIV 1 !...
...there are two 1000 in DIV 1 !...
...Good Luck!... )
There must be some trouble with my eyes ..
/w\. I'd better go to bed now...But, you're already red now...
... But I want to become a IGM .... ... )
В анонсе есть две опечатки. 1.Правильно не "Традиционно вы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач. ", а "Традиционно мы благодарим Gerald за помощь в подготовке соревнования и Delinur за перевод задач.". 2.Правильно не "Вы надеемся, Вам понравятся задачи! :)", а "Мы надеемся, Вам понравятся задачи! :)".
Will Фермер Джон and his N коров (1 <= N <= 100,000) make an appearance?
There is no cow level.Like!! «Che Haali mide inja benevisi bad ina nafahman o kolli beshun bekhandi :D»
Фермер Джон со своими коровами постепенно захватывают просторы интернета, а особенно USACO и Codeforces)
.
I just wanted to see how my avatar looks in the comments.
Really nice!!!
we always see beautiful problems in USACO contests.
I hope we have beautiful and interesting problems in the first usaco-like code forces round !
But not very difficult like USACO 8-))
Good to see Bessie and the cows invading the world of algorithms !
Hi guys, looking forward to round 174.
I wanted to bring up a problem that I found while solving other past problems. The Python language is not very well supported, so that even if a program has the right time and space complexity, it wont pass the tests because the tests have been written with C/C++/Java in mind.
for example I solved http://codeforces.me/problemset/problem/222/B but it would sometime pass and most of the times not pass depending on how many answers I would spit out at a time.
Is it possible to take some actions toward better support of Python? maybe supporting Python3x would be enough cause it has faster input/output libraries.
Please let me know,
You can mail to the administrator about this issue
pretty good! Good luck to everybody.
many coders from various countries have been holding contests;great!
and I wonder Bessie the cow and John the farmer will cause problems again :)
Counting both Div1 & Div2 , there are One 500 , Three 1000s , One 1500 , Three 2000s but Two 2500s break the sequence :)
Wish I can be red after this contest! I will do my best to help Farmer John to handle his cows!
My time to be pink coder :)
But I think it looks like purple more than pink ~>_<~
I think it will be better to mix both of them (purple and pink) to get Candidate Master's color).
i think it mix of both !!
How about :
My time to be
rgb(170, 0, 170)coder :)I hate "fading the more negative voted comments" feature of codeforces. It takes me more time to see the comments. I do not why I always open the comments with negative votes(they are interesting and I want to see what people hate and why ??).
It would be good to have a possibility of reverting the vote. Some minuses may be done by mistake. It's an irreversible mistake now.
Wow, its good.. everyone likes usaco problems and fermer John... So i wish everybody luck :D
fermer?maybe farmer =D? Good luck, we will help you Mr. John!!!
oh sorry, its Technical error :D
Lol, you get Technical error and '+' , i found you error and get '-', nice community -_-
will I have to insert "USER,LANG,PROB" headers in my code? :))
Will you have to do this same in usaco contest ? :))
No USER it's ID.
and I really did it, just in case I need them :)))
http://codeforces.me/contest/283/submission/3334424
It will be produced in usaco's difficulty problems?
The score distribution look's pretty good to me.Wish we have a nice contest! Thank's goes to USA setter scott_wu and abacadaea. We like to help Jhon, Bessie, and cows with so much excitement. :)
В двух предыдущих раундах div 2, задачи "A" были очень легкие и интереса особого небыло их решать. Надеемся тут будут интересные задачи...
Спасибо!
Если ты не заметил , задачи А всегда лёгкие и соответственно особого интереса не вызывают.
По сравнению с остальными они очень легкие, задачи состояла в том что надо считать сроку и вывести ее, только сменить первый регистр символа.
Сейчас задача А не очень лёгкая...Накаркал...
Farmer John? I think I'll back to blue...
memeda
Nice and exciting contest, cute problems! I'm so sad because i couldn't register for it :((
I think they mixed up A and B))
Я думаю они перепутали местами А и В))
Someone else having problem to hack ?
yep....There has been a while that I cannot lock my problem, and there has been a while that I cannot see other's locked solutions after I locked my problem, and there is the last moment after I submitted a hack waiting for the webpage to response for 10s it says contest end.
Why i cant hack?
Can't process your hack, try againIn my room(num 24) was 0 hack.why? becose there was not some icon to upload generator.when you use input block ==>
"Can't process your hack, try again"i saw >10 solution with TLE but I could not hack them :(I hacked 4 solutions(with TLE too :)) without any problems.
You are not in my room!
I just tried to say what I had no problems when hacks solutions. I think, you should write letter to administration.
:) i just send message but they wrote me "Write you own generator and submit it."
Maybe a pro in your browser
Finally see Americans set the problems, good job. Problems in the last contest are way too sophiscated, and this time the problems are beautiful.
I was thinking why codeforces is still in Beta version, Now I know the reason "504 Gateway Time-out".
I was seconds late to submit B :(
Not this time wjmsbmrThank you for very interesting problems.
Looks like we beat the USACO results :)
Haven't xperienced too hard DIV-2 A before :\
When p = 2 I see some code return 1 in this case. I really don't understand why, because when p = 2 the only possible value of x is 1 , while (x-1)%2 == 0 , clearly.
Now you can see wjmsbmr is not me LOL.
Unless...
who said it is U???~~~
После третьего или четвертого взлома от Egor у меня начали закрадываться сомнения... Примерно после шестого я понял, что мое решение неверное, подумал — "да ладно... все равно я в ж***, так что пусть ломает, перешлю потом, мне не жаль... Если бы не он — я бы вообще не заметил баг..."
Возникло странное ощущение, что я сделал хороший поступок)
На чем все А ломали?
Возможно переполнение int или TL.
На обычном переполнении.
Спасибо, что-то вообще не подумал об этом
Если набить большой-большой вектор, потом много-много раз применить первую операцию ко всему вектору, то сумма элементов вектора превысит границы int.
Переполнение int.
В решении за линию некоторые забывали обнулять при добавлении нового элемента или при удалении уже имеющегося величину, отвечающую за то, сколько надо прибавить на префиксе, заканчивающемся в этом элементе.
Strongly suggest unrated
I can promise you not only unrated round, but more! You will be banned soon because of unfair play.
first time seeing admins publicly announcing name of cheaters. I think the above statement of admin is result of outbrust of feelings. Shouldn't they give person a chance to explain his stance as Troy1118 is a member of codeforces for 2 year.
I do not think his situation is like those unrated people who cheat in very first match. (It does mean at all that I am supporting cheaters. If he has cheated , he should be banned no doubt. But admin's reply again raises the question of whether a person should be given fair chance to defend himself and also of whether publicly anounce name of the cheaters or not ??)
May be Admin has special powers. I did take the name of a person in the previous contest(link to comment) and got -40 + lots of advices.
i think you got '-' because you reported it.
What has he done?
Sorry for my interest, but can someone tell me why (s)he (Troy1118) is going to be banned ? Which rule did (s)he break ?
Я надеюсь, что не зря использовал в A(div.1)/C(div.2) дерево отрезков с ленивым проталкиванием. Или есть более простые решения?
Есть:)
=(
Ну расскажите хоть.
UPD Спасибо за ответы.
при первых двух операциях сумму и кол-во поддерживать поддерживать легко.
Давайте теперь поймем сколько вычитается из сумму при третьей операции. ДЛя этого храним
s[i]сумму добавлений на префиксе длиныiТогда при удалении
А можно пояснить шаг "s[cnt — 1] += s[cnt]" ? Почему есть влияние на какой-либо элемент кроме последнего?
s[i] = x значит, что мы добавлили ко всем числам на отрезке 1..i по x. При удалении последнего элмента, нужно указать что мы добавили на отрезке 1..(i-1), иначе информация потеряется.
PS: коряво как-то объяснить получается)
Теперь все понял, спасибо! :)
После каждого запроса нужно знать только сумму. При первых двух запросах сумму просто обновляем (либо плюс x·a, либо плюс k). А при первом запросе добавляем к add[a] значение x. Когда будем элемент удалять, то всю add[last] прибавим к add[last - 1], а от суммы отнимем val[last] + add[last], сам же add[last] обновим на 0.
Я сделал что-то типа пирамидки с помощью доп массива с общей сложностью O(n)
The Contest was so cool, i like the problems. but i couldn't solve them !!! If i had more time, i would submit problem C too, i solved it but for my internet connection error at the last minute! i couldn't submit it!
by the way, Thank you, scott_wu and abacadaea, for this beautiful problems with cows and farmer John!
First, I got the standard message, that the contest is over. But I didn't send some solution in time, so I entered the contest once again and sent the solution just to check if it was correct (as in 'practice').
And now I see it was sent on 02:04:28 and it was (pre)accepted for judging.
Nice try!
Amazing round ! The problems is interesting :)... But I made a silly mistake again in Problem C...sad >_<
Большое спасибо авторам за задачу A DIV 2 — познавательно!
А как она решается то?
Да втупую решается, перебором всех x и всех степеней x.
http://e-maxx.ru/algo/primitive_root пункт "Связь с функцией Эйлера"
Есть и аналитическое решение: wiki
Да — так и решил)))
Probably, first round, when I send solution for A just before contest ends. Thank you for great tasks!
[284C]
Why this generator gives Invalid Input? Please give me a hint. Thanks :)
ignore it
here is one cycle with
<and one with<=There's no problem, he made n equals 199999 and outputs 199999 lines then
UPD: Sorry, I thought you want to say, that he's checker is uncorrect, but you answered to guy thought like this :) My mistake.
As far as I know , Last line is printing extra "\n". So if you could change that, it will be fine.
what's validator comment?
It's
FAIL Input can't contain chars with codes less than 32, but line 5 (1-based) contains [validator wfval.exe returns exit code 3].i had the same problem. you must swap 2 and 3 integers there: for(int i=1; i<=100000; i++) printf("1 !99999 !1\n");
.
if(Div.2)
dont try to steal my idea
sorry, i didn't see your comment.
lol now i got -40 contribution. i love this people.
... My solution for B(the easiest one) failed because of char mass[100000] instead of char mass[200000] :/ And I was late a little to submit C :/
у двух человек полностью одинаковые решения по 3-м задачам
lawliet_djez : A — 3338474, B — 3334615, C — 3341327.
metalopocalipsis : A — 3338366, B — 3334502, C — 3338081.
Thanks for fast editorial ! Great !
During the contest I didn't read the message about the contest duration had been increased by 5 minutes and I wasn't refreshing my browser after the message had been announced, then on my browser the contest was ended 5 minutes earlier, 2-3 minutes later I had finished my solution for problem A and I didn't submitted my solution because I thought the contest was over :(
on the next round I hope the system refreshing all contestant's browser automatically after the message has been announced
there's no way the browser could detect if new message was announced, except it was already refresh it every time, or doing it in background
http://www.codeforces.com/contest/284/submission/3335241 and http://www.codeforces.com/contest/284/submission/3334788 are 'quite' similar...
Purely a coincidence xD
they are really similar lol xD
Good!!but what we can do for it!!!
Как все С (div 2) ломали??
Вероятно, TLE
Выше говорят, что на переполнении
Thanks a lot for the editorial just after the contest!
http://codeforces.me/contest/283/submission/3339789 в чем ошибка, скажите, пожалуйстаа
In case 3, you also have to set change[sz(v) — 1] to 0, otherwise when you add new elements after removing some old ones, the old value of change entry will fuck up your result. This is how my initial solution got hacked.
And int overflow.
int sum = 0;:(Переполнение типа int
poor system test!
Can someone please help.I was unable to pass the pretests for div 2 problem C . Here is my code. I tried it with segment tree. I'm not experienced with segment tree. I've only used them once or twice.This code got WA in pretest 9.
Amazing round, cool tasks, like it. Thanks guys :)
Sad...I learnt a lesson from this round that I should be more confident..I worked out Div1.D at about 00:15 after the beginning of the contest,but I could't make decision to submit my code because I just think it's impossible for me to solve Div1.D in only 15min..So I stupidly did nothing but waited for someone who would solve it,and it's rng_58 at 00:34,then I followed him and got AC...What a stupid I am huh?
You should think like this and submit: "I'll just submit to make sure it fail pretest so that I can focus on other problems"
It doesn't make a sense. What was the point of waiting for somebody who submit the task first? It would be better if you didn't submit it at all.
I haven't participated for a while. Can someone please tell me what is "bestRatingChanges"? Is it a new feature?
Can someone explain the solution for Div1 D Can't understand from the editorial
Have you checked this one http://codeforces.me/blog/entry/7037? Which part do you feel confused?
Damn... :( Can somebody share 4 more points with me...? :D
The next contest is div2 only, anyway. You can gain even more points if you participate in it, get a rating increase and then in participate in the next div1 contest, than if you actually got the 4 more points now and skipped the next div2 contest :D
Yes, you are right! But I can't participate in the next round. It's our New Year ceremony in Iran! :)
http://codeforces.me/contest/283/submission/3345114 interesting, why does this solution fail on memory? I think I have constant (but big) memory.
I think this is the reason:
int N = 20000+1;So 20000*(small constant) is not close to 262 MB. And N is a constant, why does it fail only on the 9'th test and not earlier?
The problem is that your array is not enough. So when your code runs a large test, there may be some unexpected issues in the recursion and it somehow won't terminate. And when the recursion keeps going on, your memory will exceed the limit.
Hm, thanks, but anyway I don't understand. Why doesn't it fail if I'm indexing out of my array; is it adding more memory by itself? haven't heard about similar never before; Also I don't see any bugs in my code, do you?
The recursion consumes memory itself since you have to store all the variables of the recursion.
This simple program also runs out of memory (you can try it in "Custom test")
`
void go(int x, int y, int z, int t) { if (x == 10000000) return; go(x + 1, y + 1, z + 1, t + 1); }
int main() { go(1, 2, 3, 4); }`
Thanks, I just understood you incorrectly the first time, of course I know recusion consumes memory.
Not only the problems were perfect... you have also published tutorials in few minutes... fantastic :)
Does someone know why this solution failed precision check? Does that mean that the sum is wrong and is there a way to download the test?
I would try
bit.update(size - 1, -bit.total(size - 1));EDIT: sorry, it won't work
I figured it out, should be like this:
Can anyone tell why my solution for Problem C Division 2 is gave WA. http://www.codeforces.com/contest/284/submission/3336215
you need set a and b to zero on delete
http://codeforces.me/contest/284/submission/3345657
http://codeforces.me/blog/entry/7027#comment-126522
could someone post the test no 10 or help to figure out why my solution on C Div2 fails on test no 10 ?
Yeah~ think my English is very poor ,not you in your problems' discribe.In pro B(div.2),I readed it again again again and again...I dont know what you want to say,I translated it in a variety of dirctions,but when I see the sample input&output,I thought im wrong...
The problems are interesting, it's good to see cows and Bessie again!
it there anything wrong with the checker of div.1 problem A?
http://codeforces.me/contest/283/submission/3331170
i just cannot figure out what's wrong with my submissions, while the checker said "Checker comment wrong output format Extra information in the output file"
It seems that N, the size of your array, is a little too small. The sequence starts with one element, so it can have up to 200001 elements total.
I've changed N to 200001 in your code and gotten AC here: http://www.codeforces.com/contest/283/submission/3347718
thank you!
your problemset is really nice, though i have made a lot of mistake like this.
hope for your next excellent round!
could you post somewhere test no. 10 for C Div2 problem? My solution still fails on it. :(
Why my actual rank for Round174_div2 is different from the rank that appears on my profile? One shows #5: http://codeforces.me/contest/284/standings One shows #7: http://codeforces.me/contests/with/lxfind There might not be a big difference, but which one leads to the new rating?
My submission for Div.2 C, is giving WA on test 10's 103363rd number due to precision error :(
Print as many numbers as possible! I use printf("%.15lf") ..
What a great contest ! I would like to say thank you to figure out my mistake! Expecting you can get great contest later~
I think I have a similar but more comfortable solution for Div.1 D.It depends on this property:
If a[i] has been determined,and a[i-1] should be replaced,then we can optimize a[i-1] that:
Proof:
If a[i] is even,k = a[i] / 2,then a[i - 1] = (2p + 1)k, a[i - 2] = a[i - 1] * (a[i - 1] + 2q - 1) / 2.
Then let r = 2p2k + pk + 2pq - p + pk + q,which is always a integer.
a[i-2]=k(k+2r-1)/2.So a[i-1]=a[i]/2 is better than any other a[i-1].
If a[i] is odd,k = a[i],then a[i - 1] = pk, a[i - 2] = a[i - 1] * (a[i - 1] + 2q - 1) / 2.
Then let
,which is always a integer.
a[i-2]=k(k+2r-1)/2.So a[i-1]=a[i] is better than any other a[i-1].
Using this property,we can calculate dp[i] with simply enumerating j from i-1 to 0.
There are many formulas.Although it's very natural to guess it's correct.The code 3335280 is easy to understand.
А почему не делается разбор на русском языке?
Вообще-то всегда сначала делается разбор на английском, он же более распространен среди участников.
Просто я как бы сижу на русском сайте, и мне хотелось бы читать разбор на русском.
А в жизни не всегда все так, как нам хочется, да. И, кстати, в вашем возрасте вполне можно знать английский хотя бы на среднем уровне, ага.
Вы не понимаете. Дело не в знание ангийского а в том, что здесь сидит куча школьников, которые не знают еще английского, но им хотелось бы почитать разбор. Но они не могут этого сделать
Разбор на русском будет.
Прочтите внимательно мой первый ответ. Там написано : "**сначала** делается разбор на английском". ок?
ок. Просто я, например, не видел разбор на русском для предидущего контеста div2
китайцы же :)
))
Чтение тектов(в данном случае — разборов) на английском языке будет отличным подспорьем для этой "кучи школьников". Без знания английского сейчас никуда.
Но здесь Вы возможно правы.
I think the data of div1 A have some problem! If it comes ti = 1 many people add ai * xi directly but actually there have a date's ai > the length of the current sequence. look my submit 3350410 3350482
I don't see any mistake in testdata 10 which your submit 3350410 get WA, can you tell more?
maybe the mistake like this: 1 1 3 1
so the ac code will give 3 but I think it should be 1
I should go back to learn English....
div1 problem D how to prove that : if( j-i-1 < m2[j] ) then there aren't any cool sequence begins with a[i],ends a[j]
I saw the editorial for A in DIV1 but still got wrong on test 10, what's wrong ?3352082
you should updating add[last] = 0 after removing last element of the sequence
i think that you forget to set add[last] = 0 in case choose == 3.
it liked usacos problems..... But at the and of the contest was balk and finaly i hadnt time to hack :(
My solution Link , I don't know why i WA in test 5, I pass this test in the same code but submis in systems WA. :|