Блог пользователя HellKitsune

Автор HellKitsune, история, 8 лет назад, По-русски

Привет!

После долгого перерыва, 25 января в 17:35 MSK, состоится учебный раунд Educational Codeforces Round 17.

Вам будет предложено 6 задач на 2 часа. Проблемсет, на мой взгляд, получился достаточно сбалансированным, и должен заинтересовать как новичков, так и опытных участников. Задача F может оказаться полезной многим красным :)

Идеи задач придуманы MikeMirzayanov и мной. Спасибо fcspartakm за помощь в подготовке раунда.

Надеюсь, вам понравится, и желаю удачи!

UPD: Контест завершен. Наверное, немного сложновато для начинающих вышло :) Разбор будет через некоторое время в виде подсказок под спойлерами.

UPD2: Разбор

UPD3: Фаза открытых взломов завершена. Поздравляю победителей:

  1. eddy1021
  2. W4yneb0t
  3. kmjp
  4. LHiC
  5. Deemo

А также лучшие хакеры!

  1. halyavin +249 : -35
  2. step_by_step +82 : -11
  3. -Morass- +51 : -141
  4. MishaPrigara +50 : -5
  5. uwi +46 : -9

Если у Вас есть идея для задачи на будущие учебные раунды, можно воспользоваться новой формой предложения задач. Пожалуйста, используйте префикс "er-" в имени задачи, чтобы было понятно, что задача предлагается именно на учебный раунд.

  • Проголосовать: нравится
  • +279
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we hope for rated educational rounds some day?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    The the "educational" name may change!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

      well, mike mentioned in the blog on the introduction of educational rounds that educational rounds might be rated in the future. I did not ask for anything unreasonable. Give me my upvotes :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        Well, if it is rated it would be less "educational", and we can get under rating pressure. So if the round is unrated, you could care less about your rating and learn care-free.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Let's make educational rounds rated like atcoder. In atcoder beginner contests are rated for beginners. More beginners will participate to rounds.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How many problems will there be?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I think 6 or more problems will be , (He said :: Task F may end up beneficial for many reds )

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Like they were usually held, there will be 6 tasks for 2 hours. I'll update the blog with this :)

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

After a long time Educational Round is there, Hoping for good and interesting questions. All the best !!

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

if we want to suggest some problem to the educational round, who we should contact???

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Rated?

»
8 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Rated?

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

My prayers are listened . Thanks MikeMirzayanov.

I was really missing Educational CF Rounds .

Thanks to fcspartakm , HellKitsune for their effort .

»
8 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

How many problems? 6 or 7 o5 5

»
8 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

I hope that my rating will change in this education contest..... :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    It is unrated contest. You can improve your skills and become beneficial with some good problems.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why there is not many users with contributed task ? Is it your decision, or nobody wants to give problems ?

»
8 лет назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Since Nobody Has Asked, Is It Rated?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't have to feed Bessie today (I'm a gaucho, you know), so I can take part in this round. Let's hope some nice problems!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Looking forward to see the problem proposal system adapted to educational rounds :)

»
8 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Many people want Educational contests to be ratede. May be we should vote for this?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    I think that rating Educational Rounds would be like giving points to soccer teams for what they do during practice sessions.

    I believe the main purpose of Educational Rounds is to learn important techniques and algorithms and the people that take part in them are either like "I'll participate and see if I learn anything new" or like "I'll take part until I get bored". Rating such an irregular contest would be a mess.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope the problems can interesting

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ignore

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

does this contest increase or decrease rating points?

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

how does people generating prime numbers for problem A?

I was thinking about sieve-ing it, but 10 ** 9 seems too big.

tho, in the end, ruby's 'prime' library is fucking cheat.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    Don't ask such questions during the contest!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      sorry, I thought it's fine since this is unrated. I'll note it.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        if i is divisor of n, then n/i is divisor of n, so we are only enumeration to sqrt(n), we can solve the problem

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't need to generate prime numbers for A. I just generated the numbers that divides N that are less than or equal to sqrt(N). Every other divisor can be generated from these numbers.

    If query K is less than the size of the divisor array just print the divisor. If K>divisors.size() and K<=2*divisors.size() than you can generate the divisor by dividing N to K-divisors.size()th divisor from the end in the array. If K>2*divisors.size() print -1.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

My first contest on this site it was fun simple straight to the point

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think 2h isn't enough :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://codeforces.me/contest/762/submission/24127457

isn't this O(n log^2 n) ?? why would it TLE ?????

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

nice problems, waiting for editorial :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will we be allowed to submit after the contest.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is test case 2 in problem B ?

SO many WAs

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Since now is open hacking period,is the edtorial going to be posted after the period ends?

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Can we discuss solutions in hacking phase?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone describe solution for C, i'm guessing it's related to LCS.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No. LCS will be N^2 which is too much for the given time limit

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    actually it doesnt have anything in common.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried BS.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Same.Binary-search rocks

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        no, i did with greedy + binary search code here

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Yeah. BS means binary search :)

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            someone describe the solution pls!!

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              i would,but i don't know if i am allowed until hacking period ends

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                Actually, the hacking phase is just there to include all test cases for the problem, and since it's also not rated, it doesn't affect that we discuss solutions. In fact, discussing will probably be better for finding all corner cases, if more people understand the basic solution.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

              Binary search on the contiguous segment's length.

              First, precompute this

              precompute

              The above code assigns forward[i] to be the smallest index of a such that b[0:i] forms a subsequence in a. Similarly, backward[i] is the largest index of a such that b[i:b.length()-1] forms a subsequence in a.

              Then we BS on the length of the segment to delete.

              For each starting position of the segment to be deleted, check if forward[start-1] < backward[start+segment_length] . If for any starting position, this above relation becomes true, then we can also try a smaller segment size, else, we must try a bigger segment size.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                i did it so:

                we index i from 0 to length of b

                we say that from 1 to i we want to have the substring in the final result.We bs the position j,with the condition that if we erase the substring i....j then we get a valid result.and the condition in BS would be forward[i]<backward[mid]

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

    My solution is O(n). Let dp[0][i] be the length of the longest prefix of b that is a subsequence of a[1: i], and dp[1][i] be the length of the longest suffix of b that is a subsequence of a[i: len_a].

    We can easily see that if a[i] equals to b[dp[0][i - 1] + 1] then dp[0][i] = dp[0][i - 1] + 1, otherwise dp[0][i] = dp[0][i - 1]. Do the similar thing for dp[1][i].

    We will find the position that dp[0][best] + dp[1][best + 1] is maximum, then print the first dp[0][best] characters and last dp[1][best + 1] characters of b.

    Source code: 24121085

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let Pi be the set of indices of A which form the subsequence for B[1..i]. Similarly, let Sj be the set of indices of A which form the subsequence for B[j..m], where m is the length of B.

    That is, store the indices of A for the longest prefix and suffix of B that is a subsequence in A.

    Iterate over indices of A and try to maximize the length of Pi + Sj, which is equivalent to minimizing the length of the segment erased from B which is [(i + 1)..(j - 1)].

    Submitted Code

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, I'm getting worse every round. I knew how to solve A task, but after runtime error I started to solve problem E... Solved A 18 minutes before the end. :( Why am I so bad?

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Guys, how do you solve these problems? I am trying hardly to do my best, but no significant result in almost a year time. Even these "simple" educational tasks. What could you suggest? Thanks.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    on codeforces educational doesn't mean simple.and don't worry,after just 1 year i didn't know much.You have to patient and you will get better

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    These problems aren't simple,just the ideas maybe are well-known and i think this helps a lot to build your set of ideas when you solve a problem.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello, I have a short question — someone hacked my solution, I fixed something. Is it somehow possible to check, whether my new solution works fine on 'hacking' test or I would need to wait until the end of hacking phase?

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

What's the hacking test for C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I got hacked on a test like this:

    aa
    a

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    a aba

    Sometimes works I guess

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Good day to you,

    I got many of hacks with A=10^5*'c' B=9*10^4*'c'

    I.e., string full of "same" characters and one shorter string {two short strings might work too}

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For problem C . I have a input

    axbxcxdxexfxg

    abcwwdewwfg

    why ans is abcfg ? shouldn't it be abcdefg ?

    because :

    abcdefg we have to remove 4 characters

    abcfg we have to remove 6 characters .

    In this problem they said removing minimum characters . So It should be abcdefg . why abcfg ?

    Can anyone explain ?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      You have to remove the minimum possible number of consecutive ( standing one after another ) characters from string b

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand C problem. please anyone explain it..

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Good day to you,

    well you have two strings, and you have to remove EXACTLY ONE consecutive passage [i.e. "K" consecutive characters] form second one, so it becomes sub-sequence of first string {i.e., all characters from rest of second string appear in first string [not necessarily consecutive] in same order}

    HINT: As you can see [from statement], you remove the part from middle, suffix or prefix so (if anything) only what can remain is: "suffix", "prefix", "suffix+prefix" or "whole string"

    Good Luck & Have nice day!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      thanks -Morass- You made my day.....

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Thank you -Morass-

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please tell me how to implement after suffix+prefix string is a subsequnce of string A . ? Suppose :

      axbxcxdxexfxg

      abcwwdewwfg

      i got abcfg , now how i check abcfg is a subsequence of String A ? There has a bruteforce way , check 'a' is where in string A , if found break , then search for the next character 'b' , in string A after that index where 'a' was found . I need efficient way . Is there any ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Good day to you,

        firstly, (to second comment), as I said, it must be EXACTLY ONE BLOCK OF CONSECUTIVE CHARACTERS so "abcdefg" is not possible (you removed two consecutive blocks)

        secondly, how to do it efficiently? Well you can do iteration through array (from back to front), precalculating array of "next" (code — if you "un-think" the macros), so that it will tell you (on every position) next occurrence of ANY character on O(1). The precalculation costs O(N*ALPHABET).

        The same can be done for "back".

        Hope it is strait-forward now {you can use two pointers or similar to get the answer then}.

        Good Luck & Have Nice Day!

»
8 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

I think there is a problem with the judge. Lots of "Judgement failed" in problem B

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
  • Sorry about my English... I'm from VietNam
  • Hi every one — Problem B, all submissions in the worlds.. only 3 Accepted... very very magic... and I don't understand why?... I think ... look at ourselves
»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Auto comment: topic has been updated by HellKitsune (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody tell me what is wrong in my code. Why is it giving runtime error? http://codeforces.me/contest/762/submission/24149549

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

хакер хуже глиномеса