By BledDest, 7 months 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 PikMike, 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  

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

It's not in the upcoming contests list?

»
7 months 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.

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

    Are you blind?

    • »
      »
      »
      7 months 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.

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

Wow, what a pleasant surprise.

»
7 months 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?

»
7 months 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).

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

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

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

Please rated for Div.1 and Div.2

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

Удачи

»
7 months 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 -_-

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

    Losers are losers

    • »
      »
      »
      7 months 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?

  • »
    »
    7 months 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.

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

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

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

From where do we register for the contest??

»
7 months 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?

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

there is no contest on contests page..

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

    Believe me, you are really blind!

    • »
      »
      »
      7 months 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.

»
7 months 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?

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

    "Educational"
    Of course they are supposed to be easier

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

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

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

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

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

when can I register?

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

Hope the problem statements are not as long as the announcement

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

I wish everyone hacks himself!

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

please hit the like button of my comment

»
7 months 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

»
7 months 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?

»
7 months 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?

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

    It is "Educational" you don't take any score for hacks!

»
7 months 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?

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

rating predictor is not working!!

»
7 months 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...

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

    same here :(. wasted more than 40 minutes!

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

How to solve D?

  • »
    »
    7 months 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!

  • »
    »
    7 months 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

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

      how to get pre[i][j] ?

      • »
        »
        »
        »
        7 months 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

      • »
        »
        »
        »
        7 months 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)

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

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

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

          What's val in the above expression?

          • »
            »
            »
            »
            »
            »
            7 months 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

  • »
    »
    7 months 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.

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

any idea what is test 16 for D?

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

    Totally random test with n = m = k = 500

    • »
      »
      »
      7 months 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

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

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

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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

    • »
      »
      »
      7 months 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

  • »
    »
    7 months 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.

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

D is harder than usual

»
7 months 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? ;)

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

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

    Btw can you please explain your approach to E?

    • »
      »
      »
      7 months 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! ;)

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

        The answer for 2892384500 should be 2892384493, not so?

        • »
          »
          »
          »
          »
          7 months 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

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

        thanks a lot mate :)

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

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

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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

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

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

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

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

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

Damn Codeforces, it became too slow towards the end

»
7 months 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.

  • »
    »
    7 months 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.

»
7 months 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)

  • »
    »
    7 months 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)

    • »
      »
      »
      7 months 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

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

        Oh, right, thanks I'll fix it.

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

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

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

    Same issue

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

      same issue, I am also not able to see solutions to hack!!

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

    I'm investigating it. Thanks. Fixed!

    • »
      »
      »
      7 months 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..

      • »
        »
        »
        »
        7 months 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).

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

          yup got it, in fact the problem has been fixed now

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

How to solve problem E?

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

How can i hack others solution ?

»
7 months 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 :(

»
7 months 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)..." :|

»
7 months 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.

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

Is it possible to view other's solution ?

»
7 months 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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

»
7 months 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?

  • »
    »
    7 months 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.

  • »
    »
    7 months 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

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

How decreasing memory to solve D.

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

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

»
7 months 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.

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

In Berland students study in the university 500 days a week

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

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

»
7 months 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.

»
7 months 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.

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

    So that hackers stay away?

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

      Extract from CF Contest Rules

      "It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work."

»
7 months 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?

»
7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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!!

      • »
        »
        »
        »
        7 months 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.

»
7 months 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

»
7 months 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.

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

    brute force. take mod while a>=2*b and b>=2*a

  • »
    »
    7 months 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

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

What is the solution for F?

  • »
    »
    7 months 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)

  • »
    »
    7 months 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])

  • »
    »
    7 months 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

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

Did the image change just now?

»
7 months 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?

  • »
    »
    7 months 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.

»
7 months 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 !!

  • »
    »
    7 months 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 :\

»
7 months 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

  • »
    »
    7 months 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

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

PikMike
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://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!

  • »
    »
    7 months 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.

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

      Hi Vovuh

      Shouldn't this round be made unrated for all the users who experienced the same problem?

      Thanks!

»
7 months 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 ?

  • »
    »
    7 months 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!

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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

»
7 months 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 )

»
7 months 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..

  • »
    »
    7 months 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

  • »
    »
    7 months 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.

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

When should rankings for div 2 update?

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

How is penalty calculated in educational rounds?

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months 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.

»
7 months 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

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

Why the rating has not changed so far ?

»
7 months 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?

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

These are my hacking testcases.. I did 108 hacks with them for B:

3 1000000000000000000

1000000000000000000 49999999999999999

49999999999999999 1

1 1000000000000000000

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

When rating update will happen for div 2 :(

»
7 months 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.

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

When rating update will happen for div 2 ^_^

»
7 months 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.

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

rating has just updated now wow ;)

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

nvm

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

Who won the special prizes?