Bidhan's blog

Codeforces Round #244 (Div. 2)
By Bidhan, 12 years ago, In English

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.

  • Vote: I like it
  • +234
  • Vote: I do not like it

Comments Comments (123)
| Write comment?
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

(Y)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Too early a notification, after a long time.

Thanks :)

Gl Hf all.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      It was my first contest here, sorry :3

      → Reply
      • »
        »
        »
        »
        12 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
12 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Prediction: Last place will be worse.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Finally a Bangladeshi problem setter contest :D hope everyone will enjoy it :)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Just thanks)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

At last , a bangladeshi problemsetter , hope , more will arise , of course with div1 problems :) :)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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!!

→ Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Sorry, that' s about Testing Round... Posted to the wrong place...X|

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What about score distribution ?

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good luck for everyone

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +40 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    So what's the idea behind D?

    → Reply
  • »
    »
    12 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      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

      → Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yeah, same for me with E. In fact, i just debugged it :P (Also, hashing for D passed pretest for me without TLE).

    → Reply
  • »
    »
    12 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it +6 Vote: I do not like it

    Well, D has really simple (n2) solution, which doesn't use any standard algorithms or hashing: 6529607.

    → Reply
»
12 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Is problem D solvable by hashing?

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what about the tutorials?

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

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)?

→ Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Every problem has at least 250 people who has "pretests passed". Are all the problems contain weak pretests?

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    yes, the pretests were weak, i got passed on the pretests of C with a typo, instead of "% 1000000007" for modulo, i wrote "& 1000000007"

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Pretests are made to give possibility to hack. So it's absolutely normal, that you passed them with such bug

      → Reply
      • »
        »
        »
        »
        12 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        dont you think not checking the modulo thing would be a little too much of a possibility?

        → Reply
»
12 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

как В решать

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

too slow system testing!

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

System testing too slow.. :(

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    8, 9, 10 is not SCC. 1..7, 8, 9..10 -> 3 SCC, total = 1 + 4 + 10 = 15.

    → Reply
  • »
    »
    12 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very slow system testing

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

not sure if the system tests are very slow or the time just passes slowly because i'm afraid of my C judge :|

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Looks like System testing is Slower.....:D

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is ''Idleness time limit exeeded''?First time saw this verdict in cf. :/

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
»
12 years ago, hide # |
← Rev. 3  
Vote: I like it +17 Vote: I do not like it

WoW!! More than 100 tests for each problem!!

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    All the hacks were added to the testset before system test. That's why number of tests increased.

    → Reply
»
12 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Is there any trie solution passed for D?

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Отличный контест, задачи очень хорошо подобраны)

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

→ Reply
»
12 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Wow, veeery slooow systest, but very fast rating update.

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

Round Stats

→ Reply
»
12 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

TO WORSE,

I see youre very workless But i gonna pass him next contest HURRAY DIBILS

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply