Доброго дня!
Совсем скоро 2 Мая, 19:30 MSK. стартует Codeforces Round #244 для участников из второго дивизиона. Как все вы знаете, участники из первого дивизиона могут посоревноваться вне конкурса.
Раунд был подготовлен мной (Bidhan), студентом университета Дхака, Бангладеш. Это мой первый раунд на Codeforces, и я старался сделать задачи контеста интересными и решаемыми для участников из второго дивизиона. Очень много усилий было потрачено на то, чтобы условия задач были как можно понятнее. Надеюсь, что раунд пройдет без накладок, а задачи вам понравятся.
Отдельное спасибо msh_shiplu, лектору университета Дхака, за его большой вклад в подготовку раунда (подготовка одной из задач, написание альтернативных решений, разработка тестов). Также спасибо Gerald за помощь в подготовке контеста.
Желаю всем удачи :-)
Распределение баллов по задачам: 500-1000-1500-2000-2500
(Y)
Just see this verdict :
6524921
N > your maxn, so your solution have runtime error, but sometimes it can be as endless time limit.
Too early a notification, after a long time.
Thanks :)
Gl Hf all.
There is always at least 2 unrated users in top 10 of div2 only contests... Are they really unrated or they are some of div1 users that they want to compete in the contest?? If I am true that is really unfair!
It was my first contest here, sorry :3
No I didn't mean you :)
But there is a lot of div1 users that register a new account to participate officialy and/or hack problems...
Prediction: Last place will be worse.
Prediction: First place will be ttthebest.
Prediction: ceil( Total places / 2 ) place will be Willionaire.
are you predictor ^_^
Prediction: Maximum Wrong Submission by EROR :D :D :D
Hey, the guy from your university is setting up a contest, make it right, solve all 5 this time.
But I decide the problem C and D. And you're not! xD
Your attempt say that you will not decide D
one more prediction: I'll become purple
One more prediction: my rating will stay same :)
May be your prediction is going to be right... :P
UPD last place is for worse. He really tried heart and soul to take that position.
Looks like Your Prediction got Correct.. worse is going to be last or 2nd last... It seems he was trying heart and soul to got the last place...... :D
Am I psychic or what?
well, unfortunately not! worse has finished last in atleast five rounds before today, so ur guess wasn't really a no-brainer! :D
Finally a Bangladeshi problem setter contest :D hope everyone will enjoy it :)
Just thanks)
I guess this is the first time a round is prepared by someone from the Indian Sub-Continent. I hope someone from India (including me) will prepare a round soon. India also has good problem setters as seen in codechef contests.
But only one red?
I dont think a player's rating decides how a problem setter he is and how many problems he can prepare. Otherwise tourist would have been writing awesome problems for a long time now.
Maybe he's just too busy winning contests to run them? :-)
At last , a bangladeshi problemsetter , hope , more will arise , of course with div1 problems :) :)
Hi! Im new here, and i can't find how to register for this event. On the contests page i see the round and it tells me "Before registration 46:26:28" and nothing else... how do I sign up?
hf all!!
registration will be opened at night before contest
Sorry, that' s about Testing Round... Posted to the wrong place...X|
мы тоже надеемся, что все будет круто :-)
Разбалловка стандартная? Интернационал это круто :D
What about score distribution ?
Updated :)
good luck for everyone
весьма увлекательный контест!
заставил подумать)
I'm really stupid, since I've come up with a correct idea on E just 5 minutes before the end...
But C and D are awful. The idea of both is just obvious, but both problems require knowledge of standard algorithms.
So what's the idea behind D?
My solution was trie but don't know is it correct or not or pass within time :(
hashes
TLE 14
hashes with binsearch ?
Yes, how else can you find out, how many substrings with a particular hash?
i meant that we can find the optimal length of substring using binary search
so it would be about log n (binsearch) * (n log n (building hashes, searching for optimal substr with middle len)
am i right?
You can't really do that, because it is not monotonic. I mean, if there exists a unique common substring of length n, that does not mean there exists one of length n+1, so binary search may fail.
No.
hashes + map
That's O(n^2*(log n)), i did that and got TLE 14.
I have 15ms with it. Look at my code. I am near 90 place.
I did that and I've passed pretest in 30 ms :)
But I afraid of anti hash tests ...
For that reason I implemented 2 hashes : ))
I've solved it using a z-function.
The idea was to find a minimum-length unique substring for each starting position at both
s1ands2. Then we loop over all possible starting positions ats1ands2, find LCP of the suffixes and choose a minimum-length substring that is not longer than the LCP, but is unique in boths1ands2.If something is still not obvious, just look at my code, it's pretty straightforward.
I agree, problem E was also standard (I saw like 3 problems like this one before (although this one had extra constraints, making it more interesting to solve)). C was all about knowing Kosararaju's/Tarjan's algorithm. D was about hashing the right substrings (poor me getting WA on pretest 10). Seeing this from another perspective, these problems were a good programming exercise.
At D I passed the pretests with a very bad hashing algorithm. Also I passed in O(N^2 log N) , not O(N^2). Although , for me was a great ocasion to test the speed of set and unordered_set as I was participating unoficially.
E was very nice, but quite known ideed.
EDIT: At D , there was a solution in O(N^2) without hashes , so + for the authors.
E was not only a variant of a well-known problem, but its solution is quite easy to deduce even when you don't know it beforehand because the additional constraints don't change a thing about the fact, that (one) optimal strategy is still to place the police station to the [n/2]-th criminal's position..
i think E was easier than C and a lot easier than D
Yeah, same for me with E. In fact, i just debugged it :P (Also, hashing for D passed pretest for me without TLE).
Well, D has really simple
(n2) solution, which doesn't use any standard algorithms or hashing: 6529607.
Is problem D solvable by hashing?
Yes.
UPD. Looks like not really. Too slow? But we'll see after systest
UPD2. Some solutions with hashes got accepted, for example, 6528389
UPD3. But my solution got TL17. Sad :(
Anybody knows what is in that 17th test such different? My suffix automaton gives WA.
No, time limit is too strict.
Pretests passed.
Hopefully that anti-hash testes will be not)
It's only bad for you if you calculate hashes by modulo 2^64 :)
Modulo 2^64 always worked for me.
Oh, you're lucky, there were no anti-hash test :)
anti-hash
testestests :Dкакие-то слишком простые D и E, скорее обе как C
Перед концом тура мои взломы сперва отображались как "Неизвестный вердикт", через некоторое время после этого как "Игнорирован", хотя участник, которого я взламывал, не обозначен, как взломанный после конца тура в предварительной таблице комнаты. Что это может означать? Заранее спасибо за ответ.
Вы в этих взломах использовали srand(time(0)), много раз уже говорилось, что так делать нельзя.
what about the tutorials?
here it is. :)
Не, я так не играю! Какой-то dibil1000 ниже меня!-____- Как и обещал, решил С и Д =)
Завтра попробую с C начать решать. А то с Е не всегда получается...Так это не шутка была?:)
Ворс никогда не шутит! Или ты не заметил? У меня только бомбит за то, что нашелся человек, который ниже меня. Конкурент!
Прям конкуренция века
А ты как думал? Занять последнее место — это дело чести!
Решил Д ???
What was the intended solution for D? I'm guessing it doesn't involve hashing (because all the mods would time out). Will a trie work here (I guess yes, but I want to know other's opinion)?
Suffix Array??? O(NlogN) After the Contest you can see my code....
It's definitely an overkill for N, M <= 5000 :).
Every problem has at least 250 people who has "pretests passed". Are all the problems contain weak pretests?
yes, the pretests were weak, i got passed on the pretests of C with a typo, instead of "% 1000000007" for modulo, i wrote "& 1000000007"
Pretests are made to give possibility to hack. So it's absolutely normal, that you passed them with such bug
dont you think not checking the modulo thing would be a little too much of a possibility?
как В решать
Можно в лоб написать дерево максимумов, или отдельно выделить все числа которые больше нормы, и брать соседние, теперь между ними найдем кол-во нужных отрезков
а O(n^2) зайдет в В
Нет
No
too slow system testing!
System testing too slow.. :(
Зачем в С 120+ тестов? Тестирование настолько медленное, что я успею написать виртуально еще один контест, пока рейтинги обновят.
I am really confused about problem C 3rd sample, the first 1,2...7 nodes form an SCC and 8,9 and 10 form another. Now if I put a checkpost at 1 and 8 , then I have total cost 1+4 = 5. How the min cost is 15 ?
8, 9, 10 is not SCC. 1..7, 8, 9..10 -> 3 SCC, total = 1 + 4 + 10 = 15.
The flaw in the logic is that 8, 9 and 10 don't actually form a SCC. The subgraph formed by 8-10 has 2 SCCs (8 and 9-10). We deduce that the total cost should be 1 (for the 1-7 SCC) + 4 + 10 = 15, as mentioned in the statement.
Very slow system testing
Problem B, Div 2 was a bit misleading. When you say contigous segments what do you mean? continous by index or continous by severity level. Took me some time to figure that out . Was it intentional ?
contigous by index, I believe that.
Well, it wasn't clear in the problem statement.
В первой задаче 70 тестов. На финальных тестах по первой упало пока что только одно решение. Стоило того.
not sure if the system tests are very slow or the time just passes slowly because i'm afraid of my C judge :|
Looks like System testing is Slower.....:D
What is ''Idleness time limit exeeded''?First time saw this verdict in cf. :/
I guess it means something like "your program spent too much time without using any CPU resources". Did you include some system call like sleep or pause?
I didn't get this verdict. :) saw it on judge status. this submission: 6524921
WoW!! More than 100 tests for each problem!!
I counted 151 on my C submission LOL. And most of them seem to be maximal cases. Is this really necessary? I mean, I know test cases must be exhaustive, but I find these quantities not very... logistic.
All the hacks were added to the testset before system test. That's why number of tests increased.
Is this the first round with that feature?
No, every rounds have this feature...
Nice idea! But it makes system testing very slow... And it's also unfair for non-deterministic solutions.
No this idea is really good...
Being a problem with non-deterministic solution is unfair...
But there ARE these kinds of problems in cf! (Link)
Is there any trie solution passed for D?
What was the intended solution for D???
I used suffix automaton to build the trie. I think building the trie by inserting every suffix of the string must cause MLE.6533026 ACed after the contest.
No automation, no MLE, just trie. http://mirror.codeforces.com/contest/427/submission/6533247
Good job!
By the way, it is automaton not automation.
I know it from long time and first time to notice that
What is complexity of this algorithm? It is O(N2 * 26), isn't it?
Yeap, it is, but in average, it's very fast :)
I tried a naive trie solution, which got hacked (I guess too many nodes were created).
Then I switched to radix tree (aka patricia trie) in 6531792. The basic idea is: Adding a new string to the tree results in at most one new branch / node.
i LOLed when i read this! :D
Translation pls? :D
"Author, when you don't add max test, you make me upset." It's a reference to Viktor Tsoi's "Malysh" song.
Отличный контест, задачи очень хорошо подобраны)
Now really, a translation please. Thanks.
When will be the ratings update?It took a lot to evaluate the sources...I hope it won'y take so much for updating the ratings. P.S.Sorry.You updated preety fast.
Wow, veeery slooow systest, but very fast rating update.
relevant comment
but i guess this time it was the opposite! :D
Round Stats
TO WORSE,
I see youre very workless But i gonna pass him next contest HURRAY DIBILS
the battle for last place intensifies! :D
I love this round.I spend a lot of time on problem D,and when I finally solved it ,I felt very happy.By the way,I think the problem E is apparently easier than D.