### Bidhan's blog

By Bidhan, 6 years ago, ,

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.

• +234

 » 6 years ago, # |   0 (Y)
•  » » 6 years ago, # ^ |   +2 Just see this verdict : 6524921
•  » » » 6 years ago, # ^ |   +3 N > your maxn, so your solution have runtime error, but sometimes it can be as endless time limit.
 » 6 years ago, # |   +4 Too early a notification, after a long time.Thanks :)Gl Hf all.
•  » » 6 years ago, # ^ |   +10 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!
•  » » » 6 years ago, # ^ |   +4 It was my first contest here, sorry :3
•  » » » » 6 years ago, # ^ |   0 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...
 » 6 years ago, # |   +1 Prediction: Last place will be worse.
•  » » 6 years ago, # ^ |   0 Prediction: First place will be ttthebest.
•  » » » 6 years ago, # ^ |   +6 Prediction: ceil( Total places / 2 ) place will be middle_impulse.
•  » » » » 6 years ago, # ^ |   0 are you predictor ^_^
•  » » » » 6 years ago, # ^ |   +5 Prediction: Maximum Wrong Submission by EROR :D :D :D
•  » » » » » 6 years ago, # ^ |   +6 Hey, the guy from your university is setting up a contest, make it right, solve all 5 this time.
•  » » 6 years ago, # ^ |   0 But I decide the problem C and D. And you're not! xD
•  » » » 6 years ago, # ^ |   0 Your attempt say that you will not decide D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 one more prediction: I'll become purple
•  » » » 6 years ago, # ^ |   +22 One more prediction: my rating will stay same :)
•  » » 6 years ago, # ^ | ← Rev. 5 →   +11 May be your prediction is going to be right... :PUPD last place is for worse. He really tried heart and soul to take that position.
•  » » 6 years ago, # ^ |   +4 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
•  » » 6 years ago, # ^ |   0 Am I psychic or what?
•  » » » 6 years ago, # ^ |   0 well, unfortunately not! worse has finished last in atleast five rounds before today, so ur guess wasn't really a no-brainer! :D
 » 6 years ago, # |   +19 Finally a Bangladeshi problem setter contest :D hope everyone will enjoy it :)
 » 6 years ago, # |   0 Just thanks)
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   -10 But only one red?
•  » » » 6 years ago, # ^ |   +8 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.
•  » » » » 6 years ago, # ^ |   +21 Maybe he's just too busy winning contests to run them? :-)
 » 6 years ago, # |   +5 At last , a bangladeshi problemsetter , hope , more will arise , of course with div1 problems :) :)
 » 6 years ago, # |   0 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!!
•  » » 6 years ago, # ^ |   +1 registration will be opened at night before contest
 » 6 years ago, # | ← Rev. 2 →   0 Sorry, that' s about Testing Round... Posted to the wrong place...X|
 » 6 years ago, # |   0 Wish luck for every one. GL & HF ....
 » 6 years ago, # |   0 Thank You
 » 6 years ago, # |   0 What about score distribution ?
•  » » 6 years ago, # ^ |   +7 Updated :)
 » 6 years ago, # |   0 good luck for everyone
 » 6 years ago, # |   +40 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.
•  » » 6 years ago, # ^ |   +3 So what's the idea behind D?
•  » » » 6 years ago, # ^ |   0 My solution was trie but don't know is it correct or not or pass within time :(
•  » » » 6 years ago, # ^ |   +1 hashes
•  » » » » 6 years ago, # ^ |   +11 TLE 14
•  » » » » » 6 years ago, # ^ |   0 hashes with binsearch ?
•  » » » » » » 6 years ago, # ^ |   0 Yes, how else can you find out, how many substrings with a particular hash?
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 i meant that we can find the optimal length of substring using binary searchso it would be about log n (binsearch) * (n log n (building hashes, searching for optimal substr with middle len)am i right?
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » » » » » » 6 years ago, # ^ |   0 No.
•  » » » » » 6 years ago, # ^ |   0 hashes + map
•  » » » » » » 6 years ago, # ^ |   0 That's O(n^2*(log n)), i did that and got TLE 14.
•  » » » » » » » 6 years ago, # ^ |   0 I have 15ms with it. Look at my code. I am near 90 place.
•  » » » » » » » 6 years ago, # ^ |   0 I did that and I've passed pretest in 30 ms :) But I afraid of anti hash tests ...
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 For that reason I implemented 2 hashes : ))
•  » » » 6 years ago, # ^ |   +5 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 6 years ago, # ^ |   +5 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
•  » » 6 years ago, # ^ |   0 Yeah, same for me with E. In fact, i just debugged it :P (Also, hashing for D passed pretest for me without TLE).
•  » » 6 years ago, # ^ | ← Rev. 4 →   +6 Well, D has really simple (n2) solution, which doesn't use any standard algorithms or hashing: 6529607.
 » 6 years ago, # |   +1 Is problem D solvable by hashing?
•  » » 6 years ago, # ^ | ← Rev. 4 →   +7 Yes.UPD. Looks like not really. Too slow? But we'll see after systestUPD2. Some solutions with hashes got accepted, for example, 6528389UPD3. But my solution got TL17. Sad :(
•  » » » 5 years ago, # ^ |   0 Anybody knows what is in that 17th test such different? My suffix automaton gives WA.
•  » » 6 years ago, # ^ |   -9 No, time limit is too strict.
•  » » 6 years ago, # ^ |   0 Pretests passed.Hopefully that anti-hash testes will be not)
•  » » » 6 years ago, # ^ |   0 It's only bad for you if you calculate hashes by modulo 2^64 :)
•  » » » » 6 years ago, # ^ |   0 Modulo 2^64 always worked for me.
•  » » » » » 6 years ago, # ^ |   0 Oh, you're lucky, there were no anti-hash test :)
•  » » » 6 years ago, # ^ |   0 anti-hash testes tests :D
 » 6 years ago, # |   0 what about the tutorials?
•  » » 6 years ago, # ^ |   0 here it is. :)
 » 6 years ago, # |   +4 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)?
•  » » 6 years ago, # ^ |   -7 Suffix Array??? O(NlogN) After the Contest you can see my code....
•  » » » 6 years ago, # ^ |   0 It's definitely an overkill for N, M <= 5000 :).
 » 6 years ago, # | ← Rev. 2 →   0 Every problem has at least 250 people who has "pretests passed". Are all the problems contain weak pretests?
•  » » 6 years ago, # ^ |   0 yes, the pretests were weak, i got passed on the pretests of C with a typo, instead of "% 1000000007" for modulo, i wrote "& 1000000007"
•  » » » 6 years ago, # ^ |   0 Pretests are made to give possibility to hack. So it's absolutely normal, that you passed them with such bug
•  » » » » 6 years ago, # ^ |   0 dont you think not checking the modulo thing would be a little too much of a possibility?
 » 6 years ago, # |   -9 как В решать
•  » » 6 years ago, # ^ |   0 Можно в лоб написать дерево максимумов, или отдельно выделить все числа которые больше нормы, и брать соседние, теперь между ними найдем кол-во нужных отрезков
•  » » » 6 years ago, # ^ |   -9 а O(n^2) зайдет в В
•  » » » » 6 years ago, # ^ |   +2 Нет
•  » » » » 6 years ago, # ^ |   0 No
 » 6 years ago, # |   +11 too slow system testing!
 » 6 years ago, # |   +3 System testing too slow.. :(
 » 6 years ago, # |   0 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 ?
•  » » 6 years ago, # ^ |   0 8, 9, 10 is not SCC. 1..7, 8, 9..10 -> 3 SCC, total = 1 + 4 + 10 = 15.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
 » 6 years ago, # |   0 Very slow system testing
 » 6 years ago, # |   0 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 ?
•  » » 6 years ago, # ^ |   0 contigous by index, I believe that.
•  » » » 6 years ago, # ^ |   0 Well, it wasn't clear in the problem statement.
 » 6 years ago, # |   +4 not sure if the system tests are very slow or the time just passes slowly because i'm afraid of my C judge :|
 » 6 years ago, # |   0 Looks like System testing is Slower.....:D
 » 6 years ago, # |   0 What is ''Idleness time limit exeeded''?First time saw this verdict in cf. :/
•  » » 6 years ago, # ^ |   +8 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?
•  » » » 6 years ago, # ^ |   0 I didn't get this verdict. :) saw it on judge status. this submission: 6524921
 » 6 years ago, # | ← Rev. 3 →   +17 WoW!! More than 100 tests for each problem!!
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   +9 All the hacks were added to the testset before system test. That's why number of tests increased.
•  » » » 6 years ago, # ^ |   0 Is this the first round with that feature?
•  » » » » 6 years ago, # ^ |   +2 No, every rounds have this feature...
•  » » » 6 years ago, # ^ |   +1 Nice idea! But it makes system testing very slow... And it's also unfair for non-deterministic solutions.
•  » » » » 6 years ago, # ^ |   +4 No this idea is really good... Being a problem with non-deterministic solution is unfair...
•  » » » » » 6 years ago, # ^ |   0 But there ARE these kinds of problems in cf! (Link)
 » 6 years ago, # |   +8 Is there any trie solution passed for D?
•  » » 6 years ago, # ^ |   0 What was the intended solution for D???
•  » » 6 years ago, # ^ |   +1 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.
•  » » » 6 years ago, # ^ |   0 No automation, no MLE, just trie. http://codeforces.ru/contest/427/submission/6533247
•  » » » » 6 years ago, # ^ |   +3 Good job!By the way, it is automaton not automation.
•  » » » » » 6 years ago, # ^ |   0 I know it from long time and first time to notice that
•  » » » » 6 years ago, # ^ |   0 What is complexity of this algorithm? It is O(N2 * 26), isn't it?
•  » » » » » 6 years ago, # ^ |   0 Yeap, it is, but in average, it's very fast :)
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 I tried a naive trie solution i LOLed when i read this! :D
 » 6 years ago, # |   +10
•  » » 6 years ago, # ^ |   0 Translation pls? :D
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 "Author, when you don't add max test, you make me upset." It's a reference to Viktor Tsoi's "Malysh" song.
 » 6 years ago, # |   0 Отличный контест, задачи очень хорошо подобраны)
•  » » 6 years ago, # ^ |   +3 Now really, a translation please. Thanks.
 » 6 years ago, # |   +29
 » 6 years ago, # | ← Rev. 3 →   0 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.
 » 6 years ago, # |   +10 Wow, veeery slooow systest, but very fast rating update.
•  » » 6 years ago, # ^ |   +3 relevant comment but i guess this time it was the opposite! :D
 » 6 years ago, # |   +12
 » 6 years ago, # |   +6 TO WORSE,I see youre very workless But i gonna pass him next contest HURRAY DIBILS
•  » » 6 years ago, # ^ |   +6 the battle for last place intensifies! :D
 » 6 years ago, # |   0 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.