Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### gen's blog

By gen, 6 years ago, ,

Hello everyone!

Codeforces round #238 will start today at 19:30 in Moscow time. The round will be held in both divisions.

The round was prepared by me and cfk. This is the 4th round for me and the 2nd for Krisjanis. I think the problems this time are rather unusual and maybe even surprising. We have no doubt that everyone will find a problem that suits their taste! But you have to find it. (:

As always, thanks to Mikhail Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems, and Maria Belova (Delinur) for translating the statements. Big thanks to Gerald Agapov (Gerald) for helping in preparation of the contest. Me and Gerald had a chance to talk about the problems onsite during the Petrozavodsk winter camp, which I think was very productive.

We wish you a very exciting round!

UPD1: Score distribution:

DivI: 500 1000 2000 2000 2500

DivII: 500 1000 1500 2000 3000

The scoring for the problems is relative, so that the cost of each problem would be a multiple of 500 and closer to the objective estimate. Don't be afraid, the problems are not really that hard. (:

UPD2: Congratulations to the winners!

#### DivII:

UPD3: Excellent round statistics from DmitriyH.

UPD4: The contest tutorial is published here.

• +402

 » 6 years ago, # |   +27 "Problems will be unusual and surprising". Hmmm... Sounds interesting. Good luck to everybody...!!!
•  » » 6 years ago, # ^ |   -8 haha,friend,You are very speedy.
•  » » » 6 years ago, # ^ |   +1 haha,friend,You are very smarty -_-
•  » » » 6 years ago, # ^ |   0 chinese? Because your photograph is Big Big Wolf~ :) Chinese Characteristics~
 » 6 years ago, # |   +6 First Contest in Iran's New year and unusuall problems!! Great!!
 » 6 years ago, # | ← Rev. 3 →   -9 Today in Kazakhstan is New Year(Nauryz). I will solve problems with meat and kumys. Good luck for everybody!!!
 » 6 years ago, # |   +13 Every contest anybody has new year and should write about it. It's sooo interesting for us!
•  » » 6 years ago, # ^ |   -13 No, hardly every contest. Count contests per year and think: could there really be so many existing calendars?
 » 6 years ago, # |   0 On this round I wish all high ranking.
•  » » 6 years ago, # ^ |   +2 what about other rounds you still wish same thing
•  » » » 6 years ago, # ^ |   +16 Not to mention his "wish" is impossible because everyone can't get high ranking. Unless almost nobody solves anything.
•  » » » » 6 years ago, # ^ |   0 or all solve problems with same final score with probability 0.0000000000000000000000000000000000000000000001
•  » » » 6 years ago, # ^ |   +6 Please don't in those little details
 » 6 years ago, # |   -8 wish all participants a very happy Match ^_^
 » 6 years ago, # |   0 This round will be even unusual and surprising for me, if my solution of Problem-C gets AC and fails system test of Problem-A :)
•  » » 6 years ago, # ^ |   +5 Since you know that, so it won't be surprising ;)
 » 6 years ago, # |   +13 Hi all, wanted to ask a simple query. How to find name of blogs in a tabled manner, In the right panel titled "Recent Actions", If I click on detailed, I can see comments of people over different blogs, But I dont want that. I want to see more number of blogs similar to ones shown in that panel itself. Eg. I would like to see around 30 entry per page for Recent actions, Is the any such option available somewhere on codeforces?
 » 6 years ago, # | ← Rev. 2 →   +36 My first D1 round. So exited :O #mlc
 » 6 years ago, # |   +7 E is 3000 seems that opening it during contest time is useless :D
 » 6 years ago, # |   +20 Loving the pretty pictures.
 » 6 years ago, # |   +22 Thanks for the contest I really really enjoyed C in DIV2 ;-) It's amazing problem !!!
•  » » 6 years ago, # ^ |   +5 I was going into BIT ideas, Then I thought that why is GF(2) given, find solution was really cute =D
•  » » 6 years ago, # ^ |   +48 Div1-A/Div2-C, aka "how to solve a problem while ignoring over half of the input". Pretty nice :P
 » 6 years ago, # |   +23 Awesome problems. I really enjoyed solving C and D. Thanks for the contest.
 » 6 years ago, # |   +18 Haha, I spent most of time on problem C and didn't solve it. :( Good contest though.
•  » » 6 years ago, # ^ |   +2 Ok, i just solved it.
 » 6 years ago, # |   +11 Very nice problemset, I found my problem! It was Div1 C :)
 » 6 years ago, # | ← Rev. 3 →   +3 Nice contest, the pretty complicated at first Div1 A turned out to be awsome. What was the main idea behind D? I used a stack and LCA, but got WA. I imagined that the stack part was wrong, but couldn't find any counterexample after looking for it 10 minutes. Do you have one? (I would like to add that the stack used line intesections, not just simple comparisons)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Stack works when you can't see a hill again after removing it, which doesn't work in this case.The LCA is correct (that's pretty easy to see). To find the next hill a climber goes to from hill i, you add the points from right to left, remember the top convex hull (well, it's actually a concave curve, but it uses the same idea as convex hull algorithm) of these points, update it when adding points and always pick the leftmost point in the hull so far (after the just added point, from which the climbers go to the next point of the hull). This can be done using vector cross product — as long as the leftmost 2 points of the hull (if they exist) are placed in such a way that the leftmost one is below the line from the just being added point to the one to its right, you remove the leftmost point of the hull — because it won't be in the top convex curve ever again. It works the same way as the standard convex hull algorithm.Another contest where D appears simpler than C. At least to those who are used to more algorithmic problems — like me :D. Too bad I missed the start of the contest (thanks to the modern world's stupid shopping obsession), I think I could've done well.
•  » » » 6 years ago, # ^ | ← Rev. 8 →   0 Thanks a lot for the pointers, In order to understand why my stack is not right, do you have a small handly counterexemple? thanks.Edit: I tried to build a counterexample like this:  | | | | | | | | | | 1 2 3 4 (In reversed order, from right to left) On an exemple like this, my stack alg runs as follows: Push 1 make_edge(1,2) (i will not write these from now on) Push 2 try to pop the stack -> verify whether or not line segment 1 3 passes through hill 2 -> no -> no pop Push 3 try to pop the stack -> 2 4 is above 3, so we pop the stack try to pop the stack -> 4 1 is above 2, so we pop the stack (make edge 1,4) Push 4 And now we have our tree, on which we apply a LCA algorithm.
•  » » » » 6 years ago, # ^ |   0 Depends on the exact approach. Just be satisfied with the general guideline that stack is useful if you're sure that you can't use a discarded element again. In this case, it fails because heights of hills can vary greatly — you can discard and use again any hill many times.If you want a good counterexample, you can always look for it yourself — try the case that gives WA; if it's too large, try generating your own and comparing against AC solutions, etc etc.
•  » » » » » 6 years ago, # ^ | ← Rev. 9 →   0 I edited my approach ^, I also corrected a few small mistakes and got ACC. Please note that my stack pop criterion is geometry heavy, something like if(((1ll*stack[poz].x-stack[poz-1].x)*(1ll*v[i].h-stack[poz-1].h))<((1ll*stack[poz].h — 1ll*stack[poz-1].h)*(1ll*v[i].x-1ll*stack[poz-1].x))) No need to try to understand the formulas, all I did was to check if a segment intersects another.
•  » » » » » » 6 years ago, # ^ |   +1 It could quite possibly be the same thing I was talking about. (Convex hull can as well be implemented with stack.) I just expect an algorithm that's called just "stack" to have storing the hills on a stack to be the most complex idea in it :D
 » 6 years ago, # | ← Rev. 2 →   0 My best performance in cf ever(Div2 5th place wink). Thanks a lot for the mathy contest :D
•  » » 6 years ago, # ^ |   +1 And I am probably going to fall at my lowest rating in the last 2 years or so. Last two contests have been miserable for me. Making a lot of silly mistakes, I dont know what has happened. :( T_T . But both of these contest had very exciting problems.
 » 6 years ago, # |   +12 Nice contest! Interesting and solvable problem :)
 » 6 years ago, # |   -9 Объясните, пожалуйста, популярно, почему каждый флип меняет парность ответа?
•  » » 6 years ago, # ^ |   -11 раскрой скобки в выражениитам получится что ответом является сумма произведений диагональных элементов
•  » » » 6 years ago, # ^ |   -8 аааа, тьфууу.. вот дурак.. Заметил, что каждый два раза, но протупил выбрасывть их.. спасибо
•  » » » 6 years ago, # ^ |   -7 А если точнее, то просто сумма диагональных элементов. А каждый флип просто инкрементит ответ.
 » 6 years ago, # |   +1 I got TLE in Div1 A on pretest 7. I had used cin cout with ios::sync_with_stdio(false). Until now I used to think that this method is faster than scanf printf. But when I changed this to scanf printf , the code was accepted. What is the reason for this?
•  » » 6 years ago, # ^ |   +2 cin/cout does usually works longer than printf/scanf...use read/write instead!
•  » » 6 years ago, # ^ |   +14 Each operation on cin flushes cout by default. Use cin.tie(NULL); to prevent this.
•  » » » 6 years ago, # ^ |   0 Are #define endl '\n' and ios :: sync_with_stdio(false) enough?
•  » » » » 6 years ago, # ^ |   +5 Together with cin.tie(NULL); this is probably about all you can do to speed up iostreams.Also with std::strings it helps to .reserve() the maximum number of characters before inputting a string, and to reuse the same string object if possible: string s; s.reserve(100005); for (int i = 0; i < n; i++) { cin >> s; // do something } 
•  » » » » » 6 years ago, # ^ |   0 Not just with strings. If you have a vector<> which you construct by adding elements (my implementation of interval trees, for instance), .reserve() can cut down on time and memory nicely.Note a line in my template: #define dibs reserve :D
 » 6 years ago, # |   0 Very nice problem :) it's really surprising !-.- but I late to realize that
 » 6 years ago, # |   -23 А можно еще попросить, объяснить, почему мое решение на А упало? не понимаю :(
 » 6 years ago, # |   +11 Thanks to authors for illustrations! Very helpful!
 » 6 years ago, # |   0 Great Round ! too bad my C couldn't make it through the system tests :D, I realized after that it had a very simpler solution than i thought
 » 6 years ago, # |   +16 Illustrations were so helpful.
 » 6 years ago, # |   +9 when will the ratings be updated?
•  » » 6 years ago, # ^ |   0 Rating updated just now. +26 :p
 » 6 years ago, # |   0 Are people with multiple accounts finally getting deleted in the final standings? Because the unrated guy that finished first is no longer there.
 » 6 years ago, # | ← Rev. 2 →   0 Why the Codeforces Judge Doesnot Give Runtime Error in Situation When Size of array is Smaller than that Required... Rather It gives WRONG ANSWER. In some Judges like spoj WE get RUNTIME ERROR. Got WA on test7 PROBLEM C DIV 2 due to shorter array size,I concentrated on other Bugs rather than Array size which i missed ... so Discouraging
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 global array overflow will not lead to runtime error(if only a little), but local one does. overflowed parts may not be initialized correctly.UPD overflowed 2-dimensional array will get wrong answer. See the implementation of 2d arrays: the i+1-th row is placed right after the i-th row. So if you write overflow data in i-th row the result is the data in i+1-th row is modified.
•  » » 6 years ago, # ^ |   +17 When you do something wrong in C++, you don't get a runtime error. You get undefined behavior, and today you saw one of the many ways how it can behave.
•  » » » 6 years ago, # ^ |   0 You are Exactly Correct I resubmitted the same solution by making the Global array local which was declared shorter than the size required and instead of runtime Error I got Time limit Exceededd id:6118036
 » 6 years ago, # |   +3 When the editorial posted then?
•  » » 6 years ago, # ^ |   +14 The editorial will be posted tomorrow, we are working on it!
•  » » » 6 years ago, # ^ |   +5 Thanks. I'm waiting for it
 » 6 years ago, # |   0 please can any one tell me why the judgement verdict "SKIPPED" is shown ........??
•  » » 6 years ago, # ^ |   0 Its because your Last pretest Passed soloution is system Tested
•  » » 6 years ago, # ^ |   0 Maybe you have copied the solution or commented about the solution outside
 » 6 years ago, # |   0 Thx for contest, I am very happy for my participation, in final I got +163 ratig points) thx a lot
 » 6 years ago, # | ← Rev. 2 →   0 Can someone please help me by pointing out why 6118389 solution fails but 6118249 passes ? (Only difference is the part commented out in the AC solution)The code that has been commented out should have no effect on the final solution, since (X +- (2*Y))%2 is same as X%2 .EDIT : Will not work in if 2*Y > X.
•  » » 6 years ago, # ^ |   0 I had a similar solution which failed on case 50. Weirdly, converting everything to long long got AC.
•  » » » 6 years ago, # ^ |   0 Still WA. there shouldnt be a problem for long long in any case. The maximum value would be 1000*1000
 » 6 years ago, # |   +3 If the result of the judging is Compilation Error, Denial of judgement (or similar) or if the solution didn't pass the first pretest, then this solution won't be considered in calculating results. I take this rule from here Now I ask If this is the only solution I submit it wrong and get wrong answer in the first pretest so it won't be considered in calculating so it doesn't considered as a try so system has to deal with me as out of contest at this moment like the case of you didn't submit anything. Now, why my rate change ?
•  » » 6 years ago, # ^ |   +8 I think this rule only means that there are no penalties for a compilation error or failed on pretest 1 ... However, I think it is quite fair to get your rating changed, cause u actually tried to solve a problem during the contest ...
•  » » » 6 years ago, # ^ |   +8 you are right :)
 » 6 years ago, # | ← Rev. 3 →   +49 Thanks for the round!
•  » » 6 years ago, # ^ |   +39 Maybe it makes sense to integrate your statistics into codeforces instead of creating a blog?
 » 6 years ago, # |   0 first contest and become purple. happy~ >.<
 » 6 years ago, # |   0 Is there a quicker method for console input in java, other than BufferedReader or scanner?seems that using either of them cannot pass problem c in div2?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Just now I translated my code into c++, and I used "scanf" for console input.It passed.
•  » » 6 years ago, # ^ |   0 I used BufferedReader in java (Scanner will not do with 1000000 lines) and it worked perfect.By the way I see no solution with BufferedReader among your 3 submissions.
•  » » » 6 years ago, # ^ |   0 It is here. http://codeforces.com/contest/405/submission/6114625 Did I make some mistakes?
•  » » » » 6 years ago, # ^ |   0 No mistakes, but probably there really are some points to improve: you really need not filling matrix at all — you need only to sum diagonal elements; in matrix filling you also need not do "split" — this creates 1000 small strings 1000 times while you can simply check diagonal character with "charAt"; you was trying do output with System.out.print for each command — I fear this could be slow — try to collect the whole answer string in array or list and after the loop output it with a single "println". For 1000*1000 matrix your two pairs of nested loops will give 10^6 iterations each (and this is not necessary as I've told) so you probably spend significant time in vain and then there remained too few time for printing answer with "print".Check my solution (it is similar except details mentioned): 6111736 — it really takes less than 200ms... So I do not think you need to resort to C, though surely Java is slower :)
•  » » » » » 6 years ago, # ^ |   0 Thank you very much for your suggestion!
•  » » 6 years ago, # ^ |   0 Many Java coders use a self-written FastScanner class or something similar. For implementation details please look at any of my submissions.
•  » » » 6 years ago, # ^ |   0 OK, thank you!
•  » » » 6 years ago, # ^ |   0 i'm not expert, but i dont see what's the difference between ur FastScanner and java.io.BufferedReader. can u please explain the difference? thanks.
•  » » » » 6 years ago, # ^ |   -17 Oh, it seems that you don't know Java at all...Please read about BufferedReader. Then please read about Scanner. Then please understand that FastScanner is a recreation of Scanner's most useful features for competitive programming that works fast (contrary to Scanner). Then you won't ask such stupid questions.
 » 6 years ago, # |   +14 I'm waiting for editorial .thank you
•  » » 6 years ago, # ^ |   0 me too
•  » » » 6 years ago, # ^ |   0 hehe
 » 6 years ago, # |   +2 The tutorial will be tomorrow they said. Wait for it, they said. -_- :DDD
•  » » 6 years ago, # ^ |   +6 Read it, I say now. :)
•  » » 6 years ago, # ^ |   +9 For those, who didn't find it — see the tutorial Here :DD Thanks gen for the excellent round! :)))
 » 6 years ago, # |   +22 Thanks everybody for participating in this round! We would like to hear your thoughts: what did you like very much or not so much? What can we improve in our next round? (Apart from the late tutorial, sorry for that..)
•  » » 6 years ago, # ^ |   +15 The Style and the format of problems were very interesting (especially prob. C and D in div. 2)! I liked the problem statements, they were very clear and easily understandable.Maybe the only thing that I didn't like so much, is that there was little opportunity of hacking someone's solution, maybe for some of us it's good, but I think that passing the pretests almost meant passing the System Testing.But, in general I hope seeing more this kind of rounds here at CF. It can serve as an ideal example for the upcoming contests. We are waiting for other, even more interesting and challenging problems!Thank you for the hard efforts ! :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   +10 I liked that the authors messed with my head in Div1 B/Div2 D by making an example where |X| did not equal |Y| (because one term was 0 and could be omitted), and then writing instead of
•  » » 6 years ago, # ^ |   +5 Thanks for organizing the round. I tried to solve problems A-C in Div1. Problem C was excellent: a "natural" problem and a very clear problem statement. Problems A and B were also interesting, but they were somewhat difficult to understand due to the complex problem statements. In addition, it's not nice when cin and cout are too slow (and warning about this makes the problem statement even longer) — maybe it wouldn't have been necessary to use so large test cases.
•  » » » 6 years ago, # ^ |   +3 Cin and cout aren't too slow if you use the right tricks. (Okay, they are sometimes, but such problems are very rare.) It's not actually an author's obligation to warn about it, and in some problems it even seems unnecessary (200000 integers is hardly an extra large test case) — take it as gen's generousness of sorts :D
•  » » 6 years ago, # ^ |   +6 I think div1 problems (A-D, I don't know how to solve E so far) are really awesome. Thank you for the contest.
•  » » » 6 years ago, # ^ |   0 I found E simpler than C and D. Don't be afraid of it, it isn't hard at all.
•  » » » » 6 years ago, # ^ |   0 Yes, during the contest I try to solve E after a lot vain work on C and D. However it requires more patience which I am lack of. Finally I solve it in the practice.
»
6 years ago, # |
-9

# 239 ?

•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   0 Oh! Lastly, Rested round 239, but I am afraid concerning on this round, so I always miss a new round.