Завтра, 31-го августа, за 4 с половиной часа до конца лета (по Москве) будет проходить Codeforces Round #136. Автором этого контеста буду я, это уже мой 6-й контест на CF.
Помогает строить раунд мне Геральд Агапов (Gerald), задачи переведет, как я предполагаю, Мария Белова (Delinur). Спасибо всем.
Надеюсь, вам понравится раунд. Разбалловка стандартная.
Спасибо за участие. К сожалению, большинство моих контестов не пользуются особым интересом, судя по системе "Вклад", но надеюсь все-таки нашлись те, кому он понравился :)
В первом дивизионе ровно 7 участников решили все задачи, они и попадут на главную:
В то время Топ-4 во втором дивизионе выглядит следующим образом:
На данный момент есть только разбор на английском.
And again your contest at the very end of august(round #84, 29 aug 2011).
47 to all.
what is 47?
Lucky number.
Most likely, you'll find this out during contest.
Автор оригинален в своих смайликах. Мило.
UPD: Пофикшено.
О таком можно и в личку сказать ;)
Всем удачи на уже сегодняшнем контесте, надеюсь, будет весело)
О таком можно и тут написать.
Will the problems be sorted by difficulty or not?
What a pity that I cannot attend this match because it is 1st,Sep in my timezone and I must back to school. But I wish everybody will enjoy this match and do your best!
We should back to school the day after tomorrow, so we can do.
I must back to school too.For I haven't finished my homework,I have to stay up to finish them.So I can sttend this match.How happy!
My teacher told me that we'll have an exam on 3rd and it realy shocked me...I wish my test scores will be as many as my rating on CF...700 is enough in fact...
Back to school on Saturday, poor you guy. Anyway, virtual participation is still available for you later :)
It's the last year for me in middle school,so no matter Monday or Saturday is busy for me...
Gui.....
Wow! Mr. witua always your problemset is great! ;) Thanks for preparing another contest!
The cute faces are nice!
Let's hope for a * lucky * round to all :)
Unfortunately, it can't be lucky for all of us — someone has to be a looser..:)
It depends on what you expect for the match.
If I solve 3 or 4 problems, I learn something new (a good idea, algorithm, etc) from one of the problems I solve and I feel happy with my solutions, but many people are lucky so I lose rating, I consider myself lucky in the contest.
Besides rating is not everything, you can lose rating and then increase your rating in another match, but a good idea or solution that makes you learn something interesting, is never lost.
I was expecting it to be on the 29th. Was you n th birthday too great to find a time for contest this year?
Unfortunately, it was scheduled before I was setted as an author. Sorry for disappointing you.
I 've Been Missing Normal Score Distribution ! Thank You ! I Wish Luck for Everyone :)
Hope all the best from this contest!!!! ........Good luck and Have fun everyone ......:)
Can somebody explain the solution for Div2-D ? It drove me nuts.
I used sqrt — decomposition.
let's find all possible values of x for interval [1..n]. there will be no more than 2 * sqrt(n) such values. iterate over values of constructed set, and solve problem for all intervals. O((n + m) * sqrt(n))
I use segment tree :d
Me too, a offline 2d segment tree's painful code :-|
Actually he used 1d segment tree
Спасибо за раунд, было очень интересно порешать :)
can somebody tell me how to solve problem D in div 2?it drives me crazy...
Классный раунд, спасибо автору. Даже если у меня упадут все задачи, я не расстроюсь. Веселье от 11 взломов просто неоценимое.
P.S. Видел решение в С за куб. Ну как такое вообще может в голову прийти?
In my opinion, Div2C is the easiest problem.
No. The easiest problem is A, of course :)
A is easy too :) but I had to implement 'f(x)' to solve it :D
Agree,but I made a little mistake and spent all time in it.
Кто-то знает в чем особенность пятого теста на С?
У меня тоже на нем падает. Почему — пока не могу понять.
Видимо в том, что некорректно считать перестановку циклически замкнутой. Тест сходу придумать не могу, но, кажется, валилось именно из-за этого.
У меня заработало, когда я начал сдвигать перестановку в другую сторону
Я в разные стороны двигал, но не помогло.
По задаче Д (див 1) надо было перебирать по размерам стягивающего прямоугольника и поскольку известно, что хотя бы одна точка треугольника будет в вершине этого прямоугольника, то аккуратно расписать случаи? Или я чего-то более красивого не заметил?
Я бы считал кол-во точек с различной парностью координат, а потом просто перебираем 6 чисел(от 0 до 1) — координаты треугольника и смотрим чтобы четная площадь была. Естественно, потом нужно вычесть все треугольники нулевой площади.
да, я бы так же делал, тем более, что такая задача уже была (как я ниже написал) и так я ее и решил, видимо
в этой задаче, видимо, больше проблема вычислять, сколько троек точек на одной прямой
Да, пожалуй так код выходит проще гораздо, со стягивающими прямоугольниками случай 3 точки на одной прямой отпадает, только получается куча вариантов с подвариантами (1 точка на углах, 2 точки на углах: на одной стороне, противоположные, 3 точки на углах).
что такое стягивающие прямоугольники, можете сказать?
Прямоугольник минимального размера, в который треугольник входит целиком. Получается что все точки треугольника лежат на сторонах этого прямоугольника. И что ещё более круто, одна из вершин треугольника лежит в вершине стягивающего прямоугольника.
То есть, идейно, пребираем все размеры стягивающего прямоугольника (x; y), и если мы аккуратно подсчитаем сколько треугольников туда влезет, и при этом мы знаем что всего можно запихать (W-x+1)*(H-y+1) таких прямоугольников, то ответ должен быть суммой по всем размерам.
"Получается что все точки треугольника лежат на сторонах этого прямоугольника."
это не так, возьмем треугольник (0,0),(3,4),(1,3) (1,3) не лежит на стороне
Но все равно, это сильно упрощает решение
Lot of TLE's in div2 problem B :)
In div2_B I hacked 4 contestant with one test — max test.
I hacked 5 contestants with max test.
how i can hack solution?
First, you need to block your solution (you can do it on tab "Problems" by clicking on lock icon). Then you'll be able to view and hack solutions of blocked problem by double-clicking into cells in your room.
Как всегда не хватило последних секунд...
I failed DIV I — C 4 times. Two of them were because the examples were symetric so I misunderstood the way of rotating (I was shifting to the right instead of shifting to the left), and in all the submissions I failed pretest 5. I cannot find where to get the pretests, but it seems a lot of people failed that test case. Can anyone who failed that case, and then fixed it, tell me what was the mistake on your code? Does anyone know where can I find the test case?
Also for problem B the problem statement was wrong. Even if the examples clarified it, you can choose x = 0 and it also works (it doesn't say x > 0 or x is a positive integer, it just says "number x" and 0 is a number.
I misunderstood the way of rotating too!
Yes, that was a mistake causing WA on test 5.
I tried with both ways of rotating and still got WA.
I looked at the test case I failed and my bug was considering the permutations as cyclical. I can't believe I looked for the bug for almost an hour and couldn't find it!
Same with me. Fortunately, I decided to skip it after a bunch of submissions and had enough time to solve another problem.
So I WA for 6 times!
where can I find the test case? -> It looks like pretest #5 during the contest is called test #5 afterwards.
Seems like there is a test case in problem A that is designed to stuck java's Arrays.sort
Java can't sort the array with 100 000 integers. How unfortunate.
That's why my solution failed. Is it the problem of java library or the server problem?
It's a problem of java library
This is not happened the first time here :(
Thats why I intentionally used merge sort and got passed :) Soln
winger's solution passed it with Arrays.sort — 1980 ms :|
http://codeforces.me/contest/221/submission/2169999 1984 ms.
I think it's not much fair, is it?
Maybe, was it because he used PrintWriter instead of System.out directly?
my submission for Div2 — C got TL using Arrays.sort , Is Arrays.sort poorly implemented?
Remember , Arrays.sort in java is implemented using quick sort which has a worst case complexity of O(n^2) .Read this
So you can do
- shuffle the array randomly before using Arrays.sort()
- use mergesort, heap sort ;)
No, it's because someone is design the data intended to let java solution TLE
I submitted the same solution in practice, in the contest it failed test case 80 with TLE, in practice it passed test case 80 in 90 ms. (it failed with TLE on test case 91 anyway) what's the reason behind this? thanks
Научите меня читать:(
К сожалению, если не научился читать к 20 годам, шансов уже нет. Та же фигня =(
Ну до 20 может успею ^^
Задача Д — уже похожая задача была, только там дается n точек, никакие 3 не лежат на одной прямой, нужно посчитать количество треугольников с целой площадью
как я понимаю, задача Д отличается лишь тем, что нужно еще уметь считать, сколько троек точек лежат на одной прямой?
System tests are still testing submissions for the first 10 minutes of contest (in DIV I) and it already tested 26% of the submissions. That means that the goal of this match was being very fast to solve problem A, that's not very nice. In my opinion the difference of dificulty between problems A and B was very big.
Анти-джаваквиксорт тест :(
:(
А есть какой-нибудь способ в одну строчку массив пошафлить?
А то, оказывается, Collections.shuffle(Arrays.asList(array)); ничего не шафлит, если массив примитивных типов был.
можно просто объявить массив
Integer[]вместоint[], и использовать стандартный Arrays.sortНу с объектами свои приколы. Их сравнивать неудобно, например.
Кому-то повезло: http://codeforces.me/contest/220/submission/2072275 :D
Am I the only one to have solved div2 A recursively as in the description? :D
Nope, I have seen another solves like yours in my room :)
I didn't do well,but I still like this round very much.It is my first time to do Div1.Thank you!
Somebody used an anti-quicksort challenge again. So stupid of me!
Не пришло уведомление о взломе -> не пересабмитил. Windows 7, Chrome 21.0.1180.83.
Раньше такого не замечал. С чем это связано? Нагрузка сервера или проблема в браузере/компьютере/еще что? Были ли под конец раунда у кого-нибудь еще такие случаи? Не очень приятно.
Как решается C человеческим способом? Я писал дерево отрезков для выбора минимума, в дерево кидались интервалы где некая функция убывает либо возрастает. не успел.
Вместо дерева отрезков делать линейный проход с хипом
линейный проход, с двумя сетами: в одном сете все такие x: posb[x] < posa[x], в другом posa[x] >= posb[x]
Почему в A падает такое решениe(WA): 1)Находим неправильные пары чисел(т.е инверсии соседних элементов). 2)Если их много, то говорим NO. 3)Иначе каждое плохое число свопаем со всеми числами в массиве, и смотрим, получился ли он отсортированным.
Потому что, сделав один обмен несоседних чисел, можно убрать 4, как ты говоришь "неправильные пары".
Если в массиве есть аж 4 "неправильные пары", один обмен заведомо не спасёт, так что обнаружив такое их количество, есть смысл сразу вывести NO.
15342 Сколько тут неправильных пар?
Две.
Я, кстати, исходный массив сортировал, а потом смотрел сколько чисел поменяли свои места. если 2 или 0, то YES, в противном случае NO. Во время контеста накосячил (написал условие вместо цикла), но на дорешке сдал.
Со всеми числами или со всеми неправильными? Если со всеми, то TL должен быть. А много -- это сколько?
Ну я вообще только самую левую искал, поэтому работает за линию. Но видел людей, которые брали побольше (10 + eps), и тоже получали WA.
This problemset is interesting~~ enjoy a lot... Although I have made a silly mistake in Problem B >_<. One of my friends' Java solution fail because of Arrays.sort's issue...Actually I don't think it is good to put such a case >_<...
lose one point in rating and drop to #7 T_T...... Sigh...It seems I'm always making silly mistakes>_<... How can I get rid of it ?
Problems with Arrays.sort and HashSet/HashMap were discussed a lot, but in Russian. These tests should be in system testset because they are used for hacks.
Ok,but I think it's unfair to those who are new to here. Why don't put it in FAQ?
Nobody reads FAQ ;)
which are the problems with HashSet/HashMap, where i can found info? thx
It's this.
It Was a Very Nice problemset and I myself really enjoyed it ! Thank You All for preparing contest (and ofcourse participating The Contest :) ) . But I had a Problem With Task E Div1 in Place where The problem Described the pair l,r many people didn't notice that its a1,,,,al,ar,....,an :D i had 4 WA because of it and Didn't manage to read the rest of the problems (after A I jumbed to E :D)
witua's rounds have always been good for me, and ratings is always increasing..
I'm 256. in final stadings. And I have 2560 points :D. Interesting numbers :)
I did a little mistake in problem C div 2. I counted the number of changes and then, I divided it by two. When I saw that 3 — 2 — 1 gave me only 1, it was late, I was blocked this solution. I got it, it not the same return (cant <= 2) that return (cant / 2 <= 1). Thanks for this great contest.
I was able to solve A-D correctly. After contest... :( But I enjoyed the problems, they are really interesting.
В div. 2 — B при решении использовал осмотр чисел от 1 до sqrt(x)+2 и завалил финальное тестирование(
Оказалось, надо было ограничивать sqrt(x)+1.
Ещё можно было добавить проверку, не рассматривали ли мы это число раньше
Считалось ли решение В за
времени ассимптотически верным? А с такой же асимптотикой по памяти?
UPD. В предыдущих правках были ошибки.
Это про какую задачу?
Это про В...
У меня решение за O((n+m)*sqrt(n)) (ведь имелась ввиду именно такая асимптотика? :) ), памяти O(n+m), с корнем уже не должна влезть
После прочтения Вашего решения я ощутил себя тупицей, постоянно выбирающим страшно неоптимальные пути...
Ты как-то по другому решаешь или же можно другими способами решить, более легкими и простыми? А то в голове у меня небыло такого даже написать. С одной стороны все очень просто, а с другой куча не ясностей.
А вы уверены, что говорите о той же задаче? Они явно обсуждают задачу Б первого дивизиона
Ок, формулу поменяли :(
В смысле?! о_О Посмотрите на решения на С++, использующие 200 с лишним МБ памяти.
UPD. Насчет n * m — ошибка, разумеется, n + m.
My solution for problem A (div1) failed the system test (Time Limit Exceeded). It's quite unclear to me how it could get time limit when it's a O(nlogn) solution with n<=100000. In my computer it works very fast. How can I contact to anyone who can check that? Seems like unfair to me
I think, it was anty-quicksort test, so it was O(n * n)
This is not first incident when one contestant asks help from another one during contest. Someone (I won't tell who) sent me message like this:
1)how to solve C help me please2)it won't do harm for your rating. just + for me....It won't "+" for you. If I helped:
1)it won't be your really rating.2)it will affect to others rating.3)do you really want to practice ComputerProgramming?Сегодня на контесте заметил:
Баг или фича? Я про полосу прокрутки.
Ubuntu 12.04, Google Chrome Version 21.0.1180.89
В FF все нормально
У меня такая же полоса прокрутки в половине сабмитов. Windows 7, браузер — Chrome
И у меня этот баг начал с недавних пор проявляться, win7 x64 Chrome 21.
my code is giving correct output(=91) on test case 9 but here it is giving wrong answer on test case 9 2084000
i did submit your solution and it got AC. i just changed, the size of s1,s2,s3 and i submitted it with GNU C++ 4.6, instead of GNU C++0x .
sorry, i forgot the link
@fab But what can be the reason of increasing array size?? on my system it is giving correct answer for test case 9.(=91), for even an array of size 10??
i really don't know. it did give the right answer in my computer too, i just increased the array size to be sure ( it almost never hurts to let it have some air to breath ) i asked some of my friend, one of them, said, it might be the C++0x, and it still might not be completely perfect. but again, i don't know. sorry.
actually 10^9 is 10 digits, so your arrays are too small.
thanx actually i use bloodshed dev c++ compiler which gives correct output even when array size is exceeded by 1 or 2 i think.....
Stop using it, it is old and unmaintained. Try MinGW+Code::Blocks or MS VC++ Express.
Господа. Кто-нибудь подскажет мне. Тест номер 5 в задаче E div 2: 10
5 1 6 2 8 3 4 10 9 7
3 1 10 6 8 5 2 7 9 4
Ответ:
Почему? Ведь после первого сдвига перестановки будут такие:
5 1 6 2 8 3 4 10 9 7
4 3 1 10 6 8 5 2 7 9 Как минимальное расстояние может быть равно 0?
Сдвиг в другую сторону.
Спасибо. Я смог завалить 2 задачи из-за своей невнимательности. :-(
Can someone please explain in detail how to solve problem D in Division II?
number x must appear more than x times,add them together,so the numbers that are useful are no more than sqrt(n).You can use the prefix sum and calc all the number'time by brute force.Notice the time limit is 4 seconds.(sorry,my English is poor.)
By the way,who is the person in your photo? It seems to come from Star Wars.
It is Luke Skywalker in his pilot costume. :)
I am a fan of Star Wars,so glad to see him here.:)
Господа, прошу помощи. Я не пойму задачу про слоника и функцию. Поясните пожалуйста. Ответ такой n, 1, 2,...n-1; Но ума не приложу почему. Если я правильно понял, то мне нужно получить последовательность, чтобы подав ее в функцию f получилась последовательность 1..n. При рекурсивном спуске всегда получается ответ n, 1, 2,...n-1; Но если подавать эту последовательность на вход, я не могу получить возрастающей последовательности 1..n . Где я ошибаюсь?
суть задачи заключалась в том что нужно данную функцыю запустить задом на перед.И некоторые в условий задачи понимали не правельно и делали так что свапали елементы местами и потом запускали функцыю но нужно запусть функцыю для следуйщего елемента а потом свапнуть.вот наглядный премер функцый задом на перед вызываем функцыю для первого элемента у нас последовательность такая.
1 2 3
вызываем для 1 функцию
функция вызывает функцыю для 2 а потом свапает но так как функцыя для 2 ещо не закончилась она не может свапнуть функция для 2 вызывает 3 и тоже не может свапнуть потом функция для 3 уже не может идти дальше потому что элемент последний и заканчивает роботу тем самым функция для 2 свапает 2 и 3 элемент уже вид последовательности такой 1 3 2 функция для 2 заканчивает свою роботу тем самым заставляет функцию для 1 свапнуть 1 и 2 елемент теперь последовательность принимает окончательный вид 3 1 2
Простите, кажется я не понимаю условие. Пусть f- функция слоника, тогда должно быть так:
f(n) /* n<>1 -> f(n-1) -> swap -> ..-> f(1) -> n,1,2,...n-1 теперь происходит возврат f(1)->swap->f(2)->swap->f(n-1)->swap... Также должно быть? если да, то у меня не получается возрастающей последовательности, если подам на вход n, 1,2,... n-1; Пока не понимаю...
ну вот смотри мы запросили функцию слоник f(n) она запустила функцию f(n-1) а потом свап таким образом что свап не задействуется пока функция f(n-1) не закончитса и так оно будет вызывать до 1 а потом просто функция вылетит и все функций начнут свапать будет происходить так (3 1 2 тут функция вылетит) (1 3 2 функция для 2 свапнить x и x-1 элемент тоесть 2 и 1) (1 2 3 функция для 3 аналогично свапнить 3 и 2 элемент)
Интересный был контест, только мне почемуто кажитса что во втором девизионе первые три задачи были слишком легкие
Но ты почему-то 2 задачи решил и ты на 768 месте:)
третью не решил потому что забыл эвристику квиксорта а остальное баги в проге помогли.А так задачи были не очень сложные
Если смотреть на D и E, то первые 3 задачи
халявы. На этом контесте роль игралскоростьи конечноhack(кстати, это у меня первый раз). Если смотреть на результаты, участники между 50 местом и 500 местом, многие решили только первые 3 задачи.ну так я и говорю что первые 3 задачи лёгкие
По задаче D(div2). Пока еще не разобрался с решением в разборе, но придумал вот такое: Отсортим все запросы по правой границе. Пройдемся по массиву, начиная с первого элемента и если он меньше n, то сделаем следующее: добавим в вектор, который отвечает за это число его индекс. Теперь, если мы получили, что размер этого вектора больше или равен этого числа, то это означает, что чтобы этот элемент был включен в ответ, то левая граница запроса должна располагалаться между индексами (cnt[b][sz — b — 1] + 1) и (cnt[b][sz — b]) (включая концы). Пометим это, прибавив 1 на этом отрезке, но не забывая отнять 1 на прошлом отрезке для этого же числа. Теперь, чтобы ответить на запрос, нам всего лишь нужно вывести l-ый элемент. P.S. cnt[b] — вектор с индексами элементов b, sz — его текущий размер. Кому интересно, вот код: 2086625. Надеюсь, решение не слишком тупо. Извиняюсь, если я неправильно понял решение из разбора и изложил его же своими словами.
thanks for preparing the contest and the problemset. i had a little problem with task C ( div.1 ) and i thought it might be someone elses' problem, too: i saw that a lot of people ( including myself ), got wrong answer on test 5 and i think, they made the same mistake that i did, and it could easily be prevented, just by making better thought, sample cases. the problem was that, i ( and i think some other contestants ) did make a little mistake in understanding how the shift works, so, the solution we outputed, was just bacwards. but if the test case 5 ( which is a reasonable case with n = 10 ) was a sample case, we could easily have realized this and get it right.
I WA on test5 too,and I realized the reason after my brute force program get Wa too.I think it is important to understand the problem more carefully.I just hope that we won't make the same mistake in the future contests;
i do think it's important to be careful and try not to make mistakes, like this. but it's not an implementation problem, and in this problems, finding the algorithm is the most important part, not little things like this. and second of all, i think the idea behind sample cases, is to prevent this kind of mistakes ( and/or for understanding the problem, better ) and it seems to be a common mistake, because at least more than half of the contestants ( the ones that i checked ) who got WA in this problem, did get WA at least once on 5. i don't think it's that important.
Maybe you are right.
А на чем Б-шку ломали?
Видимо, некоторые делители до n / 2 перебирали, а не до корня.
Некоторые делители до n / 2, некоторые до n перебирали.
Блин, почему у меня в комнате такого не было((((
Кто подкажет, почему qsort улетает на 82 тесте в задаче C (div 2). Тест 81, где 99996 чисел пролетает за 60 мс, а тест 81 с 100000 числами падает по TL.
Потому что у тебя опорный элемент в середине. Представь, что случится, если там всякий раз будет оказываться максимум или минимум.
А куда лучше всего его передвинуть или что можно изменить?
Ну как минимум нужно брать случайный.
Пытался написать рандом от L до R и упал по времени на тесте 6
Не значение элемента рандомное, а его индекс в массиве.
Упс, вот в этом я и правда ошибся. Большое спасибо Вам за подсказку ;)
It was my first CF round where I was to rank up, after 3 contests losing rating...
I found the problemset very interesting and I was able to get accepted for 2 problems, A and C!!!
I wish that we can have more rounds like this in a near future and wish good luck to everyone in the upcoming school year as well!!
Bruno
Очень странно ведет себя задача D из Div2. Написал решение — получил WA33. После получаса поисков решил посмотреть на АС решения других участников: понял, что моё концептуально не отличается. Попробовал сдать чужие АС решения — WA33, кто-нибудь знает в чём дело?
Интересно, что тест 33 поменялся со времени соревнования: раньше начинался на
, а теперь на
Это либо ошибка, либо своеобразный rejudge =) Есть ли смысл пытаться сдать эту задачу сейчас, я имею в виду, у кого-нибудь сдается его решение?
Неа(
Только что пересдал. Спокойно прошло.
Хмм… Эта посылка, так: 2096960? В ней тест 33 снова отличается от приведённых выше.
Странно вот что : если отправлять по коду 221D то WA33, а если по 220B, то AC. Мистика.
У мне на обоих кодах решение получает WA33
Теперь все ок. Спасибо, что починили =)
Та же ерунда. Тест 33 начинается на
362 328 428 153 ...И таска не проходит
Третий вариант, который встречался:
250 302 154 91 381 407 ...На нем проходит.
http://codeforces.me/blog/entry/5223 — читаем
Hi,
Can anyone help me in knowing what can be done in https://codeforces.me/contest/220/submission/63940597 whose complexity is O(nlogn + m sqrt(n)logn) to get AC.
(Problem:https://codeforces.me/contest/220/problem/B)]
Thanks,