Bidhan's blog

Codeforces Round #244 (Div. 2)
By Bidhan, 11 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?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(Y)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Just see this verdict :
    6524921

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

      N > your maxn, so your solution have runtime error, but sometimes it can be as endless time limit.

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

Too early a notification, after a long time.

Thanks :)

Gl Hf all.

→ Reply
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      It was my first contest here, sorry :3

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          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
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Prediction: Last place will be worse.

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

    Prediction: First place will be ttthebest.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Prediction: ceil( Total places / 2 ) place will be Willionaire.

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

        are you predictor ^_^

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

        Prediction: Maximum Wrong Submission by EROR :D :D :D

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Hey, the guy from your university is setting up a contest, make it right, solve all 5 this time.

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

    But I decide the problem C and D. And you're not! xD

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

      Your attempt say that you will not decide D

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

    one more prediction: I'll become purple

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      One more prediction: my rating will stay same :)

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

    May be your prediction is going to be right... :P

    Image Hosted At MyspaceGens

    UPD last place is for worse. He really tried heart and soul to take that position.

    Image Hosted At MyspaceGens

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

    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

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

    Am I psychic or what?

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

      well, unfortunately not! worse has finished last in atleast five rounds before today, so ur guess wasn't really a no-brainer! :D

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

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

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

Just thanks)

→ Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    But only one red?

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

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        Maybe he's just too busy winning contests to run them? :-)

        → Reply
»
11 years ago, # |
  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
»
11 years ago, # |
  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
»
11 years ago, # |
← 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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about score distribution ?

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

good luck for everyone

→ Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    So what's the idea behind D?

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

      My solution was trie but don't know is it correct or not or pass within time :(

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      hashes

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

        TLE 14

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

          hashes with binsearch ?

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

            Yes, how else can you find out, how many substrings with a particular hash?

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

              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?

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

                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.

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

                No.

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

          hashes + map

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

            That's O(n^2*(log n)), i did that and got TLE 14.

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

              I have 15ms with it. Look at my code. I am near 90 place.

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

              I did that and I've passed pretest in 30 ms :)
              But I afraid of anti hash tests ...

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

                For that reason I implemented 2 hashes : ))

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

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← 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
    • »
      »
      »
      11 years ago, # ^ |
      ← 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
    • »
      »
      »
      11 years ago, # ^ |
        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
  • »
    »
    11 years ago, # ^ |
      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
  • »
    »
    11 years ago, # ^ |
    ← 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
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is problem D solvable by hashing?

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

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

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

      Anybody knows what is in that 17th test such different? My suffix automaton gives WA.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    No, time limit is too strict.

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

    Pretests passed.

    Hopefully that anti-hash testes will be not)

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

      It's only bad for you if you calculate hashes by modulo 2^64 :)

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

        Modulo 2^64 always worked for me.

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

          Oh, you're lucky, there were no anti-hash test :)

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

      anti-hash testes tests :D

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

what about the tutorials?

→ Reply
»
11 years ago, # |
  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
»
11 years ago, # |
← 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
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        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
      • »
        »
        »
        »
        11 years ago, # ^ |
          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
»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

как В решать

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

    Можно в лоб написать дерево максимумов, или отдельно выделить все числа которые больше нормы, и брать соседние, теперь между ними найдем кол-во нужных отрезков

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

too slow system testing!

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

System testing too slow.. :(

→ Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      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
  • »
    »
    11 years ago, # ^ |
    ← 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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very slow system testing

→ Reply
»
11 years ago, # |
  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
»
11 years ago, # |
  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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  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
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't get this verdict. :) saw it on judge status. this submission: 6524921

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      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
  • »
    »
    11 years ago, # ^ |
      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
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is this the first round with that feature?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        No, every rounds have this feature...

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Nice idea! But it makes system testing very slow... And it's also unfair for non-deterministic solutions.

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

        No this idea is really good...
        Being a problem with non-deterministic solution is unfair...

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

          But there ARE these kinds of problems in cf! (Link)

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

Is there any trie solution passed for D?

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

    What was the intended solution for D???

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

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

    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.

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

      I tried a naive trie solution

      i LOLed when i read this! :D

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

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

    Translation pls? :D

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

      "Author, when you don't add max test, you make me upset." It's a reference to Viktor Tsoi's "Malysh" song.

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

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

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

→ Reply
»
11 years ago, # |
← 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
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

Round Stats

→ Reply
»
11 years ago, # |
  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
»
11 years ago, # |
  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