Good day everyone.

Codeforces round #244 for division 2 participants will start at May 2, Friday, 19:30 MSK. As you all know, participants from division 1 can also take part from out of the competition.

The round was prepared by me (Bidhan), student of University of Dhaka, Bangladesh. This is my first codeforces round. I have tried to prepare interesting and solvable problems for division 2 participants. Special effort was given to make the problem statements as clear as possible. Hoping that everything will go right and everyone will enjoy the round.

Special thanks to msh_shiplu, lecturer of University of Dhaka, for his contribution to the contest by finding time to set one of the problems, writing alternates, reviewing problem statements and giving expert advice on dataset generation in spite of his hectic schedule.

Also, a BIG thanks to nice guy Gerald, for helping throughout the preparation process.

I wish all the participants good luck :)

**Update0** : Score distribution is 500-1000-1500-2000-2500.

**Update1** : A **short editorial** of the contest is here. The post will be enlarged to detailed editorial later.

The Russian translation of this post is here.

(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

UPDlast 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

fiverounds before today, so ur guess wasn't really a no-brainer! :DFinally 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|

Wish luck for every one. GL & HF ....

Thank You

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

`s1`

and`s2`

. Then we loop over all possible starting positions at`s1`

and`s2`

, find LCP of the suffixes and choose a minimum-length substring that is not longer than the LCP, but is unique in both`s1`

and`s2`

.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 (

n^{2}) 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

:D~~testes~~testswhat about the tutorials?

here it is. :)

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.. :(

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.

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://codeforces.ru/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(N^{2}* 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.