Привет, Codeforces Round #221 начнется 24го декабря в 18:00 по москве. Раунд будет проводиться в обоих дивизионах.
Задачи готовили whd, oGhost и boleyn.su. Это наш первый раунд на Codeforces, и мы надеемся, что он будет весьма хорош.
Хочется поблагодарить Gerald и alpc104 за помощь в подготовке раунда, а также MikeMirzayanov за создание платформы, где все мы можем соревноваться и общаться.
Распределение баллов по задачам будет анонсировано перед началом контеста.
UPD1: Распределение баллов 500-1000-1500-2000-2500 для обоих дивизионов.
UPD2: Наши поздравления победителям! Также поздравляем с рождеством всех, кто празднует его сегодня!
Div 1:
2.al13n
3.rng_58
5.uwi
Div 2:
1.bohuss
2.Tyg3R
3.xhsong
4.adamant
5.Kira96
Good luck
And Merry Christmas (note the date)
Hope the contest won't be like the last contest( Hard && Unrated ). Good luck to eveyone!!!
Good luck ... :)
Maybe people can already assume that every round announcement has some kind of grateful acknowledge to MikeMirzayanov, since it's becoming a bit boring to read that part every single time.
then don't read that part! :D
+1!
It is more like fetishism. We really have to eradicate this practice.
UPD: no disrespect was meant to Mike at all.
If this is the last round this year...
HAPPY NEW YEAR TO ALL :D
The last round 's Good Bye 2013. It will take place on the last day of this year :-)
Why this blog isn't on the home page !?
Contest in Christmas Eve? And on top of that — at 18:00? Weird idea. I'm not familiar with Russian traditions, but in Poland at that time we usually gather with family around table and celebrate Christmas Eve :P. Other days will be better or at least earlier hours. Even though I will try to compete :P. In Poland it's not that bad hour, because it will be 15 :P.
Pay attention to where the three round makers come from.
They come from Renmin University of China
The round will take place at 18:00 MSK means 22:00 CST.
BTW, as a freshman,it's always hard for me to make a decision whether I should take part in a round start at 19:30 MSK or not , because if I do, I have to coding from 23:30 CST to 01:30 CST while my roommates are sleeping, which may bothers them.(In my school, a student should never stay outside domitory after 23:00)
Wouldn't the round writers have it better if the round was earlier?
Are you sure that your roomates are sleeping at 23:30 CST? hehe
Christmas is not celebrated on 25th of December in Russia, see this wikipedia link. And even on 7th of January Christmas is not celebrated that widely comparing to how they celebrate it in Europe for example. In Russia people mostly celebrate New Year.
Your snow bear looks so cute! cute cute cute!!!
The Orthodox calendar isn't affected by the Gregorian correction (not everywhere, though), so Christmas in Russia should be shifted to 13 days later. Still, 24th this late is not the best choice.
You really are in no position to comment about "no-lifes" on my youtube videos if you plan on participating in a contest on 3pm-5pm Christmas Eve. ;)
OK, you convinced me. Tomorrow at 3pm I'm going to watch your whole screencast :P.
Yay, I participated and took in my opinion really good place — 38th :D!
Wow, three problem setters Chinese from RU! Look forward to it!
In fact, RUC is short for Renmin University of China, while RU is not.
By the way, I was born in Chongqing. It is good to see students from my hometown attending our contest. Good luck and have fun!
That's so sweet. Thanks!
king base!time is good for chinese,thx for setter
Good time for chinese..
Люблю задачи от новых авторов)
Но решать их ты, видимо, не любишь.
:)
Looking forward to it ! When the contest ends, it will be Christmas in China and we will have to go to school as usual ...
I love this contest!
Hope a better Contest than the previous one... That was not a Contest...
hope every contestant can have fun with the problem set :D
Желаю всем удачи на контесте!!
Have you changed the contest time or i need some sleep :) ?
Up-vote this comment if you can :P
It is very hard. We can't. Sorry.
Let me guess. After seeing some people in the last two contests, asking for downvote and getting them, you thought this would work!? If only it was that easy :p
Good Rate on Codeforces and Happy New Year))))
10 minutes before the contest and no score distribution published!
Surely we should unregister and not participate in the contest if we don't know the score distribution.
just solve problems and have fun :)
Just for Remember you said
The score distribution will be announced before the contest starts.
Chill. 2 more minutes left. That's like 120 seconds. Plenty of time to update the score distribution.
Now it's 30 second only do you still think that ?
I posted it 16sec before contest started.
Я понять не могу, почему постоянно такая проблема — указать распределение баллов? Почему всегда это делается одновременно со стартом контеста, а то и позже? Кто мне объяснит?
Я вот никогда не мог понять, зачем оно кому-то может понадобиться до контеста. Вы в зависимости от неё тактику на листочке по минутам расписываете, что ли?
Лично я просто настраиваюсь. Не знаю как, но это помогает собраться с мыслями.
Может быть, потому что Сережа настоятельно рекомендует прочесть условия ВСЕХ задач?
Power belt, I have late for contest and registration. WHY registration starts at late evening? Should it be possible to open registration 1,5 day before contest?
Merry Christmas and Happy Halloween (Note : OCT 31 = DEC 25 :D )
Maybe I have a chance to go to div1...thx...
Как решать С (div2)?
Например вот так:
Находим первых вхождения 1, 6, 8, 9 и перемещаем их так, чтобы они оказались в самом конце нашего числа. (Или просто удаляем из него)
Выбрасываем лидирующие нули, при этом учёв их количество (потом сможем вывести их в конце).
Считаем остаток от деления на 7 числа, составленного из первых n-4 цифры. Попутно выводим их.
После этого какой-то (можно высчитать для каждого случая заранее, а можно перебрать за 4!, это не очень долго) комбинацией из чисел 1, 6, 8, 9 мы можем довести любое имеющееся число до делящегося на семь. Найдя нужную комбинацию, выводим её. Затем отдельно выводим выкинутые ранее лидирующие нули.
Вроде бы должно работать...
А почему при помощи этих цифр 1, 6, 8, 9 это можно сделать?
можно проверить, что перестановки этих цифр дают все остатки от 0 до 6.
Да. Это просто надо знать! Теория чисел. Круто мне нравиться!
Минусы от того что вы все знаете теорию чисел? Молодцы. Это очень хорошо.
Вообще было бы не плохо снабжать свои минусы или плюсы комментарием. Даже в обязательном порядке. Ну вот например на мое высказывание — хоть один комментарий за что минус. Очень интересно.
Этого не надо знать. Можно взять и на компе (можно даже и вручную) сгенерировать все перестановки 1,6,8,9 и посмотреть остатки.
Понятно все. Нет меня не трогают минусы. Скорее всего меня не уволят с работы за них. Не уйдет жена. И не обидятся оба мои сына (они еще ничего не понимают). Но все-таки хочется знать критерии постановки минусов.
Было бы клево под лайками и анти- лайками ставить подпись. Как в контакте. Чтобы обмениваться любезностями.
Но к чему? Смысл лайков/дислайков как раз в том, что можно легко выразить согласие/несогласие или симпатию/антипатию, ничего не объясняя.
К этому посту примерно 200 комментов — мне что, к каждому лайку оставлять пояснение и аргументировать свою позицию?
Да наверное стоит к этому относится как просто к цифре с минусом и все. У меня вот нет математического образования и по образованию я борт — инженер. Мне просто нравиться программирование. Да и сейчас я работаю в этой сфере как уже 2 года. И действительно восхитился как не сложно решается эта задача. Ложки то нашлись а осадок остался.
Можно забыть про лидирующие нули, если поставить число, составленное из
1 6 8 9в начало (тем самым, домножить его остаток от деления на10^(n - 4)).P.S А как давно это добавили?Ссылка на скрин
Целая простыня о том, как тебя волнуют, а потом о том, как не волнуют оценки к комментариям. Спрашивай и пиши коротко и по делу — будет меньше поводов получить минус за мысль «зачем я это читал».
p.s. «Круто мне нравитЬся» — многие ставят минус за ошибку.
nice contest!,but what is the algorithm to solve problem C DIV 2 or problem A DIV 1?
C is pretty simple actually if you think of the reason why the setter used the digits 1,6,8,9. You can get all remainders when divided by 7 for some permutation of the digits 1,6,8,9. That is for every number x in {0,1,..6}, there exist a permutation of 1,6,8,9 such that when that permutation is divided by 7, it leaves a remainder of x. I think with this hint you might be able to complete the solution.
Will there be a tutorial published?
За какую сложность кто писал D? У меня O(Nlog2N), я отвечал в оффлайне, протаскивая вверх по дереву декартово дерево пар (количество, цвет) и приливая меньшее к большему.
UPD: Я забыл упомянуть, что я ещё и протаскиваю вверх обычный мап, в котором для каждого цвета держу его количество, а это ещё + O(Nlog2N).
N^(3/2) * log(N)
--Challenge me plz
5509528 о_О
http://codeforces.net/contest/375/submission/5507862 http://codeforces.net/contest/375/submission/5510896
лол
А в чем преимущества изначального варианта?
Ну, например, он не заходит, ты идёшь думаешь, и пишешь нормальное решение за lg2 :(
У меня тоже лог квадрат с разделяй и властвуй, но вместо декартова дерева — фенвик + хешмеп с количествами для каждого цвета
Можно без фенвика, просто хранить рядом с мапой вектор ответов для всех k; при добавлении элемента он меняется только в одном месте.
Как в одном месте? Пусть у тебя есть вершина, у которой два поддерева. В первом 101 вершина разных цветов, во втором 100 вершин одного цвета. Вот приливаешь ты второе поддерево к первому. Раньше у тебя вектор ответов выглядел как (101, 0, 0, ...), сейчас будет выглядеть как (101, 1, 1, 1, ...). Нет?
Ну, можно же по одной добавлять вершины. И да, это дает n log решение, если мы верим в хеши :)
Да, круто. Для этого надо, правда, ещё вверх вектор вершин из поддерева тянуть, то это уже ерунда.
Не, можно проходить по той же мапе и добавлять по одному.
А я один решал в B два часа задачу, где можно менять и столбцы, и строки? И долго удивлялся, как это сдают все, кому не лень — оно же на НП-хард похоже.
Нет, я тоже долго решал задачу именно с таким условием. Но потом все таки решил перечитать : )
Про столбцы ничего не написано:)
Вот я перечитывал-перечитывал.....Глаз цепляется за большое-пребольшое определение подматрицы и, кажется, что в остальном невозможно ошибиться)
А разве если можно и столбцы и строки менять, мы не можем просто скучить все единицы к углу?..
Увы, нет: 100 011
Yeah.. Div1 is too hard to me.. I'd better back to div2...
Saw few people use sort in problem B div 1. O(n*nlogn) should get TLE right? I went out of my way to use bucket sort to keep it O(n^2).
Sorting? I'm kinda scared now. I didn't use sorting. At all.
I didn't use sorting too, I think n^2*logn should TLE.
5506448
Sorting, no TLE =)
Okay this is weird. I generally assume, 10^8 calculations take 1 second. So O(n*nlogn) is (5000*5000*12)/10^8 = 3 seconds. Time limit is 2 seconds. Since it didnt get TLE, I guess CF is a lot faster than I assumed. So how fast is it? I did the bucket sort for nothing :(
It seems like the compile-time optimizations by GNU C++ are able to make up for it somehow.. Even though that some solutions that used sorting were either hacked or didn't pass the systest, so it's kind of tricky to guess whether a solution will pass or not just by looking at the source code.
mine was O(n*nlogn) and it passed... :)
Is cin very fast on codeforces? I was surprised that cin solutions worked in B.
At least it is fast enough with this:
ios :: sync_with_stdio(false);I always use cin in CF and until now I haven't get a TLE by it.
according to my testing, on GNU c++ 4.4 and above cin/cout work very fast and compareable to scanf/printf :p
I think the reason is codeforces judges is really fast.
At beginning, we do not want n^2logn solution pass, but failed to generate a testcase. I am really surprised by the speed of judge computers.
my n*m got TLE.
My O(N.M.logN) get TLE ! be happy :)
Yes, I saw a solution that uses cin without sync_with_stdio, sortings of n elements n times, and push_backs n2 times — still worked under 2s :)
My solution with cin get TLE. 5505467
It seems it was quite close to the boundary.
my solution 5506320 O(N^2) using
scanf("%c",&x);got TLE, change it tox = getchar()got AC 5511177 under 0.5 s, i wonder why isscanf("%c")so slow ?Cause it parses format string "%c" on each query, at least.
My
O(n^2log(n))solution 5515627 andO(n^2)solution 5515601 actually got the same running time. But during the contest I usescanf("%1d", &a[i][j])to read the digit one by one, and it turns out the this is the bottleneck in my TLE code 5510016 ..Problem Maximum Submatrix 2 is essentially exactly the same problem as http://www.ceoi2009.ro/tasks/logs.pdf :(
And problem B in DIV 2 is almost the same as http://www.spoj.com/problems/ANARC08G/
Div1 A is almost the same as http://acm.timus.ru/problem.aspx?space=1&num=1095
We got the idea of this problem from one of our algorithm class homework.
Need hints for problems C div 2 :( soon :D
That problem looks very artificial to me, these numbers must have some magic.
So I submit a crazy solution 5502926: until find a solution, do some random swaps, and if time out then output 0. And it passed system test.
Seems it can't be no solution, but I don't know why. :)
For every 0 ≤ r < 7 there is a permutation of {1,6,8,9} that (being read as a 4-digit number) yields remainder r when divided by 7. Choose the right one and append all the other digits to it.
Even more than that, for every integer
a, there exists a permutation of {1, 6, 8, 9} that is appended toaand makes the result number divisible by 7. :)You can rearrange 1,6,8,9 to form all mods from 0 to 6 -- so just order the rest of the numbers in any order, then output the correct permutation: http://codeforces.net/contest/375/submission/5507138
For each 0<=r<7, there exists a permutation of {1,6,8,9} as (r*10 000 + permutation) % 7 = 0
So, you choose a random order for the initial number (just conserve one 1, one 6, one 8, one 9 and count number of zeros), then you calculate the rest of this number, and you choose the valid permutation of {1,6,8,9}.
You can then add as many 0 as you want lastly.
sample: 123456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869
(and with zeros:) 1230000456789 -> (23457 * 10 000 + permutation) % 7 == 0 -> permutation = 1869 -> result = 2345718690000
Если это сообщение наберёт пять плюсов, я поною по поводу контеста. Збань, привет.
Самый удачный для меня контест! Первый раз удалось решить 4 задачи за контест. :)
Very interesting problems, and no complex algorithm. LIKE it:) [Although i have solved a little tests] Hope u can papare more contests in the future!!
Are u kidding? N log^2 N solutions in D that use dat slow c++ map pass with a great handicap. Well, maybe I'm unfair cause I spent alot of time doing N log N solution, but I bet on weak tests.
100000 * 18 * 18 < 100*10^6
That's too rude, u don't assume that map is a redblack tree and we keep pairs in it.
One of logs, which going from merge is very small. Also maps are not very big mostly. Probably this two compensate.
There are even O(n * sqrt n * lg n) AC solutions, I really believe that the nature of the queries, at most n different ranges, (without partial overlaps) really improves O(n sqrt n) bound.
I used a hash map (unordered_map) instead of a normal map, and the fenwick tree is tremendously fast, so the additional log n factor is quite reasonable, I was skeptic during the contest (and even tried to find an O(n lg n)), it also seems that Codeforces got some speedy machines.
I think you did something wrong, O(N log N) solution isn't very hard. See 5512577.
Well done, but that wasn't actually a topic of my message =)
Indeed, but it was tricky to realize that is actually O(n lg n) during the contest, those who saw that all the updates are O(n) amortized mostly implemented an O(n sqrt n), the rest just used a Fenwick tree. BTW it would be interesting to find the worst case input for the O(n sqrt n) approach, here the tree structure makes the query ranges quite singular (no partial overlapping), maybe in this case is even better, O(n lg n) or even O(n)?
And for second time in a row a purple coder takes down the Div 1. Congratulations, Touma_Kazusa :).
In fact, she is red for a very long time.
In fact, she is one of the top rated users.
Can you tell us who is that?
YuukaKazami
:(
Are you sure?
The rules: "Don't create more than one account, if you have forgotten the password, use the password reminding system."
Even if the rules should be applied more or less to everybody, I don't think it was an attempt to cheat, or because the password was forgotten, but an other reason (which one, I don't really know).
The only thing that seems unfair it's that will affect rating changes of all others contestants.
I mean, I suppose that being beaten by a purple when you are red/orange make your final rating lower than if you're beaten by a top 10 user...
ну блин, с каких пор N2logN тлится при N=5000?
>:(
проходит оказывается
код 5509284 с sort intов через свой компаратор — TLE 2000мс
код 5510980 с просто sort — AC, 998мс
С++ —
говноменя огорчаетЕще немного магии.
5511406 — stable_sort с компаратором.
и как спать теперь?
А как писать sort со своим компаратором, чтобы он не получал TL в данной ситуации?
Я умею только так: sort(c, c + n); reverse(c, c + n);
Я написал
sort(v,v+n,greater<int>()), и прошло за 1.3с.Компаратор надо через функтор писать, он оптимизируется лучше: 5523979. Подробнее можно у Мейерса прочитать.
log(5000)*5000^2 ~ 3,7*25*10^6 = 92,5*10^6 ~ 9*10^8. А это как бы совсем не две секунды...
В последнем "приблизительно равно" на порядок ошибся...
Если вы о задаче В, то там можно и за O(n^2) решить.
это меня никак не утешает
in problem D,why my O(n*m) solution get tle? 5509804
Try to use getch() or smth other, not cin.
Getch()? Pff.
ios::sync_with_stdio(0);is enough to use cin and get AC =)5511181
Just as I said.
can you explain me why it is so improtant? and what this doing?ios::sync_with_stdio(0);
It is turns off synchronization with stdio (scanf/printf), so cin/cout can work faster. More information here.
Well, I guess because of this line
ans=max(ans,(j-i+1)*num[j][i]);
This line causes many memory hits, you need to access the array in row major order
swap j, i in the loops or in the array dimensions (make it num[i][j])
i think problem is with your input.
Try this.
'getch' was not declared in this scope,what can i do?
"#include <conio.h>"
Эх, на один бы взлом больше и... =)
А мне бы на 3 взлома больше =)
thanks pretest #11, for problem A (div-2).
Could someone explain the solution of Problem D? Thanks in advance
you mean in Div2?
Yes
How to solve E div 2 / C div 1?
The "Custom test" feature here limits testcase input to 256KB, but the maximal testcase for "Maximum Submatrix 2" (Div 1 B, Div 2 D) has a 5000x5000 matrix (25M elements), so it seems impossible to properly test the maximal case for TLE against Codeforces servers (even if you hardcode the testcase in the source, you're circumventing the time taken reading input). Is there any good strategy for handling this, or any way around this restriction?
Use a genarator code.
That works for hacking, but not for testing your own solution in custom test.
Oh yeah. My bad. I misread. Maybe the custom Test is not meant for stress testing.
[email protected] D,,my time is n*m*logn.....TLE.= =
What does I.O.U (name of problem B of Div 2) stands for?
I owe you
I don't understand why in B/D n<=5000. Many people submitted correct solution, but because of using (in my case cin) got TLE. I think n<=1000 would be enough for solutions with bad asymptotics to not pass.
I got n*m solution but because using "cin" got TLE.if n <=1000 than it can be solved also n*m log m and it did not want to author,I think author is strict in this issue.
Am I missing an easy solution to Div1 D or so many people have managed to code solution that resembles mine? I've done it by an algorithm which resembles heavy-light decomposition. I've done DFS, computed some data for every subtree and in one vertex I copied the data from smaller subtrees to the biggest one, which results in O(n log n) solution. I was really satisfied to get this problem accepted :).
Can you explain more detailed your solution? In Russian comments here we discussed accepted solutions in O(Nlog2N) with the same "copy data from smaller subtree to the greater one" idea, but the data was stored in log-time containers, such as Cartesian trees and Fenwick trees, so asymptotic was O(NlogN·logN) = O(Nlog2N).
There is also a solution with complexity O(N * log^2(N) + (Q + N) * sqrt(N)) without advanced data structures, by splitting the set of colors into heavy and light sets such that light set contains colors that have < sqrt(N) elements and heavy set contains colors that have >= sqrt(N), then the light sets could be processed with simple dp on tree, and heavy sets could be computed using the "copy data from smaller subtree to the greater one" idea because there is at most sqrt(N) heavy colors.
Here is my code that got accepted: http://codeforces.net/contest/375/submission/5508056
For every vertex v I call DFS(v, log) where log is some number between 1 and log n. If vertex v has children v1, ..., vk and vertex v1 has the biggest subtree, I call DFS(v1, log) and DFS(v2, log + 1), ..., DFS(vk, log + 1). If I call DFS for vertex v with corresponding argument log, after calling DFSes for its children I want to have some data in col_num[log], at_least[log] and ver[log]. For fixed color c, col_num[log][c] means how many there are vertices in this subtree with color c, for a number k, col_num[log][k] means how many there are colors c such that col_num[log][c]>=k and ver[log] is simpy vector of all colors of vertices in this subtree. Those data allow us to simply answer all queries in each vertex and update corresponding data in our parent in time O(size of our subtree) (if we aren't the biggest subtree's of our parent's children's subtrees) which results in O(n log n) complexity of whole algorithm. If our subtree is the biggest subtree of our parent's children's subtrees, our parent just treats our complete data like its initial data and update it by other children subtrees.
Power of MS C++!!! I think if lots of TLE codes submit their codes with MS C++ compiler,
they will get accepted!
Accepted Solution: 5511246 and 5511362 and 5511553
TLE Solution : 5511075 and 5507435 and 5505552
I submitted these TLE solutions with compiler MS C++ and got AC!
What is the real reason?
problem B sux
you can't strongly say that MS C++ is better than GNU C++. The difference is that cin and cout have been defined differently in these two compilers. The time of cin in MS without ios_base::sync_with_stdio(false) and with it is really close, however there is a massive difference in GNU with ios_base::sync_with_stdio(false) and without it. But GNU is faster with syncing than MS with it. I can show u a lot of codes which got acceptance with GNU with syncing that same code in MS didn't.
Div.2 Problem D I add
ios::sync_with_stdio(false);and pass.........Can anyone help to explain?!
What a pity...
cin works faster with
ios::sync_with_stdio(false);Explanation here.
Also some statistics here.
I think it is almost always better to use scanf instead of cin.
You're wrong. If you use cin with
ios::sync_with_stdio(0);on GNU-C++ your solution may be even faster than with scanf as you can see here.Feel quite disappointed about the problems setter (or the translator) of problem D div 2. You can rearrange the row but each col MUST BE ORIGINAL
I am sorry for that.
Можете объяснить почему 5505144 Runtime Error в задаче 376B - Задолженности ?
m <= 10^4, а у тебя массивы a, b, c на 111 элементов.
Div.2 Problem D: priority_queue got TLE (AC in MS C++), push in vector and sort got AC :(
I guess that why we usually prefer quicksort to heapsort :)
I don't know about you guys but I used a physics formula for Div 2 A. Is there any other solution?
Thanks for nice contest! It requires an ability to write fast without bugs not-completely-simple code in each task.
Can someone please tell me where my solution for div2-C is failing? I made use of the mathematical trick of finding %7 for large numbers.
http://codeforces.net/contest/376/submission/5506741
UPD: Found my mistake. Thanks to Zlobober ! :)
Your idea is quite right but you should add your mp[remmod] to the end of the answer, because it will give the right remainder, but not 10^(len — 4) * right remainder.
http://codeforces.net/contest/375/submission/5504410 -- my solution.
Adding mp[remmod] to the end is wrong because that can cause leading zeroes.
In any case, I found my mistake a while back and corrected it. :) Thanks!
Well, you can add all zeroes to the end, as in the author's solution.
Not quite. I'll give you an example.
No zeroes in this case, so according to you I should add mp[remmod] to the end. But it is wrong.
Test Case : 11689 Output : 18961 ( = 5 mod 7 )
It is realy unfair..... algorithm and and implement is correct only because of ios::sync_with_stdio(false); I get TLE....
You should try to study more about the ur programming language sometimes :)
It was really best Christmas present, thank you very much and see you in DIV 1 :)
Congratulations!!!
+100 :D
+174 ;)
-15 :P
It is recommended to test the maximal case locally.
I think that it takes less than two minutes to write a code to generate maximal case.
+198 :)
First of all, thank you for preparing the problems for us. It was a nice Christmas Eve.
However, I would like to point out the problems is not very good (at least for me).
For Problem B, it is EXACTLY THE SAME with CEOI 2010 Day 2 Problem 1 Logs (the only difference may be the problem from CEOI asks rearranging the columns).
And for problem C/D, I cannot recall clearly the source of these problems but I have solved tons of problems based on the old idea.
I hope that Codeforces can have more problems with new idea instead of the old one. New idea may be easy, simple, interesting, ... but it is good.
Anyway, problem A/E is really nice (maybe adapted from Chengdu Onsite 2013?). I don't come up the solutions till now.
Thank you again!
Well, if D has a nicer solution, than "move-info-from-smaller-subtree-to-larger" one with using some complicated data structures like maps, hashmaps, cartesian trees, fenwick trees etc (that are discussed above in Russian version of the site) then it would be great to know about them. Maybe when problemsetters publish editorial we will find more interesting solutions to it.
And C seems very nice and interesting for me. Can you give a sample of the problem with the same idea? Moreover, if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem (but with such explanation in task the idea to store a mask of oddity for each object becomes much clearer and obvious).
The Grove -- USACO 2006 January Silver
As far as I knew, this may be the first time this idea appears. The problem can't become cooler by replacing the definition into something like "reach from the infinite point" since it must allow multiple pass of one cell. It is not that natural.
If someone has read this and not my explanation few posts above — yes, instead of maps, trees and other stuff, you can use arrays :D -> http://codeforces.net/blog/entry/10034#comment-155315
But one one drawback is that this results in also O(n log n) memory, there are other approaches with those more complicated structures which requires O(n) memory only. But if it fits into limits, there's nothing wrong with it :).
"if authors didn't have to explain, what does "inside the closed curve" mean, it would have been really cool problem" — imagine a closed curve with many selfintersections (those are allowed in this problem!). Could you clearly state what's its interior and what's its outerior? These 2 words are losing their meaning and the only thing that can tell them apart is this parity definition.
Yes, that's exactly what I meant by phrase "authors have to explain what does that mean".
hmspmy077 in his comment above showed much nicer task, that deals with that problem another way. For that task there is no need to define what interior exactly is, because it uses only the "walk around the connected figure" conception, which is much simpler to imagine and doesn't require additional clarifications.
Problem A is not new at all — see there http://acm.timus.ru/problem.aspx?space=1&num=1095 There's about 2000 sucessful submissions on it on the most famous Russian online judge.
I did not write this round well,but I liked problems very much,thanks authors for contest.
How did people use sorting to solve Div2 D / Div1 B? O.o
More info
Awesome work, like previous stats.
How do you make such requests on this website to get data? wget parser?
Thanks! :)
If I get your question right, requests are made using
XMLHttpRequestfrom javascript. After the received html data is processed, graphs are built using Google Charts.Thanks for this fast answer!
Alternative problem for Div 1 A/ Div 2 C:
Is there a simple solution at this problem:
Find a permutation of a number n composed only by 1,6,8,9 digits (666,1689 etc...) divisible by 7
I tried to solve this problem during the thirty first minutes before finding my misunderstanding...
As long as there's at least one occurence of each of numbers 1,6,8,9 in that number, it's the same as Div1 A :D
For arbitrary numbers: if the input is small, you could do DP on (remainder,how many digits of each type you have left); if it's large, there are either few ways to solve it or a permutation should always exist, like numbers "16666666","61666666",...,"66666616" which give different remainders mod 7 — so it's enough to consider a random permutation of other numbers before it and choose the ending few digits that are good.
Ok, so for larges numbers, we can't have perfect polynomial solutions (I mean, without using random) ? Anyway, thanks for this answer.
I think we could get constant time solutions. Well, constant if we had just the occurences of 10 digits (if we don't limit ourselves to 4). Actually, digits with 7 possible remainders.
As long as the number is diverse enough, there should be a small subset of digits such that there's a permutation of them with remainder x for all 0 ≤ x < 7; if there's such a subset, the length of the number is, in fact, irrelevant — no matter what permutation of the remaining digits we use at the start of the number, we can always pad it with the suitable permutation of our subset.
The problem we got just specifies the subset for us: remainders "1,1,2,6". This is quite small, and I don't think any required subset (that doesn't contain any smaller required subset) will be much larger. Notice for example that the subset "many 6-s and 1" that I presented can be replaced by "many x-s and y", and it still holds for x, y giving different remainders mod 7 and even any prime modulus (not just 7) with 10 as the primitive root!
That leaves us with the task of bruteforcing all suitable subsets, hardwiring them into the code and just choosing the right one for any number :D
Thanks, very nice idea :)
Thanks for the round! The problems were very clever, even though I didn't solve them during the contest!
Timus 1095 is exactly the same with today's A div 1. The only difference is digits used but I suppose that there're many different sets of 4 digits that work in this case — it doesn't mean though that problems will be different as well.
:(((
Не особо хотелось, но раз уж такое дело...
Достаточно долго придумывал и писал решение по А. Ну да ладно, вроде написал, отправляю. ВА4. Что?! Код же практически идеален. Ладно, ищу багу. Нахожу — хвост делал с таким же остатком, как у первой части числа, а не с (7 — остаток). Исправил, ну теперь точно правильно. Отправляю без теста на семплах. ВА2. Как так?! Нахожу ещё багу... После цикла с подсчётом первой части числа не умножаю остаток на 10000. Теперь уж потестил на семплах — претесты пройдены.
Задачу Б тоже достаточно долго придумывал для её простоты, но и ладно. Написал, засылаю — ВА4. Баги, баги... Таак, я в своём решении двигаю не строки, а столбцы, отлично. Меняю решение, отсылаю без теста на семплах — ВА2. Ну что за дела... При подсчёте подряд идущих единиц делаю cnt[i] += cnt[i] вместо cnt[i] += cnt[i + 1]. Шикарно. Отправляю снова без проверки на семплах (заметьте, какой я самоотверженный). И... ВА3 (да-да, это семпл). Снова ищу багу. Умножаю на (m — j) вместо (n — j). Одна бага замечательней другой. Исправил, отправил, прошёл претесты.
Задача С как-то не далась. Начал думать над Д. Долго мучался, извращался, придумал только за квадрат, эх, ладно, почему бы не пойти не поломать, видел в таблице плюсики за взломы. Смотрю решения по А. Вроде всё правильно. Особо негде и не набагаешь. Так, решение с BigInteger для проверки на делимость. Забано, но не поломать. Перехожу на задачу Б. Смотрю, смотрю, особо ни к кому и не придраться, возвращаюсь к оставшимся кодам по А. А вот и что-то интересное — следующее решение с оператором next_permatation(s), где s — исходная строка. Радуюсь, пишу тест, на котором должен быть ТЛ. Решение проходит... Непонятно. Пишу новый тест. И его проходит... Вот я лох, даже такую ерунду не могу взломать. Пока я осуждал себя, контест закончился. Решение то, конечно же, упало на систестах.
Но и это не всё. Решение Б падает с ТЛ. На контесте почему-то оценил решение O(n^2*logn), подставив n = 1000 вместо n = 5000, поэтому показалось более или менее годным. В последние минут двадцать глянул ещё раз решение перед тем, как блокировать. Думаю: "Ну, по сути, должно заходить. Можно, конечно, исправить сортировку слияниями на сортировку подсчётом, чтобы уж точно заходило. Хотя... Не, и так очков раз два и обчёлся, не к чему терять ещё, блокирую".
В общем, я снизу таблицы. Большой минус, выход в фиолетовую лигу.
Сообщение носит исключительно развлекательный характер. Хотя можно и вынести что-то из него — не будьте такими лузерами, как я. Пишите контесты хорошо и всегда тестьте на претестах.
Я пока поношу тогда Ваши оранжевые штаны. С позволения...
Каждая лишняя попытка — минус 50 очков, что соответствует 25 минутам задержки для задачи (500) и 12 минутам задержки задачи (1000). Поэтому лучше потратить две минуты на локальный прогон претестов и чего-нибудь еще, чем не потратить.
А как сообщество смотрит на идею о том что бы в обязательном порядке добавлять макс тесты (по времени чтения данных) в претесты, вроде этим мы ничего не теряем (кроме времени исполнения претестов) просто отсекаем тупые баги из серии считал string (при помощи cin, geline) или char[] (scanf)?
Я конечно понимаю аргументы из серии "писать всегда оптимально", но все же не всегда это возможно, да и оптимальность понятие растяжимое.
К сожалению, мы не принимаем во внимание cin приведет над срока.
Можно, например, добавлять в условия что-то вроде "так как размер входных/выходных данных большой, используйте быстрые методы ввода/вывода".
Anyone get TLE at DIV1-B, try scanf("%s") instead of cin. what a sad story, my O(N^2) solution with very small constant coefficient TLE.
I had the same issue. I think the time constraints for B are too harsh.
Never mind, just remember to use scanf in future. I have been away from ACM for a couple of years and forget this rule :(
I did scanf but I scan character by character.
NEVER use cin without invoking sync_with_stdio first.
Can anyone explain test 4 of Pro.B div 1 (or Pro.D div 2) for me ? In the first row we have 10 ones so we can put ones adjacent so that we have a rectangle with size 1 x 10, or I misunderstood the problem ?
http://codeforces.net/contest/375/submission/5515862
You can swap ROWS not COLUMNS :)
What is the official solution for DIV1-D? When I read other's AC codes, to my surprise the moving-interval solution could pass-_-!!
Its time is N\sqrt(N),so it can pass it.In CN, we call it 'MO DUI'
questions were interesting and little bit tricy...Hats off to problem setters!!!
Can you post the editorial please.
http://codeforces.net/blog/entry/10084
Thanks
why so many down vote. is it wrong to ask for a help?
Probably because the editorial was there on the "recent actions" list, and you didn't bother to check it before asking about it.
То, что фиолетовый выигрывает второй раунд подряд на КФ — это новая мода? Может, в следующем КФ поучаствовать?
Посоны говорят, что это совсем не фиолетовый...