Endagorion's blog

Codeforces Round #109
By Endagorion, 13 years ago, translation, In English

Hello everyone. I'm Mikhail Tikhomirov and I'm the author of today round. I want to say big thanks to Gerald Agapov (Gerald) and Artem Rakhov (RAD) for great help in preparing this contest, and also Maria Belova for translating the statements into English (Delinur).

Today round is for contestants from both divisions. Each division has five problems, which intersect, as always. Score distributions are also standard (500-1000-1500-2000-2500). In short, it's a usual round. Or not?.. =)

Hope that problems will be interesting, tests will be secure, server will be fast, solutions — (mostly) correct, and the round will be rated. =) Wish you best of luck!

Round finished, thank you all for participating!

Results:

div1:

  1. tourist
  2. peter50216
  3. Egor
  4. YuukaKazami
  5. gchebanov
  6. kelvin
  7. shangjingbo
  8. rowdark
  9. kterry
  10. rng_58

div2:

  1. jonathanasdf
  2. Tranvick
  3. ProForward
  4. Eurekash
  5. neex.emil

Editorial is finally up!

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

Comments Comments (46)
| Write comment?
»
13 years ago, # |
← Rev. 3   Vote: I like it -37 Vote: I do not like it

Thank you Endagorion~

→ Reply
»
13 years ago, # |
  Vote: I like it -55 Vote: I do not like it

Wish you best of luck! ;)

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

Thank you Endagorion, nice problem set! Especially loved the Flatland Fencing (problem D in Div1).

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

I must say, C of Div.1 is very very unusual for me > <

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

    Anyone could explain the hash-based solution to problem C? It seems to be very intersting.

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

When will the system test start?

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

    After div2 testing finished I think. Today div2 got test first :)

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

OK, still far from being red. Nice problem set, anyway I hoped I could do it better.

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

I just opened solution of zzy_troy for 155D - Colliders. And his solution happened to be the same as resubmited solution of dnc1994 after I challenged him.

Check it out: 1225624 1228387.

I think "someone" has multiple accounts.

UPD: also check out the hacked solution of dnc1994 1226917

UPD2: during the contest it seemed very suspicious to me that he resubmitted using pascal, since the first submission was written in C++

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

    Yes, I remember him from one another round, where the code looked similar to some other account. There must be something going on.

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

      I'm very sorry that it happens. But as you see , I use language pascal. Maybe he (dnc1994) copied my code.

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

-7500 in Div 2 ?

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

When will my rating be update?

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

    Let Div 1 system test be over first.Then ratings are updated

    → Reply
»
13 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Chapeau :)

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

I am getting TLE in Test Case 30 for the problem Colliders.Can someone tell me where to optimize it.Here's the code ->Link .I cant get it.Thanks in advance.:)

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

Hey i'm curious as to how solutions to C handle cases like aaaabbbbaaabbba I tried a few correct solutions out but they give TLE or 0 as the answer o.O

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

The solution of problem c in div1 is using "hash" ? It's so unusal... And "map" will get TLE?

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

    What exactly do you mean by "map" and how do you know that map is too slow only by a constant factor? At least I could imagine that in some cases map compares people with many friends too often. (As an extreme example: Let's not use a map but sort the people (I guess this doesn't make a huge difference). The runtime depends on the internals of the sorting algerithm: The sorting algorithm might be "stupid" and first compare the two persons with the most friends with each other n times and then do quicksort. This sorting algorithm works in O(n log(n)) if comparison could be done in O(1) but it can take O(nm) when persons have to be compared lexicographically.).

    → Reply
»
13 years ago, # |
← Rev. 3   Vote: I like it -34 Vote: I do not like it

I think there must be many participants ignored the vital constraint in problem A:

Also, each pair has different letters and each letter occurs in no more than one forbidden pair.
It is guaranteed that each letter is included in no more than one pair.

I think writer should make it bold. It's codeforces, not readforces...

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

    That happened to me. But he did write it twice....

    If you take out that restriction and allow letters to be in more than one pair, can it be solved with DP?

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

      Most of the solutions that I read during the round ignored that restriction and used DP (so does mine). I was surprised when I tried to challenge solution that used the restriction and my test turned out to be incorrect %)

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

        What kind so DP did you use?

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

          D(i,j) — minimum deleted characters for prefix of length i, and last undelete character is equal j.

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

Interestring, my rating on the contest just went up, now I am 10th DIV2, I was 11th when contest ended. Also, may I know how soon will editorials be posted ?

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

This contest is my favorites... Every problem are clearly presented... Thank you very much Endagorion

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

I think all problems is nice.Thank you Endagorion!Finally,pray for myself not to make mistakes.

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

Is there any way to solve div1-C without hashing?

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

    I think I found an O((n+m)log(n)) solution without hashing. Unfortunately it seems to be too slow by a constant factor. It works as follows:

    (1) Let v(i) be the list of friends of i.

    (2) Sort v(i). Create the list 1..n. Sort it by length(v(i)).

    Then sort each chunk of this list with constant length(v(i)) by v(i) (lexicographically). , so this step takes at most time O((n+m)log(n)).

    Afterwards you can easily divide this list into chunks with equal v(i) in time O(n+m).

    This gives the number of doubles (i,j) which are not friends.

    (3) Add i to v(i) and repeat step 2. This time you get the number of doubles (i,j) which are friends.

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

      Lost of hashing cost about 1s, and time limited is 3s. Many solution in div1 got TLE, because of the big constant factor.I hacked by someone's big test , and got TLE too.. :(

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

    It can be solved using trie that should implemented using hash-table (it is not hashing:) ).

    You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex.

    So, we have exact solution in O(MlogM) time with small constant.

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

      You ideas are good one~ Thank you very much!

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

      Is it really necessary to sort if you are using trie?

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

        You should sort all numbers inside every list (because lists like {2,3,1} and {1,3,2} should be equal) and use a trie instead of sorting all of lists.

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

          I have a problem. how about memery limit? For each vertices on trie,have 10^6 chilid!!

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

Are the editorials coming before the next round??

→ Reply