Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

scott_wu's blog

By scott_wu, 7 years ago, ,

Hello everyone! Codeforces Round 174 will be held for both divisions on Sunday, March 17th at 7:30 PM MSK. The problem setters are abacadaea and me (scott_wu). We would like to thank Gerald for his help in preparing the contest and Delinur for translating the problems. We also thank MikeMirzayanov for creating such an awesome site. We are very excited as this is our first Codeforces round.

For this contest you’ll be helping Farmer John, Bessie, and the cows. We hope you enjoy the problems! :)

The score distribution will be slightly nonstandard.

Div2 — 500 — 1000 — 2000 — 2000 — 2500

Div1 — 1000 — 1000 — 1500 — 2000 — 2500

Good luck and happy coding! As always, to make the round more exciting, we recommend that you take a look at all the problems!

UPD: Our editorial can be found here. Thanks for participating!

Congratulations to the winners:

Div1

Div2

• +323

 » 7 years ago, # |   +76 It's like USACO only with faster results! :)
• »
»
7 years ago, # ^ |
-26

Hi

 » 7 years ago, # |   +85 Wow, finally some Americans.
•  » » 7 years ago, # ^ |   -14 really))
•  » » 7 years ago, # ^ |   -8 The moment I saw FJ's name I said it should be Americans :D
 » 7 years ago, # | ← Rev. 3 →   +4 ... There are two 2000 in DIV 1 ! ...... Maybe I should think twice before decide which one should be attacked first ... )
•  » » 7 years ago, # ^ |   +15 ...There is only one 2000 in DIV 1 !......there are two 1000 in DIV 1 !......Good Luck!... )
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +36 There must be some trouble with my eyes .. /w\. I'd better go to bed now...
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   -24 -_-
•  » » » » 7 years ago, # ^ |   -13 But, you're already red now...
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +29 ... But I want to become a IGM .... ... )
 » 7 years ago, # |   +9 Will Фермер Джон and his N коров (1 <= N <= 100,000) make an appearance?
•  » » 7 years ago, # ^ |   +37 There is no cow level.
•  » » » 7 years ago, # ^ |   +18 Like!! «Che Haali mide inja benevisi bad ina nafahman o kolli beshun bekhandi :D»
 » 7 years ago, # | ← Rev. 2 →   -22 .
•  » » 7 years ago, # ^ |   +34 I just wanted to see how my avatar looks in the comments.
•  » » » 7 years ago, # ^ |   +2 Really nice!!!
 » 7 years ago, # |   +39 we always see beautiful problems in USACO contests.I hope we have beautiful and interesting problems in the first usaco-like code forces round !
•  » » 7 years ago, # ^ |   +2 But not very difficult like USACO 8-))
 » 7 years ago, # |   +6 Good to see Bessie and the cows invading the world of algorithms !
 » 7 years ago, # |   +2 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.com/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,
•  » » » 7 years ago, # ^ |   -9 I wanted to but I don't know how to email the administrator but I cannot find the links. Do you know the administrator's password?
 » 7 years ago, # |   -18 date_of_today++;
 » 7 years ago, # | ← Rev. 2 →   -9 pretty good! Good luck to everybody.
 » 7 years ago, # |   +42 many coders from various countries have been holding contests;great!and I wonder Bessie the cow and John the farmer will cause problems again :)
 » 7 years ago, # |   -7 Counting both Div1 & Div2 , there are One 500 , Three 1000s , One 1500 , Three 2000s but Two 2500s break the sequence :)
 » 7 years ago, # |   +24 Wish I can be red after this contest! I will do my best to help Farmer John to handle his cows!
 » 7 years ago, # |   +1 My time to be pink coder :)
•  » » 7 years ago, # ^ |   +28 But I think it looks like purple more than pink ~>_<~
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +10 I think it will be better to mix both of them (purple and pink) to get Candidate Master's color).
•  » » » 7 years ago, # ^ |   +5 i think it mix of both !!
•  » » » 7 years ago, # ^ |   +14 How about :My time to be rgb(170, 0, 170) coder :)
 » 7 years ago, # |   +24 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 ??).
•  » » 7 years ago, # ^ |   +11 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.
 » 7 years ago, # |   -6 Wow, its good.. everyone likes usaco problems and fermer John... So i wish everybody luck :D
•  » » 7 years ago, # ^ |   -13 fermer?maybe farmer =D? Good luck, we will help you Mr. John!!!
•  » » » 7 years ago, # ^ |   -6 oh sorry, its Technical error :D
•  » » » » 7 years ago, # ^ |   -7 Lol, you get Technical error and '+' , i found you error and get '-', nice community -_-
 » 7 years ago, # |   +53 will I have to insert "USER,LANG,PROB" headers in my code? :))
•  » » 7 years ago, # ^ |   0 Will you have to do this same in usaco contest ? :))
•  » » 7 years ago, # ^ |   +7 No USER it's ID.
•  » » 7 years ago, # ^ |   0 and I really did it, just in case I need them :)))http://codeforces.com/contest/283/submission/3334424
 » 7 years ago, # | ← Rev. 2 →   0 ... There are two 2000 in DIV 2 ! ... ...Good Luck!... )
 » 7 years ago, # |   -13 It will be produced in usaco's difficulty problems?
 » 7 years ago, # |   0 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. :)
 » 7 years ago, # |   -11 В двух предыдущих раундах div 2, задачи "A" были очень легкие и интереса особого небыло их решать. Надеемся тут будут интересные задачи... Спасибо!
•  » » 7 years ago, # ^ |   0 Если ты не заметил , задачи А всегда лёгкие и соответственно особого интереса не вызывают.
•  » » » 7 years ago, # ^ |   -6 По сравнению с остальными они очень легкие, задачи состояла в том что надо считать сроку и вывести ее, только сменить первый регистр символа.
•  » » » » 7 years ago, # ^ |   0 Сейчас задача А не очень лёгкая...Накаркал...
 » 7 years ago, # |   +11 Farmer John? I think I'll back to blue...
 » 7 years ago, # |   -8 memeda
 » 7 years ago, # |   -8 Nice and exciting contest, cute problems! I'm so sad because i couldn't register for it :((
 » 7 years ago, # |   +1 I think they mixed up A and B))Я думаю они перепутали местами А и В))
 » 7 years ago, # |   +8 Someone else having problem to hack ?
•  » » 7 years ago, # ^ |   0 Yep. I've found countertest for my own solution but I can't hack myself! :D
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +12 Why i cant hack?Can't process your hack, try again
•  » » 7 years ago, # ^ | ← Rev. 3 →   +7 In 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 :(
•  » » » 7 years ago, # ^ |   +2 I hacked 4 solutions(with TLE too :)) without any problems.
•  » » » » 7 years ago, # ^ |   +11 You are not in my room!
•  » » » » » 7 years ago, # ^ |   0 I just tried to say what I had no problems when hacks solutions. I think, you should write letter to administration.
•  » » » » » » 7 years ago, # ^ |   0 :) i just send message but they wrote me "Write you own generator and submit it."
•  » » » » » » » 7 years ago, # ^ |   0 Maybe a pro in your browser
 » 7 years ago, # |   -9 Finally see Americans set the problems, good job. Problems in the last contest are way too sophiscated, and this time the problems are beautiful.
 » 7 years ago, # |   +13 I was thinking why codeforces is still in Beta version, Now I know the reason "504 Gateway Time-out".
 » 7 years ago, # |   0 I was seconds late to submit B :(
 » 7 years ago, # | ← Rev. 2 →   +37 Not this time wjmsbmr
 » 7 years ago, # |   +2 Thank you for very interesting problems.
 » 7 years ago, # |   +10 Looks like we beat the USACO results :)
 » 7 years ago, # |   +1 Haven't xperienced too hard DIV-2 A before :\
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +38 Now you can see wjmsbmr is not me LOL.
•  » » 7 years ago, # ^ |   +30 Unless...
•  » » 7 years ago, # ^ |   -10 who said it is U???~~~
 » 7 years ago, # |   -45 Strongly suggest unrated
•  » » 7 years ago, # ^ |   +105 I can promise you not only unrated round, but more! You will be banned soon because of unfair play.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +31 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 ??)
•  » » » » 7 years ago, # ^ |   -17 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.
•  » » » » » 7 years ago, # ^ |   +8 i think you got '-' because you reported it.
•  » » » » » 7 years ago, # ^ |   0 Where have you seen that Mike has tagged any name? He simply answered to a person who cheated, and furthermore tried to make stupid the authors.
•  » » » 7 years ago, # ^ |   +11 What has he done?
•  » » 7 years ago, # ^ |   +7 Sorry for my interest, but can someone tell me why (s)he (Troy1118) is going to be banned ? Which rule did (s)he break ?
 » 7 years ago, # |   0 wow you guys :D amazing round. Haven't had this much fun in a long time (except for the part when the site was down, that was scary!! )
 » 7 years ago, # |   0 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!
 » 7 years ago, # |   +10 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!
 » 7 years ago, # |   +23 Amazing round ! The problems is interesting :)... But I made a silly mistake again in Problem C...sad >_<
 » 7 years ago, # |   +1 Probably, first round, when I send solution for A just before contest ends. Thank you for great tasks!
 » 7 years ago, # | ← Rev. 4 →   +4 [284C] #include int main() { printf("199999\n"); for(int i=1; i<100000; i++) printf("2 1\n"); for(int i=1; i<=100000; i++) printf("1 99999 1\n"); return 0; } Why this generator gives Invalid Input? Please give me a hint. Thanks :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   -12 ignore it
•  » » » 7 years ago, # ^ |   0 here is one cycle with < and one with <=
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 There's no problem, he made n equals 199999 and outputs 199999 lines thenUPD: Sorry, I thought you want to say, that he's checker is uncorrect, but you answered to guy thought like this :) My mistake.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 As far as I know , Last line is printing extra "\n". So if you could change that, it will be fine.
•  » » 7 years ago, # ^ |   0 what's validator comment?
•  » » » 7 years ago, # ^ |   0 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].
•  » » 7 years ago, # ^ |   0 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");
•  » » 7 years ago, # ^ | ← Rev. 2 →   +7 .
 » 7 years ago, # |   +13 if(Div.2) swap(A,B)
•  » » 7 years ago, # ^ |   0 And then swap(B,C); I think that dynamic score system will be better in this round.
•  » » 7 years ago, # ^ |   -16 dont try to steal my idea
•  » » » 7 years ago, # ^ |   0 sorry, i didn't see your comment.
•  » » » » 7 years ago, # ^ |   +9 lol now i got -40 contribution. i love this people.
 » 7 years ago, # |   +1 ... 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 :/
 » 7 years ago, # |   +11 Thanks for fast editorial ! Great !
 » 7 years ago, # | ← Rev. 5 →   +8 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
•  » » 7 years ago, # ^ |   0 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
 » 7 years ago, # |   +29
•  » » 7 years ago, # ^ |   +2 Purely a coincidence xD
•  » » 7 years ago, # ^ |   0 they are really similar lol xD
•  » » 7 years ago, # ^ |   0 Good!!but what we can do for it!!!
 » 7 years ago, # |   +14 Thanks a lot for the editorial just after the contest!
 » 7 years ago, # |   +2 http://codeforces.ru/contest/283/submission/3339789 в чем ошибка, скажите, пожалуйстаа
•  » » 7 years ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 7 years ago, # ^ |   0 int sum = 0; :(
•  » » 7 years ago, # ^ |   -11 Переполнение типа int
 » 7 years ago, # |   +8 poor system test!
 » 7 years ago, # |   +1 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.
 » 7 years ago, # |   0 Amazing round, cool tasks, like it. Thanks guys :)
 » 7 years ago, # |   +39 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?
•  » » 7 years ago, # ^ |   +16 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"
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # | ← Rev. 2 →   +9 I haven't participated for a while. Can someone please tell me what is "bestRatingChanges"? Is it a new feature?
 » 7 years ago, # |   0 Can someone explain the solution for Div1 D Can't understand from the editorial
•  » » 7 years ago, # ^ |   0 Have you checked this one http://codeforces.com/blog/entry/7037? Which part do you feel confused?
 » 7 years ago, # |   +3 Damn... :( Can somebody share 4 more points with me...? :D
•  » » 7 years ago, # ^ |   +3 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
•  » » » 7 years ago, # ^ |   +1 Yes, you are right! But I can't participate in the next round. It's our New Year ceremony in Iran! :)
 » 7 years ago, # |   0 http://codeforces.ru/contest/283/submission/3345114 interesting, why does this solution fail on memory? I think I have constant (but big) memory.
•  » » 7 years ago, # ^ |   0 I think this is the reason:int N = 20000+1;
•  » » » 7 years ago, # ^ |   0 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?
•  » » » » 7 years ago, # ^ | ← Rev. 5 →   0 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.
•  » » » » » 7 years ago, # ^ |   0 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?
•  » » » » » » 7 years ago, # ^ | ← Rev. 5 →   0 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); }
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +7 Thanks, I just understood you incorrectly the first time, of course I know recusion consumes memory.
 » 7 years ago, # |   +16 Not only the problems were perfect... you have also published tutorials in few minutes... fantastic :)
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 sum -= bit.total(size - 1); bit.update(size, -bit.total(size)); --size; I would try bit.update(size - 1, -bit.total(size - 1));EDIT: sorry, it won't work
•  » » » 7 years ago, # ^ |   0 I figured it out, should be like this: ll d = bit.total(size - 1); sum -= d; bit.update(size - 1, -d); bit.update(size, d); --size; 
 » 7 years ago, # |   0 Can anyone tell why my solution for Problem C Division 2 is gave WA. http://www.codeforces.com/contest/284/submission/3336215
•  » » 7 years ago, # ^ |   +1 you need set a and b to zero on deletehttp://codeforces.ru/contest/284/submission/3345657
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   0 could someone post the test no 10 or help to figure out why my solution on C Div2 fails on test no 10 ?
 » 7 years ago, # |   0 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...
 » 7 years ago, # |   +6 The problems are interesting, it's good to see cows and Bessie again!
 » 7 years ago, # |   +2 it there anything wrong with the checker of div.1 problem A? http://codeforces.com/contest/283/submission/3331170i 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"
•  » » 7 years ago, # ^ |   +3 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
•  » » » 7 years ago, # ^ |   +3 thank you!your problemset is really nice, though i have made a lot of mistake like this. hope for your next excellent round!
•  » » » 7 years ago, # ^ |   0 could you post somewhere test no. 10 for C Div2 problem? My solution still fails on it. :(
 » 7 years ago, # |   +5 Why my actual rank for Round174_div2 is different from the rank that appears on my profile? One shows #5: http://codeforces.com/contest/284/standings One shows #7: http://codeforces.com/contests/with/lxfind There might not be a big difference, but which one leads to the new rating?
 » 7 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/284/submission/3342708http://ideone.com/qeAYLVwhy does my code not print anything on codeforces?
 » 7 years ago, # |   0 My submission for Div.2 C, is giving WA on test 10's 103363rd number due to precision error :(
•  » » 7 years ago, # ^ |   0 Print as many numbers as possible! I use printf("%.15lf") ..
 » 7 years ago, # |   0 What a great contest ! I would like to say thank you to figure out my mistake! Expecting you can get great contest later~
 » 7 years ago, # | ← Rev. 2 →   +8 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 = 2p 2 k + 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.
 » 7 years ago, # | ← Rev. 3 →   0 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
•  » » 7 years ago, # ^ |   0 I don't see any mistake in testdata 10 which your submit 3350410 get WA, can you tell more?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 maybe the mistake like this: 1 1 3 1so the ac code will give 3 but I think it should be 1I should go back to learn English....
 » 7 years ago, # |   0 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]
 » 7 years ago, # |   0 I saw the editorial for A in DIV1 but still got wrong on test 10, what's wrong ?3352082
•  » » 7 years ago, # ^ |   0 you should updating add[last] = 0 after removing last element of the sequence
•  » » 7 years ago, # ^ |   0 i think that you forget to set add[last] = 0 in case choose == 3.
 » 7 years ago, # |   +5 it liked usacos problems..... But at the and of the contest was balk and finaly i hadnt time to hack :(
 » 7 years ago, # |   0 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. :|