Educational Codeforces Round 61 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

Hello Codeforces!

On Mar/05/2019 18:05 (Moscow time) Educational Codeforces Round 61 (Rated for Div. 2) will start.

This round is organised in collaboration with Hello Muscat Programming Bootcamp and supported by Sberbank, General Partner of the boot camp and one of the largest banking leaders of Eastern Europe, providing thousands of jobs and innovation in the financial industry.

As the Hello Muscat Programming Bootcamp’s General Partner, Sberbank made it possible for students from some of the world’s top universities to attend the bootcamp, by sponsoring their participation. This includes students from Saint-Petersburg State University, Moscow Institute of Physics and Technology (MIPT), Penza State University, National Research Mordovia State University; MRSU, ITMO, Higher School of Economics / Moscow, Volgograd State Technical University, Lobachevsky State University of Nizhni Novgorod, Moscow Aviation Institute, Tyumen industrial University, University of Haifa, Northern (Arctic) Federal University, Saratov State University, Ural Federal University.

Hello Muscat Bootcamp will take place from 9th to 15th of March, and 120 students from 24 universities, including MIPT, Saint Petersburg State University and University of Tokyo will compete and practice side-by-side, smoothing the road towards the April World Finals in Porto.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours 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.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 vintage_Vlad_Makeev 7 321
2 kmjp 7 380
3 Kilani 7 452
4 neal 7 721
5 I_love_Tanya_Romanova 6 204

Congratulations to the best hackers:

Rank Competitor Hack Count
1 algmyr 121
2 MarcosK 119:-6
3 Mohammad.H915 60:-1
4 Bakry 50
5 AhmedMaherAli 45:-1
1837 successful hacks and 1117 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A vintage_Vlad_Makeev 0:01
B 1021869 0:03
C vintage_Vlad_Makeev 0:08
D vintage_Vlad_Makeev 0:24
E TripleM5da 0:20
F _Ash__ 0:06
G road_to_9k_mmr 0:25

UPD: Editorial is out

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

Comments Comments (163)
| Write comment?
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Wish interesting tasks!

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

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

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

omfg i cant waitr

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

i guess most of cf users are poor

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

Hope test cases will be stronger than previous. Good luck Happy coding

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

I hope the contest is not declared unrated this time and no technical issues or unethical behaviour from the community members.

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

I want high rating.

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

Wish you happy coding =)

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

I want easy tasks so I can get high rating!

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

    Dude, with easy tasks everyone will solve them, so it become a speed contest, which is not "educational" and doesn't make sense, cause we are here to learn and have new ideas ...

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

    I want hard tasks so others can get low rating!

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

      thanks you for getting low ratings everybody!

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

    if you want high rating you must have good rank the rating depends on rank not how many tasks you solve :)

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

      if you solve more tasks you have a higher rank

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

I always hate delays But could you please start contest later? We have just left school (Also i know that i am not an important person but i think for most Iranian person this time is really bad)

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

Deleted

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

Please suggest some problems like C today for practice

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

Why my code got Runtime error on test 1 on problem C, while same code works fine locally and ideone

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

How to solve F?

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

    https://codeforces.me/contest/1132/submission/50837409

    dp1[l][r][a] = Minimum to delete all in range l..r except for character a dp2[l][r] = Minimum to delete all in range l..r

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

      Can you please explain time complexity of your code and how does it pass , as to me it seems that the time complexity is O(26*n^3).

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

        It is O(26*n^3), and the constant is low enough.

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

    You can straight up solve for DP(i,j) = answer for substring s[i:j]. It takes O(n3) time and O(n2) memory. See my solution here.

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

How to not get MLE on G?

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

Was D binary search + simulation?

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

    How to do the simulation?

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

      Greedily charge the laptop that will run out of power the earliest.

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

    Yup. However, you should probably do simulation in O(n + k) to avoid TL.

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

      How to do the simulation? :)

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

        I think storing a[i]/b[i](how many minutes can laptop run without charging) and taking minimum every minute will work.

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

        What Jakube said. I did it by maintaining such an array that i-th its cell contained all the indices of laptops to run out of power on minute i.

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

        Use priority_queue with the eariest (t[i] = a[i]/b[i]+1) on top. Each time you will take the top and add to its a[i] by x then push it in priority_queue. Note that if you take a laptop with t[i] > k then you can stop it immediately. Sorry for my bad English

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

          I tried to implement your solution to problem D but i was surprised this morning that i was hacked, what's wrong?

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

            His approach might got TLE if implemented poorly.

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

              So what's the catch, how to avoid TLE?

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

                Refer to Pik's comment right above. Instead of p.queue, use arrays.

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

      Very tight time limit on problem D. You still even get TL with O((n + k log n) * log(2e12)) solution.

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

How to approach problem E? It seemed more like math/greedy than anything else, but I couldn't come close to a solution.

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

    Well, model solution does something like that:

    Let L be the least common multiple of all numbers from 1 to 8 (L = 840). Then, if in the optimal answer we need to use c items of weight i, we may write c in the following form: , where . Then we may merge items of weight i into p items of weight L, if we fix q.

    This allows us to use the following dynamic programming solution: dp[x][y] — the maximum number of items of weight L we may obtain, if we tried x first types of items, and got total weight of y while using less than items of each type. Note that the second dimension should have size 8L, since it is the maximum possible sum we may obtain in this case.

    But it seems that some participants used different heuristics and random. We aren't actually sure if such solutions should fail.

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

    You could solve it my noticing that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16.

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

Just the problem was searching range. I was in a fear as hell. Codeforces should check their algorithm time complexity, not just tight range.

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

Is O(n * logn * log(2e12)) expected soln of D??
How to solve F??

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

    I think so, but with bad optimization you'get TLE on 22 or 27th test case.

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

    was intended. It was more like "I'd like you to do linear simulation but won't mind if you sqeeze extra log on top of it".

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

    https://codeforces.me/contest/1132/submission/50849148

    The check function is linear time.

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

    Let dp[i][j] indicate minimum number of ways to delete the substring from i to j. Now there are 2 possibilities either character at i and character at j are equal or not.

    If str(i) == str(j) then dp(i)(j) = 1 + dp(i + 1)(j — 1) Else dp(i)(j) = min( 1 + dp( i + 1)(j) , 1 + dp(i)(j — 1))

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

I think D deserved just a little higher time limit. My O(log(1e12)*(k*log(n)) soulution didn't pass, I tried to optimize best as I could.

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

    I passed with the same complexity, but I had to use priority_queue, got 3 TLs because of multiset.

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

      Oh.. I didn't know that priority_queue is faster.. Thanks

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

      std::multiset is god-awfully slow. It's also sometimes possible to replace the implementation with a std::set<pair<T, int>> instead.

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

        Well, I did with set<pair<long long,int>> it didn't help.

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

    I hate such problems. Why Codeforces push us hard as hell in terms of time limit? I think correct time complexity is enough.

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

      See the other comments, the intention was that the simulation is run in linear, not O(n log n), although given the limits, just 2 * 10^5 I too thought linear time isn't needed.

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

        Then it's my fault :( I couldn't get any linear simulation ideas

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

        It was 2e5 but it was also 1e12 which significantly bumped the binary search constant.

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

          Well it is just a constant 2x, and overhead for multiset is probably 3-4x or even more, so I usually disregard whether the binary search is log 10^6 or log 10^12 or log 10^18. But that is my fault :)

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

    Ye, it probably did. Should've either set it the way you won't think of or make the constraints a bit lower.

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

      When you made constrains higher at the begging it was "clear" to me that you raised because such solutions :D

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

        I was more afraid of some linear simulations not passing. I believe, you'll have to set something like 10 seconds for any to pass, not only optimized ones.

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

    Instead of using set, you should just put the element that you are sorting your set by, as an index in a vector because once you delete an element form the set you will never insert a smaller one back, so you can somehow call the set monotonous. Here is my solution with complexity O(log(1e13)*(N+K))

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

why n(log^2(n)) gives TLE in D ?

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

What was testcase #5 in C?

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

    Check : 4 4 1 1 2 2 3 3 4 4

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

So shitty D

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

Problem C ?? Approach to solve problem like this ??

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

    Here is possible to use partial sums approach. Also, you can use the event-based approach.

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

    Given an array of numbers, partial sums is a technique used to get in O(1) the sum of numbers in an interval [l, r]. It works by iterating from zero to the length of the array adding up for every position the sum of the previous position. So if your partial sums array is called sum you can get the sum between [l, r] by doing sum[r]-sum[l-1]. Precalculate the partial sums array will take you O(n), where n is the length of the array.

    In this case you can do the partial sums array such that sum[i] = k if there are k workers to paint the i-th fence. To make the partial sums without iterating from l to r every time, you can simply add 1 to sum[l] and -1 to sum[r-1] because you know in that positions someone will start painting and had finished painting respectively. Finally you make the sums, such that sum[i] += sum[i-1].

    Now you can make partial sums again but counting the number of fences to be painted by zero, one and two painters respectively, to easily know for each interval [l, r] how many fences will not get painted if the corresponding painters covering that interval are not hired.

    Note that this technique is useful for problems that does not have updates over the values of the array. If you find a problem where you can do partial sums and your algorithm does not pass in time because the update queries, try something like Fenwick Tree or Segment Tree.

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

Number of people who solved D are too misleading, I read it very late (It's my fault).

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

For problem D: Beginning of 4th second both laptop has [1,1] charge but there was still one minute to finish. How does the answer be 5?

I just missed this got wrong answer at 12 :(

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

    The charges at the beginning of the (k + 1)-th minute don't matter.

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

      But it was 4th second.

      1st second- 1st laptop

      2nd second — second laptop

      3rd second -1st laptop.

      4th second ??

      Am I missing something? -_-

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

        They have [1, 1] at the beginning of the 4-th second. That is ok, they are non-negative. It doesn't matter what they become at the beginning of the next second.

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

How to solve C if constraints were 10^5 ?

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

Easier B than A is now regular event. We should try solving B first from next contest.

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

Really nice C ..haven't seen such a C in a while

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

Can someone explain C a bit please? It seemed like a really neat problem, but sadly haven't seen anything similar before.

P.S. That problem A was so wrong for so many reasons...

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

    Hint: Use a difference array to count how many painters paint each block in O(n). Then do some O(n2) brute force(Try picking any two painters and leave them aside).

    More about the difference array

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

      Woah thanks so much!!! I actually thought of that type of array, but threw that idea aside thinking it was unnecessary... Thanks so muuch!

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

Why is this dp(problem F) wrong?

  • dp[i][j] is the answer for the substring s[i..j]

  • For every string s, let the last character I'll delete (in the optimal way to delete all of the string s) be C. Since that will be the last character, the answer will be 1 + the sum of independant answers for the substrings that you'll get once you delete every occurence of C in s. So I go through all possible characters from 'a' to 'z' and sum up the answer for every substring between two occurences of C in s, then add 1.

It's exactly like going backwards in the optimal process of deleting equal substrings.

I realise it's not the same dp as most solutions, but I believe the logic is correct..

Submission.

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

    Suppose the string is "aaqwertyaaytrewqaa". You want the last character deleted be a

    "aa"+ "qwerty" +"aa"+ "ytrewq" +"aa"

    If you do "qwerty" and "ytrewq" independently you spend 6+6=12 steps.

    If you do substring "qwertyaaytrewq" at once, you spend only 7 steps.

    That's why it's not always optimal to do them independently.

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

    I think in some circumstance that isnt the optimal way. Example: acbabca. Your solution will get 5 but 4 is the answer.

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

Yall got any idea why this 50850982 gets WA?

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

D passes with priority queue, exceeds limit with sets.Good question overall

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

When you know your accepted solution is wrong so you hack yourself

Edit: See Hack

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

Many tasks can be found on informatics.msk.ru

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

Can someone please explain this solution?

https://codeforces.me/contest/1132/submission/50833595 (Author: PrakharJain)

It's a simple and nice solution, but I fail to understand how it works.

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

    For a particular subarray [i, j], I'm just iterating through all possible positions k which would form the last position of the segment which would be deleted together. The character at k should be same as in i, of course. And, then in the transition we can stop considering one of the positions (either i or k as they are deleted together). So, both the transitions: ans = Math.min(ans, recurse(i, k — 1) + recurse(k + 1, j)); or, ans = Math.min(ans, recurse(i + 1, k) + recurse(k + 1, j)); should work.

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

      But consider this case abaca in this case answer is 3 when you want answer for [1,5] you will take recurse(1,2)+recurse(4,5) and both have values 2 and 2 and their sum is 4 but we want 3 as our answer.

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

        Also, recurse(1, 5) = recurse(1, 4) = 3. So, it'll take this minimum value.

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

      Why does this 50854241 give TLE . I wrote a recursive solution and then memoized it. Can you please provide a test case other than sample test case so that I can verify my answer irrespective of TLE as the 4th test case has |s|=500.

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

        Your solution seem to me O(n^4) because of substring calls inside the iteration. Store the intermediate states using indexes and not the strings.

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

In problem A test case: 0 1 1 0 should print 1 because i can do just like that "() ()" I've been hacked because of that

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

    You have one pair of "()" and one pair of ")(". So whatever you choose first, it is not correct.

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

How to solve C for n, m = 106?

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

Can C be solved in linear time?

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

if i hack a solution after the contest in educational round do i get points or not ?! thx in advance :)

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

Please Help : Any way to remove TLE in F using map

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

How to solve G??

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

    first for each index i find the maximum index j such that j < i and aj is greater than or equal to ai,call this last[i]. this can be done in linear time using a stack.

    consider ans[i] as the answer if we start our sequence from position i.now make a maximum segment tree on ans values and iterate i from 1 to n there are two cases :

    1. i > k : in this case remove the value from position i — k and add 1 to positions in range [max(last[i] + 1,i — k + 1),i] , now the answer for query ending in position i is maximum value on our segment tree

    2. i <= k : in this case you just have to add 1 to positions in range [last[i] + 1,i]

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

omfg bad pretests.........

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

Has anyone solved C using DP?

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

Just as of now I realized how atrocious pretests of problem C were. My solution got like, 4 critical flaws right within.
And none of them got caught during contest time. I fixed one by one and got WA one by one at tests that are obviously not pretests.
Having a closer look, such tests are not really too complicated (yeah, I would blame myself as well for not testing properly and got hacked/WAs, but it's irrelevant here), making the issues going way worse.
Really wish Educational Rounds never got such incidents ever again.

P/s: For a brief overview, I calculated the number of cells being painted once/twice obviously wrong and still ACed before hacking phase lol.

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

    I got 2WA(typos) during the contest.
    Hacked.
    2 more WA during up solving.
    Finally Accepted?

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

why my submit be hacked?

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

    my a problems have be hacked ,can you give me some adives?

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

      for the test 1 0 3 1 your code gives the answer 0,but true answer is 1,because the string can be (( )( )( )( ));

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

How to solve problem E？

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

Oof my A got hacked, of all things. There goes my rating...

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

Why have the ratings not changed yet?

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

Getting older waiting for the system test o_o

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

Why the rating didn't change?

Is it unrated?

Or The system testing didn't finish?

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

    My rating changed as soon as I write this.

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

I wonder why this solution gives a TLE on test case 9 in problem — C (https://codeforces.me/contest/1132/submission/50857265). I went through other solutions and they were more or less same as mine (2 cumulative arrays).

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

    You have an error on line 19, you have pair<int, int> parr[n]; but it should be pair<int, int> parr[q];.

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

Can someone please comment more on this solution http://www.usaco.org/current/data/sol_lifeguards_platinum_jan18.html for problem C?

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

please publish editorial with neat codes.

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

When is the tutorial going to be published?

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

Pretests for C should have been stronger

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

with this contest I finally became blue! it took a long time what eventually I made it :))) If you are also struggling to go Cyan -> Blue, keep it up because it is worth it!

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

Editorial please.

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

How to solve 1132G - Жадные подпоследовательности

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

waiting for editorial

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

When you screw up the competition and get demoted to blue, but out of pure spite you want to bring everyone else with you. spite

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

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

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

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

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

Third question(C) is little bit more tricky from last div2"s third question.

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

    Well, luckily, the next div2C is more likely to be even easier than edu C!

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

I dont like the way how announcement of prob.C works. When I read "**so you decided to hire q painters to paint it**", in my mind had a confusion, if q painters would paint all the sections or not, but then I answered this for myself that "**q painters to paint it**" meaned all sections would be painted if q painters all worked. Because I joined virtual contest, so I got wa, and the question came back again with another answer: may be not all of sections would be painted, and I tried again and got ac. For now, I still wonder, if someone want to paint their fence, they must make sure that all their fence is painted, or maybe Im just a stupid man try to talk bullshit without anyone's care. Plz tell me your opinions, thanks alot.

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

RIP. I should do all possible cases for Binary search of Binary search

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

I am very interested in how the top hackers find our wrong solution and hack us(Just interested, I know why i was hacked).

-- I solved BCF and my A was hacked and I have the same score as others who solved ABC QAQ

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

    As we all know that this educational codeforces round had 12 more hours to hack any solution.Maybe there was somebody interested in hacking solutions or they wanted to get a higher rank. So they tried their best to hack others' solutions(Holland_Pig's own opinion).

    → Reply