By awoo, history, 2 years ago, translation, In English

Hello Codeforces!

On Jul/08/2022 17:35 (Moscow time) Educational Codeforces Round 131 (Rated for Div. 2) 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 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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by 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 the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space

Hey, Codeforces!

Welcome to the 131st educational round hosted by Harbour.Space and Codeforces.

Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 10 days intensive Summer Camp organized by Harbour.Space and Leagues of Code.

Don’t forget about the discounts for participating in our Summer Camp. Every member of the Codeforces community gets a 30% discount for on-site participation or a 50% discount for online participation with promo-code CFLOC2022.

Our Summer Camp is a training program that will teach participants competitive programming. It will take place in Barcelona and online on July 18-29, both participation formats are available.

We are inviting students ages 10 to 24, interested in improving their skills or seeking intensive, high-level training prior to the IOI. Teachers in the camp will be ICPC World Final Silver medalist 244mhq, SWERC 2022 Winners MaksymOboznyi, ICPC World Final Champion pashka and others. Participants will be divided into classes based on their level and previous experience. Classes will be held in English.

Learn more →

Harbour.Space

Good luck with the round!

UPD: Editorial is out

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

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it -38 Vote: I do not like it
Don't open
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -22 Vote: I do not like it

    Don't open

    upd.: why so many downvotes?(

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

      Rare to see no constructive algorithm in this contest.

»
2 years ago, # |
  Vote: I like it +81 Vote: I do not like it

 ****

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

say something irrelevant: what happened to the last div2? my little ratings is missing. hope i can get them back in this round. TAT

»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I shook hands with almost all grandmasters in the blog and all candidates

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

excited for my first round

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know about the A problem and I am gonna reveal it I am 100% sure it would be of xor :|

»
2 years ago, # |
Rev. 2   Vote: I like it -62 Vote: I do not like it

.

»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

What’s up with people commenting about Div 2A being a xor problem? Do people hate bitwise operation problems? I always thought problems about bitwise operations are possibly one of the most versatile topics, from basic observation problems all the way up to like FWHT, and one should definitely practice them and for most “easy” problems, the most you have to do is knowing the basic properties+considering each bit separately. Lmk if you disagree

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

    I am really struggling to solve bitwise questions. Any tips?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Well, I guess that xor is an uncommon topic for beginners, so appearing on div2A would be a bit scary to them. But I don't think they were that bad, after a few rounds I got used to those problems and it was pretty fun solving them too

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

    Don't even see how you needed XOR here — there's only 3 cases:

    • 2 opposite corners, so the answer is 2;
    • All spaces are empty, so answer is 0;
    • Answer is 1 otherwise.

    Edit: I misremembered the question, the answer is 2 only if all the spaces are filled.

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

      Oh this comment was written before the contest in response to some people above complaining about xor problems lol.

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

        Oh, I see. My bad for misunderstanding then.

        I saw someone else complain about it which was why I responded, but they might have been complaining about a previous contest as well.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

high HOPES with this round

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

can anyone guess the rating level of 3rd problem in today's contest?

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

spermutation forces

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Everything is correct with my code for problem C, but I'm getting WA on test case 2

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

    That means your code is not correct.

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

    Can it be solved by heap?? just asking

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

      Yes, its possible. Look at my code that I submitted after contest.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Good round, interesting tasks. Although i'm too weak to solve most of them during the contest.

Thanks for the round, thanks for Codeforces.

Waiting for the result and rating change... (I'm so unwilling to receive such a low rank...)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

God, how much more time will it take to reach Cyan?

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

Overall, a balanced educational round

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hmm, D doesn't budge for me :D.

Any tips? Only thing I've realized is that we always know where 1 is but other than that it may depend :<

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

    If $$$\lfloor \dfrac{i}{a_i} \rfloor$$$ is equal to $$$b_i$$$, it means that $$$a_i$$$ should be in some segment of integers. For each $$$i$$$, generate this segment, and then match each value from $$$1$$$ to $$$n$$$ with a segment greedily.

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

      I find the segment thing. I just did'nt know how to match the values from 1 to n.

      I though that sorting the segment by length could help. But it's gives WA

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

        Sort by left border, then keep a data structure that stores all currently opened and unmatched segment, sorted by their right border. When we come across a number while iterating from $$$1$$$ to $$$n$$$, we match it with an open segment with the lowest right border (because it will become unsuitable earlier than other segments).

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

          Why is it incorrect to just sort by the right border only ?

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

          why does sorting the segments by length in ascending doesn't work ?

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

            Suppose there are two segments with values $$$[1, 2]$$$, one segment with values $$$[3, 3]$$$, one with values $$$[4, 4]$$$, and four with values $$$[5, 8]$$$. Then, these four are the longest ones, but no point from $$$1$$$ to $$$4$$$ can be matched with them. So we need to start with the ones with the minimum left border.

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

          Would it be possible to get the total number of valid permutations to get sequence b?

          I was thinking in terms of the total number of segments that have the same closing time, but could not reach a conclusion.

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

    Looking at the solves, probably my solution is way too complicated and there is something simpler..

    First decompose each element into the ranges it can exist if the answer is k (which is i+1 to n if it is 0, i/(k+1) + 1 to i/k otherwise).

    Keep these ranges grouped by starting position (and also sort by length). Now, for the i'th turn do the following

    1: Add the smallest range by length from the i'th group (i.e. all ranges that are of the form [i,?]) to your processing group. 2. Remove the smallest range from your processing group. Place the index of this range at position i 3. Whichever group the range you just removed was from, add it's smallest range to your processing group.

    Submission:

    163296621

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In D we can calculate foreach position a minimum and a maximum value, consider them to be segments. Then sort these segments by the min value.

Iterate all numbers i from 1 to n, and foreach number collect all segments with $$$min<=i$$$. From these collected segments choose the one with minimal max value, and mark that segment as used.

It took me ages to get the formulars for min and max by trial and error. How is this done correctly in time?

$$$min=((i+1)/(b[i]+1)+1$$$ ???

$$$max=(i+1)/b[i]$$$ for b[i]>0 ???

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

    Dang really nice solution.

    Hmm maybe it would be easier just binsearching min and max for each segment :D?

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

      I guess that would be simplest for me, thanks for suggestion, did not thought of that.

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

    x>=k*y and x<=k*y+y-1 if x/y=k. Using these two inequalities you can find range of y.

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

    I had zero trouble with the formulas, but I struggled for ages with coming up with some range assignment algorithm...

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

      It is simple sweepline. Of all the segments currently open you should assign the current number to the segment that closes earliest which is obvious.

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

        Thanks — I suppose I'm new to this idea, it wasn't obvious to me

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

      the same

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

    Yeah so you know that floor(i/ai) = x, i/ai <= floor(i/ai), i/ai <= x, ai <= i/x,

    floor(i/ai) + 1 > i/ai, x +1 > i/ai, ai > i/(x+1)

    and that's how you do it

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

    $$$\lfloor{\frac{i}{a[i]}} \rfloor$$$ is $$$i \; div \; a[i]$$$. And $$$i \; div \; a[i]$$$ is the $$$max$$$ number $$$v$$$ such $$$a[i] \cdot v \le i$$$, but $$$a[i] \cdot (v+1) > i$$$.

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

    Couldn't find the formulars but managed to binary search it :3.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is greedily giving tasks to workers with no task right approach for C?

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

    Advanced Binary Search (like Book Allocation Problem) will do for C.

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

      How did you conclude it is solvable by binary search? I could only think in the greedy direction

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

        good job, the tags are: binary search,greedy. you have to apply the binary search algorithm to find the minimum hours needed. for example if 100 hour is enough so what about 50? not enough? ok maybe 75 will be enough. every time you change your range you have to check: can the first worker finish his favourite missions in (mid) hours? if he can finish so he can also work on some other mission that will take 2 hours so the first worker will do: fav + (mid-fav)/2. if he cannot finish in (mid) hours he can only work on: (mid) missions. and you have to do this for every worker with a for loop (or a while loop) if the total sum of the missions that the workers can do is greater or equal to (m) then the time you choose is a good answer, save the answer and move to a smaller range, but if it is strictly smaller than (m) it is not valid and you need a bigger (mid). :)

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

        we can just notice that if we can finish all the tasks in x days, we can finish them in x + y (y > 0) days as well, and at opposite: if we cant finish in x days, we cant finish in x — y days as well. and it's direct hint for binary search (but i confess i was thinking about greedy solution for about half an hour...)

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

    Binary Search Approach will work

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

    it's not too easy to implement — eg i was thinking about it for a half an hour, then i just wrote binsearch, which was really easier than the greedy solution

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

    Assign all 1-tasks to the workers, maintain the assigned tasks per worker in a list.

    Also maintain the last finish time of each worker in a queue, or sorted set.

    Then take first/earliest worker and last/latest worker from the queue, and asign a task from the latest to the earliest, put both again with the updated values onto the queue.

    Repeat until first and last differs by at most 2.

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

    Just assign all workers to tasks they can do with max efficiency.

    Now place them all in set. As long as largest element and smallest in set differ by >=3

    Reduce 1 from your largest element

    add 2 to your smallest element

    (you're simulating giving a task from one worker to another)

    In the end output the largest element in set

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

      Yeah, I thought of that, but I'm struck in getting largest and smallest duration after every simulation. How do we efficiently do that?

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

        Multiset if you're using C++.

        The element at M.begin() is the minimum; the element at M.rbegin() is the maximum.

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

    If you have a multiset of workers' task durations, repeat the following until the min duration >= max duration - 2: subtract one hour from the highest duration, add two hours to the lowest.

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

      In your solution for C, why did you delete the lower bound of lo and hi instead of deleting lo and hi itself?

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

        To be completely honest, it’s because I’m not very good with multisets so I do the safest possible thing. I only really took up C++ last year and before that I used Python, so my skills have a long way to go.

        The specific reason is that in the past I’ve made errors by accidentally deleting multiple instances, or the wrong iterator, and I know for sure that lower_bound is safe. One day I will bother to learn how everything works properly.

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why couldn't the memory limit for E be 512 MB? I think my solution would have passed 163297562. I didn't have the time to make optimizations :(

Still thanks for the round.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    Oh, I'm really sorry about that. I thought to make it 512MB but when I was calculating something like "5000^2 integers", I found that it is only about 100MB, so I decided that even two such matrices will fit and I decided to keep the memory limit as it is. :(

    UPD: Though, I just replaced all int matrices with short matrices, and your solution passed with 157MB peak memory used. I'm not blaming you, just informing that you could do something like that in the future. Because, for example, in this problem you couldn't meet any numbers greater than $$$O(n)$$$, so short is more than enough.

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

      Ohh, slipped through my mind that shorts are of 2 bytes. Thank you.

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

Why is this approach incorrect for D?

Every index i is satisfied by a range of values: [ (i+1)/(a[i]+1), i/a[i] ]. Now I sort the ranges increasing based on their left boundary. Now in these ranges, every value from 1 to N is covered atleast once, because it's given that the answer is always possible. Now I greedily give values 1 to N to the respective indices of these ranges in sorted order. I feel intuitively that this should work but it doesn't.

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

    Consider the segments in sweepline fashion. In all the segments that are currently open you should assign the current value to the one that closes the earliest. If you assign values in the manner you said then this wouldn't happen.

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

      Ahh got it.. Thanks.. Basically what I did would fail for cases where, let's say a later index has only one range ending at it, but this range gets assigned a former index because I'm sorting by starting points only

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

    what if n=3 and the ranges are (1,3) (1,3) (2,2)? I had also encountered the same problem but then realised that you have to sort by right boundary. I may still FST tho idk.

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

      In that case you would assign (1,3) first and then (2,2) next and then (1,3)

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

        yeah that's what i am saying that you have to sort by right not left

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

    range of values is [ (i/(a[i]+1)) + 1, i/a[i] ] or ( i/(a[i]+1), i/a[i] ]

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

    1
    7
    0 0 0 2 0 6 2

    Should be [X,X,X,2,X,1,3] (remaining numbers can be anything greater than their index)

»
2 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Fuck you and your shit harbour space, this is a disgusting contest. downvoted

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

    You should actually say that to your brain :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What can be the difficulty rating of C?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a hint on C ... like what I can try on that ??

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Binary Search the Answer. See this and this

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

    Binary search is fine but overcomplicated.

    Think of it more simply. Assign all tasks to the skilled person initially. Under what circumstances can you continue to make improvements?

    To give a hint: if someone is idle for 3 hours and there are tasks ongoing in that time, they could have done a 2 hour task and taken it from someone else.

»
2 years ago, # |
Rev. 2   Vote: I like it -46 Vote: I do not like it

Too standard and FUCKING STUPID problem F. How can this *1400 problem be put in the position of F??????

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I read both A's and B's statements incorrecty, and both of my solutions for wrong problems passed 1st tests :((((((

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a small testcase on which my submission gives wrong answer. This is my submission. 163284420

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

    bruh imagine you're a vendor and tell that the project can be finished in 343599 hours

    and then the next vendor finish it in 2 hours xD

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

      Yeah I'm not getting why it's giving wrong answer. I just want to see small testcase on which my submission fails.

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

    The problem are actually the large test cases since q and p can become very large. Make q and p long long and your solution should be correct.

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

      Thanks... Why I'm so dumb...

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

        I just realized that i made the same mistake. But somehow my solution passed ...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i have a question with problem C

from this code 163304299, i had a integer flow. so i change all int to long long like this 163303533, then i got correct.

plz tell me why...

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

    your rest can be negative number, and it can be less than INT_MIN.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why My solution for question C keep on giving wrong answer answer on test 2 I am using binary search https://codeforces.net/contest/1701/submission/163306213

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem C. Hello, can not imagine counter example for this approach, can you please help? Thanks.

Why does this idea on a problem C is wrong?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1701/submission/163296776 Can you please help me find an example where this greedy solution does not work?

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

    1

    5 15

    5 5 5 5 5 5 5 5 5 5 1 2 3 4 5

    Correct answer: 5. Your answer: 6.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Guys, What could possibly be wrong with my Problem C submission https://codeforces.net/contest/1701/submission/163308184

My approach is very greedy, but it seems to work.

Is there a way to get the buggy test case? Any kind soul help this poor fellow here please.

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

    You fail this case:

    1

    6 9

    1 1 1 2 2 2 3 3 3

    Ans = 2, yours = 3

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone Solved Problem C using Priority Queue? My solution is passing most of the tc. Anyone understanding the problem with my code please help Solution Link: https://codeforces.net/contest/1701/submission/163305827

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

    https://codeforces.net/contest/1701/submission/163281220 Here is my shitty but AC for now solution. Binary search is probably easier but I still can't solve any binary search problems that aren't leetcode easy so it never occurred to me during the contest(should probably start practicing it lol) plus I am addicted to using priority queue. I saw some people use multiset though which also seems way easier. I initially tried multiset but switched to priority queue. It is not the multiset fault though, I just had wrong idea at the time. I also don't know how to analyze algorithms but I am pretty sure my solution is $$$O(n \cdot \text{log} N)$$$ which is fine for 200000. Hopefully I don't get hacked lol.

    **Update : ** I resubmitted my solution with comments and removed some extraneous code which should make it clear what the code is doing.https://codeforces.net/contest/1701/submission/163322218

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I made video Solutions for A-D in case someone is interested.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone point me to more problems like D that I can practice? It would be a great help. _Wizard_King_ mentioned in the comments "It is simple sweepline". Where can I practice more of such problems. (thanks)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I coincidentally did 1348F - Феникс и память a few days ago, which had the same idea as problem D of this round.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of gaining 100+ points, I'm going to lose 50 points because I forgot about longs on question c, sad day for me.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone point out what's wrong with my submission. Failing on TestCase 3. https://codeforces.net/contest/1701/submission/163279323

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a pity. I could have made a D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will we get rating for this contest

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Standings for individual divisions are broken: Division 1, Division 2

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When will the editorial be available?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't seem to understand the time limit for F because there's a normal $$$O(Q \log M)$$$ solution using a lazy segment tree

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

    One of the implementations stores a $$$3 \times 3$$$ matrix in each segment tree node, and the operations are like "multiply by a $$$3 \times 3$$$ matrix on segment". I decided I didn't want to cut it off.

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

      Thank you for the explanation, that's reasonable. I thought there was some kind of $$$O(\sqrt Q)$$$ stuff involved.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for problem E?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. There is one useless operation type.
    2. It`s better (general) to delete symbols while going right to left not left to right.
    3. You can solve task with O(n^2).
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Sorry for my impatience, could anyone explain me the solution to problem E?

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

Please tell me how the problem F is solved.

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't register for the camp on time, is there another camp anytime soon?