By PikMike, history, 5 months 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 Ne0n25 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 V--gLaSsH0ldEr593--V 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 MohamedAhmed04 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 V--gLaSsH0ldEr593--V 0:01
B 1021869 0:03
C V--gLaSsH0ldEr593--V 0:08
D V--gLaSsH0ldEr593--V 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

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

Wish interesting tasks!

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

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

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

Already waiting for editorial.

»
5 months ago, # |
  Vote: I like it -28 Vote: I do not like it

omfg i cant waitr

»
5 months ago, # |
  Vote: I like it -102 Vote: I do not like it

i guess most of cf users are poor

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

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

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

»
4 months ago, # |
  Vote: I like it -33 Vote: I do not like it

I want high rating.

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

Wish you happy coding =)

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

I want easy tasks so I can get high rating!

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

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

    I want hard tasks so others can get low rating!

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

      thanks you for getting low ratings everybody!

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

      why users like you don't stop writing stupid comments like this? you are one of them, so can you answer???

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

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

      if you solve more tasks you have a higher rank

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

»
4 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Deleted

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

Please suggest some problems like C today for practice

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

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

How to solve F?

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

    https://codeforces.com/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

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

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

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

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

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

How to not get MLE on G?

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

Was D binary search + simulation?

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

    How to do the simulation?

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

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

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

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

      How to do the simulation? :)

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

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

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

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

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

            His approach might got TLE if implemented poorly.

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

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

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

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

                  I see now, thanks.

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

                  Akikaze Hey,can you tell why there is difference in the time taken b/w PQ and array of sets, i mean it has to do sth with the data retrieval i know, but i just wanted the insights. Thanks for the help!

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

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

        But I pass with 2432ms time :v

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

          You got too much luck yesterday bro :D

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

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

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

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

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

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

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 months 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))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

What was testcase #5 in C?

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

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

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

50857122 why does this give WA on test case 5?

»
4 months ago, # |
  Vote: I like it -44 Vote: I do not like it

So shitty D

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

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

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

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

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

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

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

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

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

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

How to solve C if constraints were 10^5 ?

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

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

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

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

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

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

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

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

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

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

Yall got any idea why this 50850982 gets WA?

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

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

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

»
4 months ago, # |
  Vote: I like it -55 Vote: I do not like it

Many tasks can be found on informatics.msk.ru

»
4 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone please explain this solution?

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

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

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

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

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

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

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

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

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

    you can not put it like this ()() because (( or )) or () or )( both will always remain together you can't separate them. 0 1 1 0 in this test case combination will like as following ())( or )(() so answer will 0;

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

»
4 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How to solve C for n, m = 106?

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

Can C be solved in linear time?

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

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

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

»
4 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it
  • Can we consider Problem C as a merging intervals problem? I'll elaborate
  • Take in all the [L,R] pairs as input in an array 'a'
  • Sort the intervals array wrt to L
  • Let's take t to be the first pair in the sorted array that is t = a[0]
  • Two pairs a and b are fully_disjoint if a.second<b.first or b.second<a.first ~~~~~
function combine(hash_map contribute,int key,pair a,pair b) {
    int contri=0
    if a.first>b.first && a.second>=b.second:
        contri=a.first-b.first
    if a.first<=b.first && a.second<b.second:
        contri=b.second-a.second
    if a.first>b.first && a.second<b.second:
        contri=a.first-b.first+b.second-a.second
    contribute[key]=contri
    a[0]=min(a[0],b[0])
    a[1]=max(a[1],b[1])
    
    return a
}
contribute = {} //hash_map declaration
// add a new key-value pair like contribute[new_key]=value
contribute[0]=a[0].second-a[0].first+1
for i from [1,a.length):
    if fully_disjoint(t,a[i]):
        stack.push(a[i])
        contributions[i]=a[i].second-a[i].first+1
        t = stack[-1] // The last element which was recently pushed
        continue
    stack[-1] = combine(contribute,i,t,a[i])
    t = stack[-1]

~~~~~ And after that contribute.values() that is all the values occurring in the hash_map can be sorted in reverse order and the respective contributions can be added till the last two values.

That was my logic. I know it's very complicated. Also apologize for the weird ass pseudo code, like a hybrid of python,javascript but I just wanted to know what was wrong with it. Couldn't submit it in time, "Still learning".

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

How to solve G??

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

»
4 months ago, # |
  Vote: I like it -20 Vote: I do not like it

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

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

Has anyone solved C using DP?

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

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

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

why my submit be hacked?

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

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

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

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

How to solve problem E?

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

Wish interesting tasks next time !

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

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

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

Why have the ratings not changed yet?

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

Getting older waiting for the system test o_o

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

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

    My rating changed as soon as I write this.

»
4 months 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.com/contest/1132/submission/50857265). I went through other solutions and they were more or less same as mine (2 cumulative arrays).

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

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

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

please publish editorial with neat codes.

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

When is the tutorial going to be published?

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

Pretests for C should have been stronger

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

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

Editorial please.

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

waiting for editorial

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

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

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

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

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

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

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

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

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

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

  • »
    »
    4 months ago, # ^ |
      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.

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

how to solve E? I used the dfs and got a tle