Educational Codeforces Round 39 [Rated for Div.2]
By BledDest, 7 years ago, In English

Hello Codeforces!

On March 06, 18:05 MSK Educational Codeforces Round 39 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This is a special Educational Round — Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship.

Social Discovery Ventures (SDV) creates, develops and funds Internet projects specialising in communication platforms that enable people across the world to get closer and expand their social networks.

The winners will be fully sponsored with their boot camp participation fees, accomodation, and meals for the India location!

This round also has a special regional prize — the company Phaze Ventures, a platform founded to transform the region by unlocking the untapped potential of our youth, startups and corporates, will be sponsoring the top 3 participants of this round from Oman (also among those who are eligible for ACM ICPC) — further sharing the importance of supporting talented programmers and sending them to these types of events throughout the world.

The round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them. Problem authors are awoo, vovuh and me.

Good luck to the participants! Hope you will enjoy the contest.

UPD: The tutorial has been published.

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

Comments Comments (172)
| Write comment?
»
7 years ago, # |
  Vote: I like it +97 Vote: I do not like it

It's not in the upcoming contests list?

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

Will it be on Codeforces? Because it's not on the contest list of Codeforces.

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

    Are you blind?

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

      Nope, but I think you need some memory refreshment as this contest was added in the list 1 day ago. My comment was before that time. Thank you.

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

Wow, what a pleasant surprise.

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

Acceptable start time for Chinese users:)

Vote for the contest and it will appear on the HOME Page?

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

Unfortunately, we cannot add the contest to the registration form right now, and when we will be able to do it, it might be too late for some participants.

We've decided to postpone the round. It will start on March 06, 18:05 MSK (exactly 24 hours after initially announced time).

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

Mandatory comment- "Hope the problem statements are as short as the announcement!".

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

Please rated for Div.1 and Div.2

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

Удачи

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

"Educational Round — Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship. Social Discovery Ventures (SDV) creates, develops and funds Internet projects specialising in communication platforms that enable people across the world to get closer and expand their social networks."

I have a question top winner are always top why you don't give a chance a pupil? they haven't anyy quality? Do a Randomly Winner.It will be help for him and her -_-

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

    Losers are losers

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

      But you are a pupil.. do you believe that you are a loser?

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

    This is the bug of competetive programming — only the world best participants can win prizes, it is dissapointing -_-. A lot of newbies quickly lose interest -_-. In any other sports participants are divided according to their age/gender/rating etc. and it is possible to win the prizes in any competition, if you are good for it.

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

      Isn't that with many things? -_- gotem

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

Clarification: everyone is eligible to win invitations or that is for div2 participants only?

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

there is no contest on contests page..

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

    Believe me, you are really blind!

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

      I know man. That's why I'm sometimes confusing your mom with my girlfriend.

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

I feel like educational rounds are kinda easier than regular CF rounds. Is that true?

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

    "Educational"
    Of course they are supposed to be easier

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

      Educational doesn't mean easy. It is better to upsolve.

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

The contest starts in 23 minutes, but I can not sign up...

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

when can I register?

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

Hope the problem statements are not as long as the announcement

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

I wish everyone hacks himself!

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

School 23:00 lights out,but the content begin in 23:05.so I urgently hope to 2 hours ahead of the game

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

“Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship.”

Are the finalists meant? Or any contestant who can participate in next ACM ICPC is eligible for the invitation?

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

Russian translation states that it is possible to hack your own solution, while english original doesn't. Is this true and how would doing it affect your score?

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

What if someone has already paid for this? Can we get a reimbursement?

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

rating predictor is not working!!

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

Extremely bad experience on problem C. 13 wa on problem C. Maybe I should go to sleep...

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

    same here :(. wasted more than 40 minutes!

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

How to solve D?

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

    we can use dp. dp states are dp[i][j] --> number of minimum hours he has to stay in the college if he skips 'j' lectures till the ith day!

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

    Calculate pre[i][j] = Minimum time spent in university on i'th day after using j skips on this day.
    Then calculate dp[i][j] = Minimum time spent in first i days after using j skips.
    Answer is dp[n][k].
    Transition is dp[i][j]=dp[i-1][z] + pre[i][j-z]. 0<= z<= j

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

      how to get pre[i][j] ?

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

        spend time in university = r — l + 1; we can calculate cost[i'th day][spend time in university] = skip time then pre[i][skip time] = spend time in university

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

        Observe that its useless to skip any lecture which is not at the beginning or the end.
        So, we should always skip some prefix and suffix of lectures.
        Let x be number of skipped prefix lectures and y be number of skipped suffix lectures.
        Try all x,y such that x+y<= k .
        pre[i][x+y]=min(pre[i][x+y], val)
        (pre[i][x+y] is initialised to inf)

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

          So calculating pre[i][j] is a n^3 operation?

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

          What's val in the above expression?

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

            The time spent after skipping first 'x' classes and last 'y' classes.
            It can be calculated in O(1) if you store all lecture times in a vector.
            Let size of vector be vs.
            val= 0 if x+y>=vs
            val= v[vs-y-1]-v[x]+1

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

    You may have an initial greedy idea to skip classes on endpoints of a day if skipping that class saves you the most number of hours. Unfortunately, this does not work because of the case

    2 8 2 10111101 11000011

    Greedy solution would skip first and last class on first day, but optimal solution is to skip first and second class on second day.

    We can make sets si for each day i that contain the hours that have classes. Then, for each day, we can calculate the minimum number of hours to attend class that day if we skip j classes on that day, and calculate this number for all j such that 0 ≤ j ≤ min(k, |si|).

    Once we have that, we do a simple dp, where our dp array has n rows and k + 1 columns. dpij will contain the minimum number of hours to attend class after day i while still having j days left to skip. Then, for the first row, we fill it up with the values we calculated in the last paragraph (i.e. dp[0][k] will be total number of hours of day 0, dp[0][k-1] will be minimum number of hours on day 0 if we skip 1 class, dp[0][k-2] will be minimum number of hours on day 0 if we skip 2 classes, etc.). For rows i > 0, we just test the possibility of skipping 0 ≤ j ≤ min(k, |si|) days from each point in the previous row.

    Then the answer will be the minimum number in our last row.

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

any idea what is test 16 for D?

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

    Totally random test with n = m = k = 500

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

      Shouldn't it be prefix/sufix calculation for each row then dp? I couldn't figure why my solutions fails for over an hour :D

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

        It should not, it can be arbitrary substring in a day

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

    i think the test 16 is something like when we skip on ith day some starting lectures and some lectures from last for an optimal solution. e.g 2 6 2 101101 000000 ans=2

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

      Very probable, as I made the same mistake of not including that case :c

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

      Yes exactly !! I forgot to consider that case when some prefix as well as suffix is skipped

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

    I also got WA on test 16, mostly it would be the case of having some prefix and some suffix skipped on a particular day, as I was considering either of them on one day not both.

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

D is harder than usual

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

Well, I solved E in about 15 minutes, and still wondering how could so many people solved D successfully.

Can anyone give me a hint? ;)

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

    http://mirror.codeforces.com/blog/entry/58155?#comment-418680

    Btw can you please explain your approach to E?

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

      First of all, here is my submission (36014589), in case my explanations are unclear. ;)

      With each test, provided that the number in the input is guaranteed to have an answer, we are sure that there is an answer with (|S| - 2) '9' digits (perhaps not the most optimal one, just get moving on).

      Now to find an answer with |S| length.

      First, we can use an array to store the number of appearances of each digit. Along with that, we will know the number of digits that has an odd appearance count.

      For example, with 28923845, we have count(2) = count(8) = 2 and count(3) = count(4) = count(5) = count(9) = 1.

      Since the answer is strictly lower than the given number, we can iterate the string from right to left. With each digit position, we can do the following:

      • If an answer has been found before, terminate all iterations.

      • If not, iterate all digits lower than the current one in a decreasing order. This time, all digits to the right of the digit we're iterating can be arbitrarily large without violating the "strictly-lower" criterion, therefore, an answer will be found if:

      1. There are enough digits to the right to compensate with the current number of digits with odd appearance count.

      2. If 1 is satisfied, the remaining digits to the right (after excluding the one used for compensation in step 1) must be an even number (to not creating another odd appearance count again).

      If both are satisfied, then an answer is found: which is all digits to the left of the iterating one (order remained the same), the value we're working on with that digit, and the digits to the right, which are modified according to the above criteria to keep the number "beautiful" and make it as large as possible.

      Taken the example of input 28923845 again.

      Starting at digit 5. As we're not working with this digit any more, decrease count(5) by 1, i.e. count(5) = 0 now.

      Since we still have 3 distinct digits with odd appearance count (3, 4 and 9), it is certain that we can't find an answer here. So we move on to digit 4.

      Again, we have to decrease count(4) by 1, i.e. count(4) = 0.

      Let's replace that digit with '3'. So, count(3) will be increased by 1, i.e. count(3) = 2.

      Now, only digit 9 has an odd appearance count, and we have exactly one digit to the right to spare, so we will set the value of that digit to '9', so all digits will have even appearance count. The answer is 28923839.

      P/s: What if the input is 44400000?

      Since no digit is lower than 0, we will surely start at the rightmost 4.

      Let's replace it by 3. Of course, we can replace a digit on the right by 3 to compensate, and there are 4 digits left un-handled. Since it is an even number of digits, we can safely replace all 4 of them with 9.

      The answer is constructed by the following: first two 4 digits on the leftmost (their states don't change at all), the digit 3 (replaced from the initial rightmost 4), and on the right, we have four 9s and one 3. We will write them from left to right in a descending order to make sure the number's value is largest possible.

      The answer for this input should be 44399993.

      Hope that this help you! ;)

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

        The answer for 2892384500 should be 2892384493, not so?

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

          Ouch, my bad :-P trying to clarify the case with exceeded digits but looked like I used a wrong case.

          Will fix it soon enough ;)

          UPD: I have fixed it! :D

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

        thanks a lot mate :)

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

        Many thanx to you!
        After reading your explanation  —  ez-AC :)

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

      Also, thanks for the hint for D ;)

      I got stuck with greedy for about 30 minutes, and after solving E, for some reasons my mind just froze and couldn't visualize a clear DP approach for it :-P

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

        Didn't solved it but seen the same type before usually solved by DP+Bit

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

C is very easier than usual and D is harder than usual...

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

Was D meant to be a solved in a Knapsack Problem way?

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

Damn Codeforces, it became too slow towards the end

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

I am not a grammer nazi, but this — If you can gen the string that will be obtained from the given string and will be contain english alphabet as a subsequence, print it.

UPD: It's fixed.

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

    Hoyl, why did nobody tell us this during the contest!? Sorry, it should be fixed now, statement will get updated in a couple of minutes.

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

How to solve C if we are asked to find the minimum number of operations (for any string s and t)

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

    DP[i][j] indicates the minimum way to solve the suffix ending at index i, with j as the letter we are currently trying to assign (starts at 0, goes to 25), S is the input string

    DP[i][j] = Min(S[i]-j + DP[i+1][j+1], DP[i+1][j]) — if S[i] <= j

    DP[i][j] = DP[i+1][j] ------------------------------------ if S[i] > j

    O(N*Alphabet)

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

      I think cases should be swapped, but the idea is same. Thank you

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

        Oh, right, thanks I'll fix it.

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

is there anyone else who cannot see others solution to hack!!!??

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

    Same issue

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

    I'm investigating it. Thanks. Fixed!

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

      How come some are hacking and some of us are not able to see the solutions..

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

        Up until now, people are only hacking their own solutions (the only solutions they can see right now).

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

How to solve problem E?

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

It's sad that my F couldn't get accepted because I didn't initialize 2fib0 and 2fib1 :(

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

So I ended up writing a dp solution for problem C which finds the minimal number of moves. And after the contest I noticed in the problem statement "Your target is to make some number of moves (not necessary minimal)..." :|

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

Implementation issues in D :( Good problem, though, finally a DP problem I was close to solving.

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

seems most of them are hacking them self!lol XDXDXD

only a few who hacked others!! haha

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

    Still, i am not able to see any other solution to problems. Ha Ha Ha

    Hack to other solution how possible without a see code.

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

    What is the test hack for problem C? I understand now.You are allowed to do multiple replacements for the same position of the string.

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

For the last question. maintaining prefix LIS and suffix LIS in same segtree and function as sum of both.(we subtract i from each a[i] initially and coordinate compress the array)
Can we do something like doing rollbacks on a segment tree in one direction and normal lazy updates in another direction. Does this work?

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

    I'm not sure whether we can do it using only one segment tree, but model solution uses two segment trees with almost the same approach.

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

    I have used one segment tree. There was no need of rollbacks, lazy updates, dynamic segment tree whatsoever. Only range query and point updates.
    Solution

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

How decreasing memory to solve D.

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

http://mirror.codeforces.com/contest/946/submission/36016554 can anyone provide a test for which this fails?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I had like a minute left and read problem G and BS'd an answer that was basically copy-paste from LIS template.

Threw it together in <30 seconds and submitted without compiling, WA on test 20 lol 36021949

EDIT: I realize the error and I'm surprised it made it as far as test 20.

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

In Berland students study in the university 500 days a week

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

How did http://mirror.codeforces.com/profile/assbb solve D and E but not the first 3? Seems a bit curious to me.

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

How this output is ok for problem C?

UPD: Fixed and this solution got hacked.

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

Why do so many people have weird barely readable aliases in their solutions, even for simple problems? Like this, for example.

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

Did someone solve E using Binary Search by fixing the length of the prefix then generate the appropriate suffix?

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

I've just been hacked on problem A, Actually I discovered that I understood it wrong ... but my solution passed during the contest. I don't think that you should put so weak tests like those so solution for another problem pass!!!

Hacking is for some tricky case or clever case that makes the solution wrong but not for making absolutely wrong solutions pass during the contest and then hack them after the contest. I really think you should rethink about that.

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

    The tests are not final. All the solutions will be re-tested on successful hacks after the hacking finishes. One of the points of competitive programming is that you should test your solutions better yourself.

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

      I said I understood the problem wrong ... is it logical for a solution of a problem pass another one!! That's my point, I'm not saying that they should put all the tests, but totally wrong solutions shouldn't pass!!

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

        Yes, actually I too wanted to raise the same issue, the testcases should not be so weak that it passes absolutely wrong solution, like at least it should cover all the basic cases.

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

Test: #1, time: 15 ms., memory: 1908 KB, exit code: 0, checker exit code: 0, verdict: OK

Input

aacceeggiikkmmooqqssuuwwyy

Output

aacceeggiikkmmooqqssuuwwyy

Answer

abcdefghijklmnopqrstuvwxyz

Checker Log

ok Ok

why checker log is ok ok? for problem A this submission

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

how to approach B. My solution gives wrong answer for large test cases.

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

    There is an "else if" missing in Line 15 in your code, without this "else if" the while loop breaks if the condition on Line 15 is not satisfied, however, your code won't pass even if you fixed this line because of the input constraints (10^18) and will give you TLE.

    The right approach is to subtract the quotient of the division of a by 2*b from a and subtract the quotient of b by 2*a from b while you can instead of subtraction.

    My AC Submission : Link

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

What is the solution for F?

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

    I did not solve it incontest and nor have I submitted it later, but pretty sure this is the solution (Confirmed by comparing it with accepted codes).

    Basically notice that when you make the ith fibonacci string you already have a concatentation of F(1)...F(i-1) present so its F(i)...F(i-1)F(i-2)F(i-1)

    An important intuition is that the number of occurences of the string s in F(1)...F(i) can be broken as number of occurences of some prefix of s in F(1)...F(i-1) and number of occurences of the remaining part of s in F(i). [We multiply these].

    To do this, we maintain 2 types of DP. till[i][l][r] stores the number of ways to get s[l...r] as a subsequence till the ith fibonacci string. curr[i][l][r] stores the number of ways to get s[l...r] as a subsequence in the ith fibonacci string. Notice that for each way in till[i-1][l][m] we can match it with a way in curr[i][m+1][r]. Thus we multiply these. We apply a similar logic for the transition of curr. In simple terms these events are independent so they're multiplied.

    Transition:
    1. curr[i][l][r]+=curr[i-2][l][m]*curr[i-1][m+1][r] for all m in [l, r)
    2. till[i][l][r]+=till[i-1][l][n]*curr[i][n+1][r] for all n in [l, r)

    The final answer is till[x-1][0][n-1] if fibonacci index = x and length = n (0 based indexing)

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

    Firstly, for every subsequence that is exactly the pattern, it will appear in 2^(positions free to the left) * 2^(positions free to the right).

    left[i][l][r] = sum of 2^(positions free to the left) for every subsequence that contains exactly characters [l, r[ in the pattern

    right[i][l][r] = sum of 2^(positions free to the right) for every subsequence that contains exactly characters [l, r[ in the pattern

    sub[i][l][r] = number of subsequences that contains exactly characters [l, r[ in the pattern

    sub[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * sub[i — 2][m][r]) + sub[i — 1][l][r] + sub[i — 2][l][r]

    left[i][l][r] = (sum l <= m <= r of left[i — 1][l][m] * sub[i — 2][m][r]) + 2^(size of f(i — 1)) * left[i — 2][l][r] + left[i — 1][l][r]

    right[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * right[i — 2][m][r]) + 2^(size of f(i — 2)) * right[i — 1][l][r] + right[i — 2][l][r]

    The subsequence either has parts in f(i — 1) and f(i — 2) (the summation part) or is completely inside f(i — 1) or f(i — 2) (the rest). But this isn't the complete answer because it has 2^(one side). So the answer comes either from f(i — 1) and f(i — 2) or from one of them so:

    ans[i] = ans[i — 1] * 2^(size of f(i — 2)) + ans[i — 2] * 2^(size of f(i — 1)) + (sum 0 < m < n of left[i — 1][0][m] * right[i — 2][m][n])

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

    This was 2012 ACM ICPC World Finals problem D. A thorough explanation can be found at:

    https://www.youtube.com/watch?v=dPFq4OLc-_Q

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

Did the image change just now?

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

In D, how could O(n*m²) solutions run in less than 100ms for some people?

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

    n = 500 with o(n ^ 3) just so fast. Btw, for O(n ^ 2), if the operations are not complicated, it works for n = 10000.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

On problem A ,I think the statement was very confusing. What was meant by "You may partition this sequence into two sequences"?? It seems the sequence should be partitioned into two contiguous part. Here 'partition' and 'sequence' have created confusion. The author should chose words carefully. I misunderstood it. Unfortunately the test cases was so weak that they passed for my wrong solution. Who always read explanation of test cases on A !!

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

    I wasted 10 minutes on this problem and got a penalty of 20 minutes because in my first submission i thought that I must maintain the order of the input and build a prefix sum array to know the best position of splitting :\

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

Problem A was written in a very bad way that I didn't know whether should I treat the input as a contiguous sequence or 2 subsequences after splitting and that cost me 30 penalty points.

Problem C test data was soooo weak and that resulted in hacking a lot of submissions including mine

I hope you consider these 2 issues in the next round, the weak test data and the bad problem formulation

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

    It says "in two sequences". I think this is pretty clear. They would say subsegment if they meant contiguous numbers

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

awoo
vovuh BledDest

SERIOUS BUG !!!!!!( DO READ THIS)

/*

Input

aacceeggiikkmmooqqssuuwwyy

Participant's output

abcdefghijklmnopqrstuvwxyy

Jury's answer

abcdefghijklmnopqrstuvwxyz

Checker comment

ok Ok

*/

How did my solution for C got accepted verdict? It's not giving correct answer even for the 1st testcase.

Here's the link to my accepted solution(during the contest, it got hacked now): http://mirror.codeforces.com/contest/946/submission/36018053

Another thing, now if you try to submit the same solution, it gives "wrong answer on test 1".

As you can see it clearly gave wrong answer for the test case but the verdict is "ok,ok" :(.` Can you please fix this? this is a real serious bug. Btw, it really screwed my contest. Now,I am literally inventing ways to screw a contest :(.

/*

Input

aacceeggiikkmmooqqssuuwwyy

Participant's output

abcdefghijklmnopqrstuvwxyy

Jury's answer

abcdefghijklmnopqrstuvwxyz

Checker comment

ok Ok

*/

Thanks!

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

    There was an issue in the checker, for some tests it returned OK instead of WA. It is really unfortunate but it is not a dramatic issue because you can always assume that there weren't such tests during a contest. Obviously, this argument can't be applied to wa1, though our estimated number of people affected is not that great. The participant can literally check his output for the sample case himself. We are still really sorry about it, the checker is fixed now and we will do our best in the following rounds to eliminate the possibility of similar mistakes.

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

Subsequence of the string is the string that is obtained by deleting characters at some positions

Did this note mean any thing to the solution in problem C ?

because it mean we can just print abcdefghijklmnopqrstuvwxyz or im wrong ?

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

    For example, see this test case (note the z at the 2nd position)

    azbcdefghijklmnopqrstuvwxyz

    There is a subsequence valid if we delete the first z, but we didn't use any change operation so the correct output is:

    azbcdefghijklmnopqrstuvwxyz

    The output must contain the changes you made for the string to be ok, but deleting a character is not a "change".

    Hope this helps you!

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

      But he didnot say that i must made a change he just need the final subsequence

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

        Actually it says "You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence" and "If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it."

        It says to print the changed string that contains the alphabet as subsequence, it does not say to print the subsequence.

        I agree that it could not be 100% clear at first sight :p

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

Please put stronger pretests in futur contests, We really don't want this awesome website to turn to Hackforces instead of Codeforces, this is really bad I mean I understand that this whole pretests thing is necessary due to huge number of participants but really try to make sure you put some strong pretests (sometimes a completely wrong solution can pass pretests... ) . In addition to that the hacks idea is really good but I think the hacks should not be very easy like they are now ( some people don't even read the code they just try limit input data and see if they get lucky hacking the solution )

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

After doing 108 successful hacks and then later know that it doesn't give you points in educational rounds..

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

    its doesnot give you point but if your rank is 300 and you hacked user with rank 299 you will be 299 so its good to hack

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

    I was thinking to send a message to inform you but I said maybe he do it for a purpose.

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

When should rankings for div 2 update?

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

How is penalty calculated in educational rounds?

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

    Sum of 1)Time taken for all questions from start of question to accepted solution 2)20*no. of wrong submission

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

      Oh thanks for that. 20 seems quite high tho, considering around 1000 people solve 3 in 30 mins.

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

        Yes, in my opinion in should be lowered, as it is blown out of proportion against time penalty in educational rounds.

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

Why during system test of ACM-style contest pending runs are shown with -x instead of ?x? And API also says that result is final, but some submits are pending

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

Why the rating has not changed so far ?

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

BledDest

This is with regard to question C 946C - String Transformation. I have solved the question C but after system testing i got TLE.

But to my surprise when i resubmitted the same code after the system testing it got accepted . I am posting the links of 2 submissions here one with TLE and other with Accepted.

one with TLE — 36008794

one with Accepted — 36055044

and both solutions are same , you can check yourself by comparing diff(they have no diff)

Can you please see this issue?

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

When rating update will happen for div 2 :(

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

    So u were waiting :D You became specialist. Congrats (Y). I became green :D

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

My cf predictor shows my rating will increase by 125(it has not been wrong yet) . This result was shown to me just after finishing the system testings. As cf rating changes has not been updated yet, may i assume that cf will use a new formula this time to calculate new ratings? Some of the results by cf predictors looked unfair to me. So new formula won't be bad if authority approves.

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

When rating update will happen for div 2 ^_^

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

I think that the reason that the rating is not updated yet is because of the error in the previous test of problem C.

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

nvm

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

Who won the special prizes?

→ Reply