doreshnikov's blog

By doreshnikov, 3 weeks ago, translation, In English

1547A - Shortest Path with Obstacle

Idea: MikeMirzayanov

Tutorial
Solution

1547B - Alphabetical Strings

Idea: MikeMirzayanov

Tutorial
Solution

1547C - Pair Programming

Idea: geranazavr555, MikeMirzayanov

Tutorial
Solution

1547D - Co-growing Sequence

Idea: doreshnikov

Tutorial
Solution

1547E - Air Conditioners

Idea: geranazavr555, MikeMirzayanov

Tutorial
Solution

1547F - Array Stabilization (GCD version)

Idea: doreshnikov

Tutorial
Solution

1547G - How Many Paths?

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +228
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

E was a wonderful problem to solve, love it!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u explain e?

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

      My solution differs from the editorial.

      Let's start with the following idea: if we shift a cell righter by 1, we get closer to the conditioners on the right side and get further from the conditioners on the left side.

      What this means is that we can precount the values for the very first cell with the given formula, and then we will have to see where do the air conditioners belong for the current cell, either on the right side or the left one, and change their current distance by the same value.

      I hope you're familiar with priority queues or at least sets, where we will keep pairs of values: the first will be the temperature value(not the initial one, but the one we've precounted with the formula for the first cell) and the second will be the position of the air conditioner on the line; this will give us the minimum value instantly.

      We will have to use two sets: one is for the left side, the other is for the right side. At first, all the conditioners obviously belong on the right side, so you should fill the right set.

      The loop from 0 to n — 1 is where the magic happens. We should take the minimum conditioner off top the right set and see if it is an impostor and should have been already swapped to the left side, because its position is smaller than the position for our current cell; if it has to be swapped to the left side, then we should delete it from the right set, update the temperature value for its pair, which will become its initial value + 1 — i, and insert that to the left set(if you're struggling with how to get the initial value, you can use map, where the key would be the conditioner's position and the value would be the index in the array of initial values). After we've done that, we can be sure that the conditioners do belong to the right sets.

      As we've assumed that we get closer to the right conditioners and further from the left ones, this means that we can find the minimum value as

      min((*left_side.begin()).second + i, (*right_side.begin()).second - i);
      

      This would give us the complexity of O(n + k * log(k)). Here's my solution with priority queues.

      I probably explained it badly, you might also want to see Colin Galen's solution(1:42:52), which is the same as in the editorial and is quite good.

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

        Hello, I think I came up an idea like you after the contest end. But my code got TLE. Can you take a look? 122107507

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

          Fixed: 122137899

          1. You probably messed up with a formula a bit. I'm not saying it is incorrect because it was rather hard to understand the logic behind (n — i), but using just plain -i and +i looks easier for me.
          2. You don't check whether tmp1 does actually exist, i.e tmp1 != a.end(). Therefore *tmp1 is the reason of your TLE.
          3. You do the lower_bound() through the array a, but have you sorted it previously? Its elements can be a total mess and the function would return random stuff depending on the order of the input elements(we're not guaranteed that the input is sorted).
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you very much! You save my night.

            1. Yeah, I stucked with that a bit, so my formula looked bad. But it still work :))
            2. That what I need. Thanks again!
            3. I was put a[] and b[] to a pair {a[i], b[i]} and sort it on the top, then put them back. Look a bit strange but I don't want to change the others :))

            Have a good day man!

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

      E is actually a bunch of simple "V" curves that form a convex lower packet, the solution splits it into positive and negative slopes to be considered separately

»
3 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

F and G were absolute gold. Thanks for the set!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yep, G was also my fav and most painful too haha.

»
3 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

The number of accepted solutions increased gradual way.

Proves that Level of question increased in a very uniform way. Loved this !!!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you have discord server or group that you discuss i want to connect with you and want to learn

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

      I am a pupil bruh, not much to teach anyway

      I can give you advice that after every contest, watch upsolving videos on youtube and if they use a concept you are not aware of, go watch tutorial series of that concept

      And of course, Keep practicing

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Fast editorial!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, I really liked this contest, not just because I am expected to gain 127 points.

A -> well, it's problem A.

B -> nice, introductory 2 pointer

C -> this took me a while because I was chasing down the wrong rabbithole

D -> interesting bit problem

E -> nice, but easy, problem

F -> nice segment tree

G -> couldn't solve

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how to solve F using segment tree

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 4   Vote: I like it +32 Vote: I do not like it

      Let's imagine our array in stages. For convenience, I duplicated my array just to deal with the cyclic nature of the problem.

      $$$a_1, a_2, a_3, \dots a_n$$$

      $$$\gcd(a_1,a_2), \gcd(a_2, a_3), \dots \gcd(a_n, a_{n + 1} )$$$

      $$$\gcd(a_1,a_2, a_3), \gcd(a_2, a_3, a_4), \dots \gcd(a_n, a_{n + 1}, a_{n + 2})$$$

      etc

      So let's binary search on the answer. Say, we are wondering if the answer of 3 is possible. Then, we want to ensure that $$$\gcd(a_1,a_2, a_3) = \gcd(a_2, a_3, a_4) = \dots = \gcd(a_n, a_{n + 1}, a_{n + 2})$$$. We can check this using a segment tree with range gcd queries. Since we do a binary search, we have a final of $$$\mathcal{O}(N \log N \log N \log (\max(A_i ))$$$

      Solution
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        cool

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

        Actually the time complexity is O(N"LogN*LogN*Log(Max(a[i])) , N*LogN for segment tree , Log N for binary search , and Log Max(A[i]) for GCD function .

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oops, yes, my bad

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

          Time complexity is $$$O(N\log{N}(\log{N} + \log{MAX}))$$$, only two log factors.

          If you take gcd $$$x$$$ times, time complexity is $$$O(x + \log{MAX})$$$.

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

            How did you get this equation?

            Logarithmic time complexity for the worst case of Euclid gcd algorithm is bounded by sequential Fibonacci numbers and it sounds impossible to guarantee a big count of gcd operations on them in segment tree. Is it that?

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

        Why do you not try the Sparse Table?It can solve this problem in O(n log n)

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Two logs, I suppose.

          One for Sparse Table, and one for gcd.

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

        another approach could be to check for every number that after how many steps or how right we'll have to go so that the gcd is 1 (I divided all the numbers by the gcd of the whole array in the start) then we take the max value. we can use seg tree to find the gcd of i to m (mid in binary search) the net complexity would be n*log^2(n)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey Olympia, I have tried using the same approach as you have mentioned above. I have done a binary search for each element in the array and then found the first point where the segment of the array will be equal to the gcd of the entire array. I have used range queries( segment tree) for doing so. Here is a link to my submission. Could you please guide me as to where I went wrong. Thank you.

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

        I am quite noob :((, I don't understand why gcd(a1,a2,a3) = gcd(a2,a3,a4) = ... gcd(a(n-2), a(n-1), a(n). Can you explain that.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          He is explaining an example where after two steps every element in array will become equal.

          (a1,a2,a3) = gcd(a2,a3,a4) = ... gcd(a(n-2), a(n-1), a(n)

          is only true for the case when ans=2 or ans=0.

          ans= No. of steps.

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

    My solution to G.

    You can do a basic DFS to find if the answer is 0 or 1 or 2 for every component.

    Use Tarjan's SCC algorithm to find all strongly connected components. Do a multisourced BFS from every SCC reachable from 1. Every node reachable by this BFS is a -1.

    This solution works in O(N).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do you predict your rating change?

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

      Incase you're using chrome, this will help: CF-predictor

      It's not very accurate, but good enough to make you happy or sad.

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

Please, fix the code of F.
Fix this line: const unsigned int MAX_A = 1000'000;

Thank you for D, E and F. Didn't see G.

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

    The code itself is technically correct but it's incorrectly parsed by the code highlighter tool. Will fix it in a few seconds, thank you!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest + Fast editorial

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Maybe it is just me who came up with bad solutions (dp for C, dijkstra for E, bfs-based toposort for G), but the implementation was quite painful for most of the problems today. Not something worth coming to Codeforces for :c

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

    you did come up with bad solutions, on C you can do a greedy algorithm (always try to add more lines), on E it's a simple dp where you try to find the best temperature from 1 to i and from i to n (in the end you combine both dp) and on G you can do a dfs and not pass through a guy only if he has infinite paths (you also need to store which vertices you passed through in your dfs), making you only pass through each vertice at most twice

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

      I don't question the fact that my solutions are bad, and I have also read the editorials, but I still think that implementations are unpleasant.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't C greedy? You take from either one as long as you can (need enough 0s). if stuck, no answer.

    E can be solved greedily. Start from the coolest AC and update all the cells unless a cell already has a better AC planted on it. Keep doing that for all ACs sorted from coolest to hottest. It can be proved that no cell will be updated more than twice.

    Couldn't solve F or G.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes it is, but I didn't want to think and proof anything, so just implemented the first idea I got, so dumb

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

        Well, my implementation to all questions are short imo. Well, I'm not too sure as I started CP recently.

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

    i used bfs for E, welcome to the "overthinking" club

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

    I used lazy segment tree on E....I knew it's pretty bad when I started to debug. Edit: I'm surprised that my segment tree solution runs as fast as the linear solution.

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

      Can you explain how to solve E using segment tree? Thanks.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm not sure how to solve E using Lazy segment tree..

      But one can solve the problem using two normal segment tree's itself.

      My code: 121978627

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's helpful. Thank you.

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Just to confirm, for F, using Sparse Table shouldn't TLE right?

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

    It shouldn't because even Segment trees are passing

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

    Not at all, I have used sparse table and my sol passed within 400ms. You can have a look at my solution if u want.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This round made me want to commit not alive

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Almost greedyforces, upto E. F was a nice problem.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

At the end of time I just know how to solve it but too late. Anyway I thing F is great. Great contest. Love!

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

I used some kind of Dijkstra Algorithm (multi source) to solve E

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how ? can you explain

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

      So I push the initial temp to a priority queue, and start processing by the lowest one, supposed it's T. Then I push T+1 to its left and right, and put them in the priority queue

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

        I found a very cool approach in which I first iterated from left to right and store the minimum temperature in the temp list and then from right to left and did the same at last the minimum temperature is stored in the respective position.

        Well fonmagnus can you please suggest me how can I do good in contests. It's been 1 and half year since I started and till now I am in Green. I don't know what is happening but eveyone else is just better than me !

        What should I do ?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just look at my profile to feel better

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I know the time I was in a condition like you are right now. But life is all about doing till the end that's it ! Life is too short to be small :)

»
3 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

During the contest, I think problem G is a wonderful problem since it's exactly a proper problem for those who just learn strongly connected components to practise.

However, seeing the editorial, I think the G is more wonderful than I have thinked.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain what is in the editorial... I don't understand "what's that visit in line means"... please help me with the same explanation in a simpler manner fried-chicken.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

please, somebody, tell me... why my solution is wrong for problem B and which test cases it is failing... 121938514

there is a minute error... i.g. some very minute error is present... it failed the 5002nd case which is not visible.

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

    The error seems to come on the string "abcdefghijklmnopqrstuvwxyz", your code gives No as output. I checked your code and it's because of the array declaration int alphabets[25], it should have a size of 26 not 25.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it -41 Vote: I do not like it

      checked this for my code ... It is giving correct output

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

        First, completely unecessary to call him a dickhead for helping you.

        Second, you are wrong. In your computer it works because even though you are accessing a higher index than you allocated it doesn't give an error, which can happen sometimes when you're in your local computer, but it will give an error on codeforces and can give an error on some other computer (like brobat's).

        The worst part is that that's not the only reason why the code is wrong because you got wrong answer instead of runtime error, so your idea is also wrong

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's not necessary that the idea is wrong, accessing elements out of array bounds can return unexpected values and not RE — and that can cause WA.

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

            As far as i know, in codeforces they actually go out of their way to check if you're accessing the array in bounds and not only give you a runtime error but they also highlight the line where this is happening.

            And the idea is wrong, they check where 'a' is and sees if the values increase as they go to the sides. This is not sufficient as "zax" would work but isn't actually a valid string. Also i believe the array they use to track frequencies can hold garbage data but im not sure

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      sorry for my previous comment... you are right... thnx alot ;)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I used binary search+ sliding window(with map/unordered_map) but why this code is giving TLE? complexity seems like O(n*factors[a[i]]*log(n*fact[a[i]]) (including map factor)

[submission:link]

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

There is no need to find the position of 'a' in problem B, we can start checking the values from endpoints of string as well...

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I have a very easy to understand solution for E: https://codeforces.com/contest/1547/submission/122007085

Iterate over conditioners, and for each go left and right, while you can cool down cells, it gives you O(n+k).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact O(n*k), can be improved to O(k*logk+n), if you sort conditioners first, but still not enough to pass

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome contest. Where can I find more problems similar to D?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to do A,C,D. But I got WA for B. I don't know where I did a mistake.Every test case I tried randomly seems to be fine.

Can someone plz help me with it?

https://codeforces.com/contest/1547/submission/121969497

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

    The same happened to me, dude... I don't know where's the problem... you help me please 121938514 this is my solution... please please help me as soon as you get it

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, you can use 2 pointer approach here

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

      Hey , I_Love_APUK, your approach is correct but , when we declare an array of size n it means it takes values from index 0 to index n-1. You declare int alphabets[25] which takes values from index 0 to index 24.It means you can't count frequency of z. So , just increase the size of alphabets array to count the frequencies of all characters. here is your updated code after increasing the size of alphabets array. https://codeforces.com/problemset/submission/1547/122030965.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, sure

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think you just read the problem wrong because i have no idea of what you're checking. Could you elaborate on your idea?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First I'm checking for duplicates and any alphabet whose value is greater than length of string(considering a's value to be 1.If string length is 3 only a,b,c can be there.) and storing the positions of characters.

      Now as we build from lowest alphabet, each character can go to right or left of string,i.e it can just be beside previous character or at other extreme(so the gap between to consecutive alphabets would be equal to all the previous letters before these 2 consecutive ones).( abs(mp[i]-mp[i-1])==1 || abs(mp[i]-mp[i-1])==i)

      As we're building and checking the gap from lowest pair of consecutive alphabets ,if for all alphabets until length of string ,every condition satisfies then it would be alphabetical string.

      Hope this helps :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest!thanks for every writer and tester

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

Another solution for B: 121926279

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dude please tell me why 121938514 is wrong... please

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are not considering character '$$$z$$$' in your alphabet. Try "abcdefghijklmnopqrstuvwxyz" and you will see it. You are answering NO and it should be YES.

      PD: just increase your alphabet array size from 25 to 26 and you will get accepted :)

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Test Cases separated by a line helped a lot while debugging. Please continue doing so.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Pizzeria Queries sends its regards.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I used priority queue to solve E.121971913

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

Am I the only one who used the minimum on the queue to solve the problem F? 121980439

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution, please?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I usd struct similar to the one described here.

      Instead of the minimum, I implemented the gcd function.

      Using two pointers and this struct i found longest segment where gcd() not equal to one.

      Its length is the solution to the problem.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your sharing your solution. Learnt something new.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My own solutions for B, C and E:

B. If we reverse the operations, we'll need to remove letters from the beginning or from the end of the given string. Two pointers (L and R) showed the part of the string that is not removed yet. So I iterated on letters from 'a'+s.length()-1 to 'a' and shifted one of the pointers. That allows to solve this task in O(n), not O(n^2) as in editorial.

C. On each turn, we can take the minimum of a[i] and b[j] — if it's invalid, the other value is invalid as well. So, checks with a[i] == 0 and b[j] == 0 are not needed.

E. Tried to add only "effective" conditioners — conditioners which cool some cells. I sorted the given conditioners by increase of their temperature and iterated over them, checking if some conditioners could be skipped. Then, the answer is affected only with conditioners near the cell (the nearest on left side and the nearest on right side).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

121992524

Please provide some hint on where this solution seems to be incorrect.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What does && k!=0 mean in if((i<n && a[i]==0 )||(j<m && b[j]==0) && k!=0)?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$k = 0$$$
    Array $$$a=[1]$$$
    Array $$$b=[0]$$$

    You are not finding a solution while there is one: $$$[0,1]$$$.

    PD: just remove condition k!=0 to insert a new line and you will get accepted. You don't care if there are or there are not lines to insert a new one.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it was a realy good contest thanks for all setters and testers for make beautiful contest

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D was the best and I really liked it =)

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

https://codeforces.com/contest/1547/submission/122014795

Can someone please help me understand what I did wrong, maybe suggest me the wrong/edge test cases? I am not passing test case 2. I tried to use 2 pointer approach. I have commented for better readability. Thanks in advance!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nevermind, I'm a dumbfuck who complicates things. I actually forgot to check the case if a string doesn't have the character 'a' in one of my if conditions.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, can anybody give me a proof why minimum distance between two points $$$D$$$ = $$$\mid X - X^\prime \mid$$$ + $$$\mid Y - Y^\prime \mid$$$

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem: 1547F - Array Stabilization (GCD version) can be solved using two pointers stack trick, which can be learned through EDU "Two Pointer" section. Link: https://codeforces.com/edu/course/2/lesson/9/2, video is called "Segment with Small Spread", my solution: 122018965

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

Problem E was really interesting!

But I think, there is a small mistake in Editorial. In my opinion, it should be $$$L_{i}=min(L_{i-1}+1,c_{i})$$$ instead of $$$L_{i}=min(L_{i+1}+1,c_{i})$$$

Thanks for contest again!

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

For problem D, there is a solution using greedy with less thinking, but with a little worse time complexity.

If we treat every integer as a 29 bits binary numbers. To make $$$y$$$ lexicographically minimal, start scan the sequence from position 1, and each time try make $$$y_i$$$ as minimum as possible.

First of all, $$$y_1 = 0$$$.

And then for $$$i > 1$$$, we can let $$$y_i = g(x_i)$$$ first, where $$$g(x_i)$$$ is bitwise-not of $$$x_i$$$. Since by doing this, $$$x_i \oplus y_i$$$ will be all 1's, and this must satisfy the requirement of growing.

After this, we can enumerate every 1 in $$$y_i$$$ from higer position, and change every 1 to 0 if possible.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem G, one of the test cases is:

3 2 3 3 2 2

my answer was 1 0 0 expected answer: 1 -1 -1

acc to me, there ate 0 ways to go from vertex 1 to vertex 2 or 3. but expected answer was that there are infinite solutions. Am i missing something? My Solution link

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

    Check it in CF's custom test, your answer is "1 -1 -1 " to this test, which is wrong and the correct answer is "1 0 0". Maybe you've read "Answer" part instead of "Output" part.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E has a greedy $$$\mathcal{O}(n*\log(n))$$$ solution. Check my submission.

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

Problem C

Can you help me figure out whats wrong in my code? My code:https://codeforces.com/contest/1547/submission/122039447

I just sorted both the vectors and merged them in non decreasing order and looked for no of zeroes if k+count_of_zeroes==max element of the merged array print the array else print -1

Is there anything wrong with my logic

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is you are sorting array $$$a$$$ and $$$b$$$ so you are not doing the operations in proper order. Also, you are not always satisfying 6th paragraph:

    "Restore their common sequence of actions of length n+m such that all actions would be correct — there should be no changes to lines that do not yet exist. Keep in mind that in the common sequence Monocarp's actions should form the subsequence $$$[a_1,a_2,\dots,a_n]$$$ and Polycarp's — subsequence $$$[b_1,b_2,\dots,b_m]$$$. They can replace each other at the computer any number of times."

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain proper order a little more if you dont mind?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$k=0$$$
        Array $$$a=[1,0]$$$
        Array $$$b=[2,0]$$$

        You are doing the operations in this order: $$$[0,0,1,2]$$$.

        While there is no valid operation because in this test case because you need to change line #1 or line #2 before inserting a new line.

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

Problem E was easier than I thought...

My solution was different, involving Segment Trees (This is an overkill, btw).

I had solved a kind-of-similar problem on CSES. The problem: Pizzeria Queries

The major difference being that there were updates in that problem. However, I went ahead and coded up that solution during the contest. After the contest did I realise how simple and elegant the code for E was.

Anyways, incase someone is interested in the code: 121978627

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was even more different — I used Treap. I've thought of Segment tree, but didn't understand, how to account elements only later than i in it.

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

      USACO guide has explained the solution for Pizzeria Queries pretty well.

      The code I implemented is pretty similar to the guide's solution.

      Incase you want to understand how to solve it using segment trees, you can look into the solution linked above.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone look at this solution for E. I used bfs for it, but for some reason I got TLE on test 12. Can someone spot a mistake that causes an infinite loop, because it should run in O(n)

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

I got an AC solution for G but I can't prove it's correct. My idea was to put tags on the vertices to indicate if they are of the type -1 or 2. I do a first DFS putting tags -1 or 2 in the vertices that have color black or gray (respectively) when checking the condition color == white. Then I do a second DFS propagating the tags. I thought this would be enough but it gave WA on test 4. Then I did a third DFS propagating the tags again and it got AC. Here is the link to the submission. I found very weird that the first solution didn't pass and the second passed. Is it really correct ? Maybe the tests are weak.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I request to add more Div.3 Contests in a month.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F is heck of a problem!!!✨

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmmm!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

A bit different approach to problem F:

Notice, that the number of times a[i] changes is small (worst case is log(a[i]), I believe). So if we can do a brute-force solution where we only change the elements that need to be changed, we can get N*log(MaxValue) complexity.

Note, that a[i] changes only if it's not a divisor of a[i+1]. Let's keep track of segments of elements where $$$a[l] \mathrel{\vdots} a[l+1] \mathrel{\vdots} ... \mathrel{\vdots} a[r]$$$. Only the last element may change after one iteration. It's also pretty straightforward to update the segments after the iteration as well.

Code: 122069028 ( I used std::set here, so the complexity is not optimal, you can rewrite it using std::vector).

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

If you're interested in a video, I explained all the problems on stream, and you can watch at https://youtu.be/QKW3_9RFxDI

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it possible to do binary search on the F sum? like by taking x over 0 to n steps ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, you can binary search on the number of operations. Basically, at $$$k$$$ th step $$$a_i$$$ becomes $$$gcd(a_i, ... , a_{(i+k)\%n})$$$. And to calculate gcd fast, you can use binary lifting. Look at my solution 121972800. This is $$$\mathcal{O}(n\cdot log^2 n)$$$ but you can make it faster by combining binary lifting and binary search. Similar to the idea mentioned here.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem E was great. Can Problem E be solved using priority_queue ?

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

You know, prob G's sol is really a good way to exercise my mind. Love it very much !!!!!

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I have solved the problem F. But I saw a simple elegant solution with quick execution time #123564925 However, in my opinion, it's an O(n^2) solution, n for iterations of n while iterations. What's differences between this and brute force solution, or how to prove that the while iteration would not exceed some limits. Thanks for reading my question.