ir5's blog

Codeforces Beta Round #71
By ir5, 14 years ago, In English
Hello.

Today I (ir5) and rng_58 are the authors of Codeforces Beta Round #71. During the contest, you may meet some animals and be asked to solve their tasks.

We sincerely thank for RAD for solving and testing the problems, for Maria Belova for checking the English problem statements, and for MikeMirzayanov for this great system.

Good luck.

UPD:

The round is over. The result was following:

Top 10 participants in the first division:
2. Petr
4. dancho
5. wrong
6. ACRush
7. e-maxx
9. Egor

Top 3 participants in the second division:
3. Tayama

Congratulations!

Editorial (A,B,C,D,E)

Announcement of Codeforces Beta Round 71
  • Vote: I like it
  • +155
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Animals  ? !!!!
If so including images will be nice :)
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Oh no! Not bunnies again. :P
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    No bunnies as you can see ) Only animals from TopCoder, if i am not mistaken
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      There were rabbits involved. Aren't rabbits bunnies? ;) 
      → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Can my ratings change after this contest?, The last Div 1 i attended resulted in no change in my rating   
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    It isn't div1 contest.
    It is both divsions contest.
    Yes, your rating will change(But AFAIK div1 users will NOT affect rating distribution of div2 users)
    → Reply
14 years ago, # |
  Vote: I like it +21 Vote: I do not like it
Oh my god. Two red writers. It'll be something.

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hope the problems are amazing :D
→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Hope all is gonna be okay, with no crashes.
→ Reply
14 years ago, # |
  Vote: I like it +7 Vote: I do not like it
Admin has hinted us to keep a good book of mathematics during the contest !!!
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Codeforces should include a div2 only ranklist too as rating of div 2 contestants dont depend on div 1(i think).
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
How to solve the D problem?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    У меня сложность O(NKL + 22KK).
    Но я не до конца уверен в правильности своего решения.
    Сначала делаем подмену. Рассматриваем разности соседних лампочек (или что там было).
    Теперь одна операция - это изменение двух лампочек на расстоянии a[i]. А всего надо поменять  ≤ 2K лампочек. Строим граф с вершинами (0, 1, ..., n) и ребрами между u и v, если |u - v| = a[i]. В нем находим БФСом попарные расстояния между вершинами, которые надо менять. И в полученном графе из  ≤ 2K вершин находим минимальное по весу паросочетание (тут как раз у меня только примерное доказательство правильности).

    UPD. Прошла. Значит, все таки правильное решение.
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Sorry, it's in russian:
    Рассмотрим граф, вершины которого - стыки между клетками поля (ну и края тоже). Ребра - возможные отрезки, которые можно флипать, то есть все длины приложенные во всех местах. Если в каком-то стыке есть переход от принадлежащего Х к непринадлежащему, то в этом стыке должно быть нечетное количество краев флипнутых отрезков, иначе - четное. Ясно, что нечетных стыков будет не больше 20 (2K). Получили задачу: есть граф из 10^4 вершин и 10^6 ребер, выбрать сабсет ребер, чтобы у указанных (не более чем) 20 вершин была нечетная степень, у остальных - четная.
    строим матрицу кратчайших расстояний между этими нечетными вершинами (20 бфсами), потом динамика по сабсетам. Сабсет - уже удовлетворенные нечетные вершины, переход - выбираем, какую пару неудовлетворенных нечетных соединить путем.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Видел твое решение, явно не с помощью clocks() :-D
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Could someone give a short discription (a general idea, or just a short hint) in English ^^? :)
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve E problem
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
A,B,C very easy!!!
D,E very hard!!!
i think problem C must be harder than this!!!
thank's for author's!!!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Yes. This problemset leaves no room for error, the competition for most of participant was to solved 3 problems cleanly and faster, only to write not to think. With a deep respect for rng_58, i think that it's not a good idea to give 3 easy problems and 2 hard problems
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it
      I just can't go past this accusation (even if with "deep respect") without replying.  

      First of all, problems of this round were written not only by rng_58, but also by ir5.

      Second, all accusations in bad balance should never go to problem writer. It is hardly possible for a problem writer to estimate the difficulty of his/her problems correctly. In most cases, writer's estimate is lower than the actual difficulty. Much more exact estimate is usually done by people who test the problem.

      So, if you want to blame somebody for bad balance, it should first of all go to people who tested the problemset. But even a better thing would be not to blame anybody, especially if the problems are nice (what, in my opinion, is definitely the case with today's D and E).

      Practice shows that it's much easier to estimate difficulty of problems when the overall idea / approach is relatively straightforward, it then depends on the length / complexity of implementation and on popularity of algorithms / theory involved, overall it is quite easy to measure. When the idea is non-straightforward, making a difficulty estimate is very difficult. However, such problems are the best that one can meet at programming contests. While perhaps not everybody would agree with me, I personally think that bad balance is much better than boring problems.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it
      I want to say that we did not intend to set problems with such a bad balance - just we, the judges, did not estimate D was too hard. This misestimation occurred because the solution of D looks simple to think up and not so heavy to implement, if you know it.
      As for me, I expected at least 30+ contestants would solve D correctly, but the result was only 6 ACs.

      Overall, it seems that A,B was all right. C was solved by 200+ contestants, so I think C was actually not so very easy.
      D,E are solved by only about 10 people yet. I believe those(D,E) are nice problems and you may learn something here.

      ---
      Thank you for comments, Sir ivan.metelsky.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem D and E are very, very difficult for me!
I could find no clue to solve...
I'm waiting for editorials.
→ Reply
14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
I have a suggestion concerning pretests. Currently, if one locks a problem, he is unable to submit it again. Still, it would sometimes be nice to know if a particular (wrong) solution is caught by pretests.

Suppose one is hacking others' solutions and searches for a particular bug. When a solution seems to contain that bug, one is likely to challenge. Now, if the bug was in fact covered by pretests, he is surely wrong and is wasting time (and points if he is impatient with hacking). On the other side, if the bug was not covered by pretests, then the time is not surely wasted.

I propose that after locking a problem, one can submit solutions for that problem, they are checked on the pretests, and the result is reported back.

An existing way to get the same information is to first write and submit the wrong solution, and then submit the right one. But this way, it costs additional and points for the resubmission and for the time taken to write the wrong solution first. In my opinion, being able to get this information without the penalty would be fair and won't cause any harm when the problem is already locked.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it
    Why not just open pre-tests for those who locked task? I think it would be even more convinient
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I't bad idea because you can only see N first symbols per test. *trollface*

      But in general I completely agree with you.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Argh I had a 1-line bug for C =(
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It took me over an hour to find out that 1-line bug :-(
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the killer case in C-Problem!?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I can think of some -
    1) [For cases not handling nested bad substrings]
    abcdef
    2
    bc
    abcd

    2) [For cases with prefix or suffix of original text as answer]
    abcdef
    1
    abcde (or "bcdef")

    3) [For TLE]
    aaaaaa....(10^5 times)
    10
    a
    aa
    aaa
    ...
    aaaaa...(10 times)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thx for your analysing.
      That means, C was the problem that may include various bugs!

      I didn't notice (1) case because my solution is not affected by such a case :0

      By any chance , the cause of much WA is (1)?

      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
+0 rating change. heh!

Damn it, I missed problem C only because I took too long hunting bugs in my implementation for the first two problems. Even though I think I had the solution for C right away when I read it, but had too little time to implement it.

Art of implementation... what does it take to master it?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi i am new to codeforces .... And two of my solutions got rejected. one during system testing and one during pretest. Can i know anyhow which testcases were failed . plz reply

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Click submission ID on "My submissions list"
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can find it by clicking "my submissions" in contest menu, and clicking on submission number - after your code there'll be protocol of testing system, including tests, your program's answers and right answers.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I suspected 0(n*m*m ~ 10^7) might hamper.Instead I used Kmp for preprocessing then applied DP . It costed me time :(
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
By the way, I think that the icon of ir5 is cool!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How was C solved ?
Is it DP ?
Is DP necessary ?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No, dp isn't necessary if you want to solve this problem. For example I solved it using bin search.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you please explain a little, on how to use binary search here?
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        This is my idea: binary search on the length of interval.

        Let's fix the length of interval - x:
        - you check every interval of length x in an original string, and look for any, without boring strings inside;
         - you want to check if s[i,..,i+x-1] contains j-th boring string;
        - search b - the first beginning of occurence of boring string j in string s >= i
        - search e - the last ending of occurence of boring string j in string s < i+x
        - check if e-b+1 >= length of boring string j

        You can avoid checking each boring string for each fixed interval if you construct table right[] from the editorial, and look for minimum at checked interval.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I come from CHINA.
The server was too slow yesterday, I used 40 minutes to lock a problem  and it was too hard to view others' solutions ...
Everything was ok on previous contests ..
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I recived this mesage :I'm glad to invite you to take part in Codeforces Beta Round #72 (Div. 1 and Div. 2).At what DIv should i particate?
→ Reply