Всем привет!
Приглашаем вас принять участие в Codeforces Round #248, который начнется в субботу 24-го мая в 11:00. Раунд будет проходить в обоих дивизионах. Обратите внимание на крайне нестандартное время проведения раунда.
Задачи были подготовлены zhonghaoxi, wyx528 и мной. Это наш первый раунд Codeforces, надеемся, что он пройдет хорошо.
Большое спасибо Gerald за помощь в подготовке раунда, а также спасибо colin и MSTyoda за тестирование раунда. Традиционно благодарим MikeMirzayanov за создание удобной платформы для проведения соревнований.
В дивизионе 1, это будет 500-1000-1500-2000-3000, в дивизионе 2, это будет 500-1500-1500-2000-2500.
Надеюсь вам понравятся задачи! Желаем вам удачи и удовольствия от решения задач~
Actually, it takes place on Saturday, not Sunday :D
Pity that I won't be able to participate, I have another competition going on at that time. An onsite one... nothing I can do.
Besides that:
Sorry, the time's now fixed.
And nice doge :)
First thanks for preparing this round I know it take a lot of efforts to do problem set for both Divisions
Second why this statement is always written on all the rounds
Score distribution will be published before the contest
or sentences with the same meaning
It seems that the first person wrote this sentence and all follow him without given reason :)
I think while you preparing the problem set you know the position of each problem.
but anyway when you announce the Score distribution a little bit time before the contest it create a something of a curiosity all the time starting from announcing the round till announcing the Score distribution and when we see score distribution we can Rest In Peace.
There is actually a reason... We still have to confirm the difficulty of the problems, to make sure we weren't wrong.
And in my opinion score distribution is only a subjective and relative measurement of difficulty, so it doesn't say much about the actual difficulty of the problems.
But anyway, we apologize for any inconvenience caused, and will try to put up the score distribution ASAP.
Thanks
But score distribution for DIV 2 is not correct. Problem B and C have same points but are solved by approx. 1000 and 60 people.
nice time for me:))
Are huzecong and wyx528 a pair of lovers?>_<
Of course
How do you know that? Are there any differences in these accounts? LOL
you know too much ~
Do Chinese Coders like jokes of this kind?(I've seen several instances). Or they really love each other ?
of course NOT joke
It's a joke... I dunno why though...
233333 >.< ps orzzz
no wonder they are both blushing (in their profile pics)! :D
orzzz... Hoping to see problems without too hard data structures
This post should appear in the home page so everybody can find it easily.
[update] the post is in the home page now, thanks :)
I love contests in that time of day , I wish that this contest will be interesting
Contest kicks off at 8.00 am in my country. Coding is always a good activity to begin your day.
Contest kicks off at 3.00 am in my country. Coding is always a good activity to end your day too ;)
You mean your night :D
Chinese round again~
orzzzzz
marriage!
Nice time for me, Happy to see the problem setter from my hometown :)
happy to see div1.E from your pic!
though maybe no one can solve it ……
This Score distribution not standard :)
At least it's more standard than dynamic distribution :D
3000.. How difficult div1-E will be..
And in my memory, almost all of Chinese round, nobody can solve E during the contest >_<
No 1000-score problem [again]?! Is this a new method of scoring?!
Hope,I can give better look to my rating graph today :D btw,Best of luck ... !!! :)
Kill la Kill, Clannad, Kami-sama hajimemashita, angel beats, kyoukai no kanata, white album :D
You've got 4 out of 6 right :D
there's not me……T_T
nanami & Hajime are from http://zh.moegirl.org/%E5%BC%B9%E4%B8%B8%E8%AE%BA%E7%A0%B42 right?
the last one i really don't know…… maybe Yakushiji Ryouko？
You're right... Ryouko is also from the Danganronpa series, her full name is Otonashi Ryouko.
Chinese again! :(
Why the sad face :)
omg the problem set is harder than Bruce Lee's punch X_X
On the bright side, the system testing should be fast :)
How interesting...
Del
Разве компилятор Microsorf C++ 2010 должен выдавать ошибку компиляции при warning'ах? Все время, пока я его использовал, он спокойно считывал при помощи scanf, а сегодня почему-то выдал CE. Посылка: 6700285
Причем тут scanf?
How to solve A div 1 / C div 2?
I submitted a ternary search.
Consider every page: the best strategy is to merge it to the median of all the page next(in the operation sequence) to it. Choose the best answer. I pass the pretest but I am not sure it can pass all the test.
Can you prove that we should merge it to the median?
The median is the solution to finding a 'center point' when the distance metric is abs. This also counts in multiple dimensions, e.g. if the 2d metric is abs(x0-x1)+abs(y0-y1) etc.
You can prove it by assuming another solution is better and then noticing that moving a bit closer to the median improves the answer. Hence only the median can be optimal.
Consider each of the m numbers in your sequence, what will you safe by changing it to something else?
If the sequence is "1 2 3 3 1 3", 3 is in |2-3|,|3-3|,|3-1|,|1-3| = 5. Hence if we change it to x, we safe 5-(|2-x|+|x-x|+|x-1|+|1-x|). To get the maximum value of the amount saved, just pick x to be the median of 2,1,1.
Now how expensive is this? There are m numbers, each of which could have nearly m neighbours, so is it m^2? No, because we only consider each pair of neighbours twice, so the total running time is O(m) or O(mlogm) if we pick the medians by sorting.
What is the approach to solve Div2 Problem C?
На чем ломали DIV1-A помимо использования set вместо multiset или sorted vector?
Меня взломали из-за того, что я добавлял X в вектор чисел, которые стоят рядом с X
В самом начале нужно заменить все подряд идущих одинаковые числа на единственное.
Не знаю, какое именно решение подразумевается, требующее такой замены, но, по-моему, имеет смысл сделать так со всеми подряд идущими одинаковыми числами.
В самом начале, думаю, имеется ввиду до начала алгоритма.
Решение, которое добавляет "X в вектор чисел, которые стоят рядом с X" (см. комментарий выше) :)
Tricky Div1 A is tricky :'(
Yup. I think a lot of sources at A will not pass...
In DIV1: Passed 232; Failed Systest 75
This was way harder than usual ( at least for me ). Although , very nice problems. Big plus for the authors and waiting for your next contest !
а кстати, в А див 1 кто-нибудь писал тернарник? ну т.е. перебираем число, и для него тернарным поиском ищем оптимальную замену?
Я писал.
I would say that while reading names in the problem statement, It was feeling like playing a tongue twister game. Chinese names are too difficult to pronounce in mind :).
Especially if they are Japanese
I simply replaced them with either 'Jackie Chan' or 'Bruce Lee' in my mind, for simplicity :D
Why not Alice and Bob ? :)
actually they are all characters in Japanese anime or games……
All names in the statements are from Japanese animes... So they're not Chinese names :)
Why my solution got Wrong answer on pretest 2? 6700945 UPD: found error x.x
Tricky contest...
Баг или КФ ко мне сегодня добрый?:)
Два раза пытался перечитать условие C Div1, но текст выглядел для меня примерно как тесты на логику:
Oh, sometimes you're clever enough to be very stupid :(
I used BITs instead of simple partial sums in B and so I've no idea if my code will pass TL. UPD: And it passed! I LOVE CF!!! Anyway, great problems, thank you!
Can you explain a bit about the two solutions?
There's popular Chinese Internet slang that goes "no do no die", which means if you look for trouble then you're definitely in trouble.
This is especially true in competitive programming. It's best to keep solutions simple.
Yeah, I try to do it. Unfortunately, I don't succeed always and that's one of the reasons I fail contests sometimes.
But when it's needed to change elements of an array and calculate sums of its segments the last thing you think about is naive partial sums.)
Click Zan!
Я решал А с помощью n сортировок (сортируем все числа, которые идут вместе с 1<=i<=n числом, берём медиану и пересчитываем значение). Возможно даже зайдет.
Как решали B?
B, по-моему, проще A. По крайней мере, думать надо меньше.
Будем, например, для каждой строки и столбца хранить массив частичных сумм, дабы быстро считать суммы на отрезке.
Первый тип запросов обрабатывается за O(N + M) на запрос тривиально.
Второй делаем так:
Находим длину максимального отрезка из единиц слева и справа от клетки. Потом идем вверх и на каждом шаге сначала обновляем эти длины, а потом релаксируем ответ исходя из них. После этого повторяем то же самое вправо, вниз и влево.
Это вкратце.
Я пытался делать то же самое, только считая длины деревом Фенвика. TL.
На самом деле во время раунда я тоже послал Фенвика (коммент чуть выше) и, хотя оно прошло претесты, наверняка тоже будет TL. Эх..
Можно обойтись одномерным деревом, т.к. при сдвиге указателей можно считать сумму на прямоугольниках размера 1*A или A*1.
Можно решать вообще без деревьев и префиксных сумм, просто будем для каждой ячейки хранить позицию ближайшего нолика с каждой стороны :) Пересчет на запрос будет за 4 * N.
с set-ом зашло за 500мс
How to solve D?
network flow
I'd appreciate some more detailed explanation.
Wait for the Editorial, we will write it there
OMG, I haven't read D during the contest, but now I find it is nearly same with FoxAndCity(DIV1-Hard in SRM590), which was created by me.
You can read the editorial of that task here to find how the graph looks like.
These two problems share a common idea, but I think yours is much harder and more challenging :)
pending system testing ................
Great questions! But super tough! I, for one, am looking forward to the editorial ;)
For the first time, I have to write a test generator for B to make sure that it won't get TLE.
Locked my problem too late, only to find 12 hacked solutions on Div 2 Problem A. What is the highest number of hacks for that problem? Any idea?
I'm sure I'm one of the people with 12 hacks. Not sure whether that's the highest.
At the end of the contest I felt that this contest must not be a usual contest.
When I see the home page I see Chinese writers.
I get the reason ... :)
awesome set of questions... if possible anyone plz explain the approach of Div2-C
http://codeforces.me/contest/433/submission/6692939 Arrays.sort? А что там внутри??
Towards the end of the contest I tried to hack sas4eka's solution for problem A (Div1) by trying to make it get TLE (it seems that for each pair of consecutive positions it iterated through all the occurrences of the first number in the pair, so a test case like N=M=100000 and 1 2 1 2 ...... 1 2 should make his solution get TLE). Since the test case was large, I wrote a generator and wanted to upload the generator (after selecting generated input in the Hacking interface). I selected my generator's source file and then I pressed "Hack". Instead, I got some error that either a test case or the generator must be specified (or something similar). I tries setting some generator parameters and pressed Hack again — nothing happened this time either. Then the contest ended and my hack was not submitted. Perhaps I did something wrong, because I usually do not try to hack other's solutions during the contest and I am not familiar with the Hacking interface. My question then is : can I try to hack other people's solutions outside of a contest ? (just for practice) If not, then how can I become familiar with the Hacking interface so that next time I know what to do? (because it seems that the interface is not as straight-forward as I was expecting it to be). And I would rather not waste time from a real contest for this. Note that in TopCoder it is possible to challenge solutions even in the Practice room, so maybe something similar should also be possible in Codeforces? (in case this is already possible, then please just ignore my question)
Later edit: The solution I was trying to hack did get TLE in the end, so I guess my hack would have been successful... had I known how to properly submit it.
As far as I remember there are two tabs, one for submitting usual test (in text form or by specifying a path to file with a test) and another one for submitting generator (path to generator [and some parameters to pass to generator]). Perhaps, you wrote something in the first form (or had selected file there) before to switch to the generator form.
Hm.. yes, I actually did :) At first I didn't notice the 2 tabs and I selected the generator code where the upload of a test file was. Then I noticed the tab was called "manual tests" (or something similar) and I selected the other tab (for generated input), where I did what I said in my post. I wouldn't have imagined that whatever actions I did in the first tab would still be considered when I switched to the other tab. This is non-intuitive to me and only enhances the idea that one needs to first be sufficiently familiar with the Hacking interface in order to use it properly — which is bad, given that we seem to only be able to access that interface during contests.
Thank you for your answer.
You can practice hacking while participating out of competition in a Div2 contest.
Thank you for your answer. I thought about that myself, too. I think I will do just that in one of the future Div2-only contests. However, if I were a Div2 contestant, that would leave me with no way to practice hacking outside of competition.
Hi, just a friendly reminder that Testing Round will be held today for you to practice hacking solutions. Hope you get notifications for comments :-)
What is up with Time limit exceeded on test 46 for Java solutions on Div2-B ?
If i'm not mistaken, Arrays.sort(a) in Java 7 for primitive types runs in O(N^2) on worst case (quicksort with selecting median as pivot).
Why does Div 2 Problem C have the same point with Problem B? The successful submission rate is 80 to 1066. I once believed points are distributed using the complexity of the problems, I guess not.
Another ironic part is that Problem A with just as many correct submission with Problem B has 500 points.
My opinion is that C has rather difficult algorithm to think of, while B tests you whether you know the proper sorting algorithm for the problem or not. (Note that I didn't solve either and I'm not sure I have the correct algorithm for B; handling the sorted query needs to sort by counting sort?) Both are relatively obscure for an average Div2-er.
Problem B doesn't require any special technique other than understanding cumulative sum. What I did was compute the cumulative sum of the unsorted array, then sort the array and compute its cumulative sum. The rest was just input and output.
For problem C (DIV 2) Only 59 got accepted after system test and for B it is around 1000. Still both have same points. Is there any chance of change in points distribution now?
Cнегопад
loved this contest!! I have now many things to learn in this contest's tutorial.
But "wow!!" for the character names. :D
#define int long long is evil
Can anybode explain me this pretest on C div2 (A div1)? Why the answer is 7?
5 10
2 5 2 2 3 5 3 2 1 3
Thanks.
change 5 on 2: 2 2 2 2 3 2 3 2 1 3
Let's change all 5's in 2's, we get |2-2| + |2-2| + |2-2| + |2-3| + |3-2| + |2-3| + |3-2| + |2-1| + |1-3| = 7.
Thanks. I lost, that ALL marks will be rewritten.
Java is evil , during contest same solution of problem B(Div2) got TLE in java 6692351 but in c++ , 326ms 6701333
Yes. Java Arrays.sort() is O(N^2).
EDIT : Only for primitive type array
Arrays.sort() uses a merge sort, so it is O(n log n).
See the documentation of Arrays class
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations.
So in some set it can be O(n^2)
But that requires a very evil problemsetter that targets Java specifically...
It's just coincidence may be
It cannot be coincidence. Quick sort is guaranteed to be O(n log n) with high probability , which means the chance of running O(n^2) time converges very quickly to 0 as N increases (even faster than inverse exponential growth[1/2^N]). It must have been a designed input. I really hate such behavior ...
Exactly the same thing happened for pascal programmers who copied sample quick sort procedure in FPC compiler: See This post (in a Chinese forum) . However zhonghaoxi said they were using random generator.
UPD User 2333333 is the one who submitted that input instance, though it looks quite normal, there is a previous one got generator compile error and I opened the protocol and it says:
And that's why this is happening... Such things are so disgusted, trying to attack a certain language's bug
Correction: test 45 is target to median pivot sort algorithm. (Many pascal solution fails on test #45) This is a well-known input to hack "standard" quick sort. But
Java7QuicksortKiller... so evil WTF> Such things are so disgusted, trying to attack a certain language's bug
And why exactly is that bad? The problem statement does not seem to exclude hard cases. You have one problem statement and plenty of tools (programming languages) to choose from. There is no one perfect tool. Learning the weaknesses of your tools, and how to circumvent them, is essential if you want to use the tools efficiently.
Specifically in Java, not only you can use a double-pivot Quicksort for primitive types, you can also box them and utilize Timsort for objects which is guaranteed to be
.
Hi Grand Master :D
Do you have any idea on why the quicksort in the java library is not randomized?
And why it is not possible to utilize Timsort on primitive types?
And why it is possible to shuffle a list of objects but not and array of primitve types?
Thanks in advance.
====================================================================
Disclaimer: Note that I'm not anywhere close to a Java expert.
As I understand it, library quicksort is optimized for the general case (not the corner cases). Using randomness of any sort would slow it down in the general case. Timsort, on the other hand, is stable, which can come in handy for objects but is useless for primitive types. For an additional bit of reasoning, see here and here.
To use Timsort on primitive types, you can box them into their respective wrapper classes. The same goes for shuffling. The language inherently does not allow using generics on primitive types.
Thanks for the explanation and the links.
That hack brought down over 80% of Java solutions, do you think it is a good thing or not? Personally I never support it
=============================================================
It may be seen as unfair, in the sense that a test targets a particular inefficiency of a particular tool. Indeed, some but not all of the participants expect challenges to be "pure", in the sense that once you think of the right solution, the implementation should not require much tweaking.
It may be seen as fair, in the sense that there are no artificial indulgences for users of particular tools. As far as I understand, every other tool does not have a problem with that test. If so, it's a problem with the tool.
Personally, I stick with the latter argument, bearing in mind that the particular inefficiency of Java is so easy to circumvent (boxing + Timsort).
The important part is that it's a learning opportunity for the authors of these over 80% solutions.
I am not sure if this is your intent, but your comment sounds as if you are accusing someone who just followed the rules to score as much as possible.
This is a well known problem with java when you sort a primitive type array it uses quick sort which will result in O(N^2) runtime on some specific cases. This had been discussed on many posts on codeforces before
http://codeforces.me/blog/entry/4827 http://codeforces.me/blog/entry/7108
The solution is to make your arrays of the class type not the primitive type, i.e int -> Integer, long -> Long. The JVM will use merge sort instead of quick sort in this case.
Thanks , I will take care of this from next time.
What? Doesn't the quicksort use a median selection algorithm that makes it pretty difficult to find an O(n^2) sequence?
Well there are already some generators that were posted on codeforces. Check the links in my comment.
No
And it is not only difficult to find array on which quick sort with median will work square time, it us outright impossible
Right, I guess I meant "median approximation algorithm" such as "median of three".
Once Again disappointed by the Java standard library :(
I had the same problem. It seems The quicksort implemented by Arrays.Sort is not randomized ;(
I had a "time limit exceeded" and solved it by adding a single shuffle (using the fonction below) before calling Arrays.sort and now i have 120ms. u_u
// Implementing Fisher–Yates shuffle static void shuffleArray(int[] ar) { for (int i = ar.length — 1; i > 0; i--) { int index = rnd.nextInt(i + 1); // Simple swap int a = ar[index]; ar[index] = ar[i]; ar[i] = a; } }
RANDOMIZATION IS A MUST AGAINST EVIL PROBLEM SETTERS è_é just kidding ;)
Судя по количеству решивших А, B и С (Div.2), В надо было лучше дать 500, чем 1500.
My position is 79 on the final standing & I need 114 more to be purple...
Please update it quickly... :(
UPD: I can't... :(
looks like you missed by some margin , so close.
how true your speech were !!! :'(
А можно решить див2B без дерева отрезков?
Мне кажется, что Div2 B всегда можно решить без дерева отрезков.
Это же делается простой суммой на префиксе: 6693357
*facepalm
Спасибо!
In Problem A, DIV 1, when you merge page x to y, so you copy the content of page x to page y also. Thus we will be able to find the answers on page x, also.. untill and unless we remove actually remove that page, then we will have to turn less number of pages and answers will change.. Thus th eline ", all elements in sequence a that was x would become y" in the question statement is ambigous with the description. I coded my solution assuming that if we merge page x to y, the will be able to find answers of page X on both page X and Y and thus failed.
That sentence stated exactly how a merge affects sequence a. Since the answer depends solely on a, to me this statement can not be ambiguous.
Anyway, keeping answers on both x and y will make the question more interesting and its solvable with a similar approach.
How do you solve your version of the problem? I'm quite interested :)
I agree that it is not ambiguous, but it would have been much better if the problem statement said “she would move” instead of “she would copy.” It confused me first, although I finally assumed that it was just a suboptimal choice of the word and did not ask for clarification.
By the way, I enjoyed the contest, thank you for the hard work!
May be I tell you some not very popular thought, but
Why did email invitation come in the very deep night between Friday and Saturday?
Shame on me not to visit codeforces frequently, but ...
very lucky to get #1 :)
After those bad days breaking up with girl friend, seems I can finally walk out of it and training for world final :)
thanks, i was happy with contest
Round Stats
What means Let_us_play_CF?
I tried to implement problem
Tachibana Kanade's Tofuand got TLE with MSC++ Compiler. I tried to resubmit it with GNUC++, it got AC >_<http://codeforces.me/contest/434/submission/6710299
http://codeforces.me/contest/434/submission/6710309
As I remember, in some problems, MSC++ is faster than GNUC++, some others, GNUC++ is faster than MSC++.
Luckily, I couldn't solve this problem while competeting ^_^, if not, the contest would end with many regrets ^^.
Anw, thanks for nice problems : D
Hi all. Could you please describe why I'm getting TLE on this? (Problem B Div 2) It's confusing for me because the code passes the 5th test with n = m = 10^5 but it gives TLE on test 46 whose parameters are : n = 88888, m = 1; Here's my submission Thank you.
The problem is in
Arrays.sortimplementation in Java. It is vunerable to anti-quick-sort test. You should random shuffle the array before sorting it.