HellKitsune's blog

By HellKitsune, history, 7 months ago, translation, In English,

Hi!

After a long break, on Jan 25, 17:35 MSK will be held Educational Codeforces Round 17.

You will be given 6 tasks and 2 hours to solve them. The problemset, in my opinion, turned out to be well balanced and should be interesting for both novices and experienced participants. Task F may end up beneficial for many reds :)

The ideas for problems are by MikeMirzayanov and me. Thanks to fcspartakm for helping in preparation of this round.

I hope you will enjoy the problems and good luck!

UPD: The contest is over. Probably a little bit on the hard side for the beginners? Sorry! Editorial will be in the form of hints and will appear shortly.

UPD2: Editorial

UPD3: Challenge phase is over! Congratulations to winners:

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

Also, top hackers!

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

If you want to share your ideas about tasks for next Educational Rounds, you can use the new problem proposal form. Please, use prefix "er-" in the name of the task so that we know that it is for Educational Rounds.

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we hope for rated educational rounds some day?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    The the "educational" name may change!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How many problems will there be?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Rated?

»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

My prayers are listened . Thanks MikeMirzayanov.

I was really missing Educational CF Rounds .

Thanks to fcspartakm , HellKitsune for their effort .

»
7 months ago, # |
  Vote: I like it -27 Vote: I do not like it

How many problems? 6 or 7 o5 5

»
7 months ago, # |
  Vote: I like it -27 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -24 Vote: I do not like it
      • I know it... :) thís is my new account...

      • Last my account is very bad.. so... I hope with this contest i'll change it...

      • And good luck to you. :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -45 Vote: I do not like it

Since Nobody Has Asked, Is It Rated?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Ignore

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does this contest increase or decrease rating points?

»
7 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Don't ask such questions during the contest!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hmm.., I didn't know 10 ** 7.5 is still not TLE.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        10^8 is about the safest number to assume that you dont get TLE

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think 2h isn't enough :(

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

nice problems, waiting for editorial :)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I am refreshing every 5 seconds.I reallllly want to know the solutions of D and E

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will we be allowed to submit after the contest.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case 2 in problem B ?

SO many WAs

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer is out of the range of int in C++

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had made a really stupid mistake.

      instead of sum+=x[i], I had coded sum+x[i] instead :/

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hah, I got WA cuz I forgot to user long long instead of int

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can we discuss solutions in hacking phase?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually it doesnt have anything in common.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried BS.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same.Binary-search rocks

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no, i did with greedy + binary search code here

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Yeah. BS means binary search :)

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            someone describe the solution pls!!

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
              Rev. 5   Vote: I like it +3 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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]

  • »
    »
    7 months ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same for me. Can't solve more than 2 problems per contest :(

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      How yow improved your coding skill? Truely inspired after seeing your graph. :)

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just practice.research what you don't know.If you do this you should improve pretty fast.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to see my standing in the contest, please help

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got it but it wasnt being shown in the main page :/

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

What's the hacking test for C?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I got hacked on a test like this:

    aa
    a

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    a aba

    Sometimes works I guess

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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}

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you -Morass-

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

»
7 months ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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 consequtive characters

abcfg we have to remove 6 consequtive characters .

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

Can anyone explain ?

UPDATE : I UNDERSTAND THEY said Exactly one consequtive string not more than one .

»
7 months ago, # |
  Vote: I like it +36 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it
  • 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
»
7 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Compare function must return false on equal elements. I challenged so many solutions with this error...

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does it matter? After all they are equal

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        This is STL requirement. If your comparator doesn't satisfy it, STL functions like sort may crash.