1-gon's blog

By 1-gon, history, 4 months ago, In English
 
 
 
 
  • Vote: I like it
  • +382
  • Vote: I do not like it

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

Thanks for superfast editorial

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

Too difficult contest :(

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

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

    I always fail B. Did C2 but failed B yet again. The cost of getting C2 instead of D was also not worth it.

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

I didn't like C1, C2

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

    I didn't either during the contest but after reading the editorial I loved them. Although I think it's better to be replaced with d.

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

    It took me about 1 hour to solve C1. Right after I solved it and it passed pretests I was quite content but then I came to conclusion that my solution was wrong. And right now it turns out it was correct after all. C1 is quite a confusing task

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

This contest was not for below pupil I guess :). The questions were tough(for me at least), but the questions were good and it was a good learning experience. Thanks for the superfast editorial

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

    I feel like A and B are still pretty easy, but C is quite hard :(

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

      yup A was easy I wasn't sure of the thing that in B the answer could be only 1 or -1 :). Rest B was also easy to implement

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

      I felt C1 was fine, but C2 was pretty tough.

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

Problem C is quite similar to this problem: 1438C - Инженер Артем

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

can you add who were the authors of each problem as well?

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

C is hard this time lol

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

    It is a beautiful problem. You can just try to brute force one of these 3 patterns over the grid, and one of them will always satisfy the condition.

    1001	0100	0010
    0010	1001	0100
    0100	0010	1001
    1001	0100	0010
    

    The implementation is also easy.

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

      Same idea. but i was really not sure this conclusion is right, and even pretty sure it will fail system test, but it really work, what a surprise:)

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

      Yes, that’s what I did to C1, and it wasn’t an easy observation to see at first. For example, the first time I submitted, I only used one of the three pattern, but of course it fails lol.

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

Overkilled B and wasted 1 hour

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

I was solving a complete different problem for B until the last 20 minutes, where I sadly ignored the attract all points statement. Lets say it is possible to "choose" which points to attract to itself for a point and not all. The problem being similar to the making all elements equal in a 1D array, but here in a 2d plane, with the k parameter. How would we solve such a problem?

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

    I was also solving the same problem for around 1 hour after solving 1st problem.

    I coded it and then realized sample test 3 was not passing :(

    We should read the statements and test cases.

    Solution to your follow-up version

    create vectors for all points which have their distance to current point <= k;
    
    for ( p1 over all points)
     visited[n]={0};
     queue the current pair comprising of point p1 and distance  = 0
     count = 0
     while(queue is not empty)
         current point pcurrent = queue.pop();
         visited[pcurrent] = 1;
         count++;
         for( pneighbor = all points from vector created at start of pcurrent point)
            if (visited[pneighbor] == 0)
              queue.push(pair(pneighbor, pcurrent.first+1))//queue the neighor,add 1 to distance
                 visted[pneighbor] = 1;
    
       if(count == n)
         if (min < pcurret.first)
             min = pcurret.first
    
    
    output min

    The idea of this algo is that we start to converge all points farthest from a current point in context first and to its neighbor which was connected to current point by some number of attractions

    Let me know what you think of this

    https://pastebin.com/PADi4iFx

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

Accidentally solved C, but the proof is really hard to think out

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

    I was able to come up with the strategy to solve C1 but with only few minutes left on the clock. Gave all my time to D.

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

      Have the idea but don't have time is really sad

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

        Even worse is if you start implementing solution like 45 minutes before end and still can't make it on time

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

That feeling when you wrote the same algorithm as in editorial and still got the wrong answer....:(

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

C1 is like asking for some formular. You saw that one before and can remember, or not.

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

    No, it isn't. I haven't seen C1 before and there are a lot them.
    This is actually puzzle, sometimes you would be able to solve, sometimes you wont. I just needed a simple observation for C2 and I somehow missed that. This is how it goes.

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

      Coloring arguments like this one are very common in math olympiads. That may be where "saw before" comes from.

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

        Hey -is-this-fft-, could you please recommend problems with similar coloring arguments if possible or some resource where I might be able to get a gist of it.

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

Even I don't know how I solved D. Just kept adding bunch of if's and miraculously AC'D.

Beautiful Editorials though :)

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

    I also don't know how I solved D, just added binary search and got AC :)

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

      I used next smaller index. Was gonna lose like -50 rating, D saved the contest for me.

»
4 months ago, # |
Rev. 5   Vote: I like it -26 Vote: I do not like it

I solved D and I didn't know how I can. Did someone in me for a while? After read editorial, i was confusing:((((((

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

I got TLE during system test for D even though my solution was O(nlog^2(n)) where n<=1e5. Feels very sad man! I hope from next time the pretest for TL would be stronger.

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

    During contest your codes time was 1824 ms so with this information you can easily understand code need some more speed.

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

The point distribution suggests that doing both C1 and C2 was as difficult as doing D, but I felt like D was muuuch easier than even C1.

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

Problem C WAS confusing.

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

Please give my brain cells back nvm they are already dead.

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

Can anyone give some suggestions if my thinking come to a dead end.

In D, I spend all my time to think how to perform min on neighbor elements efficiently, like from [1,5,3,4,2] to [1,3,3,2], eagering to optimize O(n^2) to O(nlogn). I also think about some properties like increasing or decreasing sequence to speed up.

But when I saw the editorial, it is totally another way.

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

    I sometimes get this problem at harder CF problems and, at least in my case, the best solution is to just try a completely different approach to the problem. If this different approach is actually correct, congrats, all is left is to implement the solution. Otherwise, you can go back to your original ideas with a fresh mindset, which means you can notice things you previously haven't thought about.

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

      One thing I realize is that, if we want to gain more information (like simulating whole process in D, instead of just deciding whether a permutation), it usually requires a higher time complexity. So it may be a good way to rethink if we record redundent information, and what is the minimum necessary factors that matter

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

One of the best contest.

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

Thanks for the beautiful contest. I think I enjoyed today's contest the most out of all the one's I have attended so far.

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

Deleted

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

    That's not a sparse table implementation. It's a segment tree. I've a feeling you've probably copied code from somewhere.

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

I couldn't solve C1 and C2 in contest but after seeing the editorial, I just loved their solution. Two of the most amazing problems I've ever seen on Codeforces. Thanks 1-gon

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

.

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

My alternative solution to D:

For each element in the array, find the longest contiguous subarray containing it and surrounding elements which are no smaller than it. If that subarray has length $$$L$$$, we know that this element's value occurs as a compressed value for all $$$k \leq L$$$. Then to determine if a $$$k$$$-compressed array is a permutation, we want to know if all elements in $$$[1, N - k + 1]$$$ appear somewhere with $$$L \geq k$$$. It can be handled simply by precomputing the max $$$L$$$ for each distinct element and computing prefix mins.

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

    There is a binary search approach as well. only the first element of output can be 1 apart from it we bs the transition point for the rest of the array.

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

    Great solution! If someone is wondering how to find the length of the longest contiguous subarray containing itself and elements greater than or equal to itself in O(n), use monotonic stacks (read or google about it)

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

Alternative approach to D:

Note that if some value $$$a_i$$$ appears in a $$$k$$$-compression, it will be present in $$$(k-1)$$$-compression. Now for every $$$a_i$$$, we need to compute the greatest $$$k$$$ such that $$$a_i$$$ is present in the $$$k$$$-compression. Suppose that $$$l < i$$$ such that $$$l$$$ is the greatest possible and $$$a_l < a_i$$$. Similarly $$$r > i$$$ such that $$$r$$$ is the least possible and $$$a_r < a_i$$$. In other words, we find the closest two lower elements to the left and to the right. Then $$$a_i$$$ will appear in $$$k$$$-compressions for $$$k \in \{r - l + 1, r - l, r - l, \dots, 1\}$$$. Finding $$$l$$$ and $$$r$$$ can be done by adding indices $$$i$$$ of $$$a_i$$$ in the increasing order of values of $$$a_i$$$. We keep the indices in a set, now we can quickly find greater/lower element.

Now we can iterate through every $$$k$$$-compression by going from $$$n$$$ to $$$1$$$ and add each element, that now appears for the first time. We can easily check if the current $$$k$$$-compression is a permutation by keeping it as a set and checking its size, its minimum element and its maximum element.

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

    can you explain me how use set to get l and r

    thank in advance

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

      Order input elements of the input and make sure you keep its original index. For example keep a vector<pair<int,int>>, where first is the value, second is the original index and sort this.

      Now add indices of values in increasing order to the set. To find the next greater, call upper_bound on the set. To find the next lower, you can keep a second set with reverse order. Calling upper_bound on this one finds the next lower.

      From the way you add items to the set, you know that the index you find belongs to a element with a lower value.

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

I had an alternative $$$O(n)$$$ solution for D that uses the "next smaller" problem (see my submission). It turned out to be an overkill but maybe it's of interest for some :)

Consider our input array $$$A$$$. First observe that for any window size $$$k$$$, an integer $$$i$$$, $$$1 \leq i \leq n$$$, will be in the resulting array if and only if there is some subarray of $$$A$$$ with size $$$\geq k$$$ where $$$i$$$ is the minimum.

Now, we can compute the array $$$B$$$, where $$$B[i]$$$ is the maximum value of $$$k$$$ for which $$$i$$$ will appear in the resulting array. So for the example array $$$A = [1, 3, 3, 3, 2]$$$ the corresponding array $$$B$$$ is $$$B = [5, 4, 3, 0, 0]$$$. We can compute this array in $$$O(n)$$$ time by first pre-computing for every index $$$j$$$, the first index to the left and first index to the right that the number is smaller than $$$A[j]$$$ (if you don't know how to compute those indices, see this article).

Finally, for a particular $$$k$$$, notice that the array resulting from the window-min operation will be a permutation if and only if $$$B[i] \geq k$$$ for every $$$1 \leq i \leq n - k +1$$$. Why? It's clear that if it is not fulfilled, the array will not be a permutation. On the other hand, if the condition holds, we'll clearly have at least one of each integer between $$$1$$$ and $$$n - k + 1$$$. At the same time, our array will have exactly $$$n-k+1$$$ integers, therefore it'll have exactly one of each integer.

Therefore, we can compute prefix "sums" (using min instead of addition) on the array $$$B$$$ which will give us an array $$$C$$$ that allows us to quickly check whether the condition above holds in constant time--we will have: $$$k$$$ will result in a permutation $$$\iff$$$ $$$C[n - k + 1] >= k$$$. In our example, we'll have $$$C = [5, 4, 3, 0, 0]$$$ and checking for the condition will yield us the output $$$00111$$$.

Overall, for each step we required linear time so the time complexity is $$$O(n)$$$.

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

    I was thinking in similar way of maintaining the prev smaller and next smaller and finding the maximum length for which it remains smaller. But couldn't connect dots of how to find solution with it.

    Thanks for the explanation!

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

      yeah, even I am thinking of the same approach I request Monogon to please add this as an alternate solution.

      Thanks for your explanation :)

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

    i also did with the exact same approach

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

    Very nice method. Very well explained. Got interesting things to learn.

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

The moment when you use FFT instead of trivial Vandermonde's identity (https://en.wikipedia.org/wiki/Vandermonde%27s_identity) is the moment you should realize people can be too experienced

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

    How does FFT help compute what we had to compute using vandermonde? I'd love to understand

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

      FFT lets you do the following:

      You are given two sequences: $$$a_0, ..., a_n$$$ and $$$b_0, ..., b_m$$$. Compute sequence $$$c_0, \ldots, c_{n+m}$$$ such that $$$c_i = a_0b_i + a_1b_{i-1} + \ldots + a_{i-1}b_1 + a_ib_0$$$.

      This is exactly what I needed here, where $$$a_i = {n \choose i}$$$ and $$$b_i = {m \choose i}$$$. If I thought for a little longer I would realize that $$$c_i = {n + m \choose i}$$$ instead of computing it using FFT.

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

I had another idea for D. It seems to have passed the tests but correct me if I'm wrong.

What I tried to to do is to find for each value x (1 <= x <= n) what is the maximum value of k so that there exists a segment of length k, where x is a minimum value. Let's call this maximum value k_x.

So for example for this case: 1 ? ? 2 ? ? if x = 2 and ? >= 2 then k_x = 5

Of course it is possible that there is more than 1 number equal to x in the array. In this case k_x is equal to maximum of k_x of all positions where a_i = x.

Calculating k_x for all x can be done with stack.

Then to create answer we do the following:

Let's iterate over x from 1 to n. If x was not present in array we break the loop. Otherwise let's calculate what k must be equal to if we want to create permutation from 1 to x. It is equal n - x + 1. Then let's calculate what is the greatest value of k that can be used. It is equal to min(k_j) where 1 <= j <= x. So if min(k_j) >= n - x + 1 then answer is 1 else it is 0.

Here is my code

Edit: Someone had already wrote about this approach while I was writing this comment. You can refer to this link to see it

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

To those who don't know anything about sparse table or segment tree yet and wanted to solve D, My approach:

A set of observations to start with:

0) Kth compression array is 2nd compression of K-1th array. Try proving this by taking some sample cases :)

1) We find the lowest number which has been repeated in the array. To do this, just sort the array and check whether a[i]==i for 1<=i<=n. If its not, break at that i. Benefit: the integers above this can never form a permutation, since this number is duplicate and smaller than them. Store 0's in the answer string

2)If we have an integer a[i] such a[i-1] > a[i] and a[i] < a[i+1], it will make a duplicate of itself when we compress it, so we need to find the smallest integer and above that integer, any array wont be a permutation since it would have duplicates. Store 0's in answer string upto this integer.

3) Now we have an array left which has a[i]=i for 1<=i<=n and the array is free of an a[i] such that a[i-1]> a[i] and a[i]<a[i+1]. The number of elements left in the array is the number of 1's you would have in your answer string.

  • Also do check that if the array is free of duplicates at the start, the first compression array wd be a permutation regardless of the 2nd observation.

Feel free to check my code as well here

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

So many alternate ideas to D in the last few comments

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

Can somebody please explain the editorial version of problem D

for the test case n = 3, array = [2,2,1] as per my interpretation: 1-compression is [2,2,1] -- not happy , 2-compression is [2,1] -- happy, 3-compression is [1] — happy.

But as per editorial we will fix l = 1,r = 3 initially and we iterate over i = 1,2,3:

so for i = 1 , as arr[3] is 1 ,so we decrement r to 2 and min(a[1],a[2]) is 2 which is i+1

and next for i = 2 ,as arr[1] is 2 , so we increment l to 2 but min(a[2]) which is 2 != i+1 , so we are failing at this i,

so as per editorial k>2 are happy and rest are unhappy, but we know 2 compression is happy , did I misunderstood somewhere please help me out

Thanks in advance :)

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

    I did the same thing using two pointers — $$$O(n)$$$.

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

      thanks for your editorial. your code is self explanatory.

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

Thanks for superfast editorial, but Too difficult contest :(

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
why this code is giving wrong ans for D

its same as explained in editorial

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

Too difficult contest.I spend lot of time on c1. But it's solution is very nice :).

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

I expected some text art in some of the test cases in either C1 or C2. Alas!

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

In problem D, wasn't sample output were big hint . In my case i got hint that except for k=1 , sequence for 1 will be contiguous .Thus i separately solved for k=1 and did binary search for rest and it got accepted .

In codeforces i find that many times sample's give a lot of hint compared to CodeChef short contests . That's why accuracy of most people on CodeChef is less compared to CF.

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

    Can u explain binary search approch

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

      Just check for k=1 separately . Then you can do binary search from k=2 till k=n . For checking a particular k , you can do what is told in the question . You can find range minimum using segment tree .Complexity will be nlog(n)log(n) . You can prove why it works on lines similar to the editorial .

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

    Interestingly enough, it gets TL if you use multiset to squeeze the array inside binary search

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

      Yeah this is because of high constant factor in multiset,set and map. Segment tree i guess is faster, the only overhead is function calls.

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

I solved D using Binary Search.

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

    Can u explain

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

      Main observation is that if for a particular K we are able to find a permutation, then for all K+1 to N there always exists a permutation. So for finding a K we can apply Binary search.

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

Thanks for the good competition. In problems C1 & C2, I did not understand how (i+j)%3 is obtained. Why does this give us solution? Can anyone elaborate on this?

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

For C, what if the direction of the color diagonals are to the other way? So it goes from top left to bottom right, shouldn't there be a check for that case as well?

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

    Either way will work, the proof is the same.

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

I am not able to solve C1 and spend lot of time but after seeing editorial approach looks very nice..

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

Can someone provide an example for which greedy in C1 fails. Greedy being swapping 'X' which is contained in most triples of 'X' with 'O' until there are no more triples of 'X'?100579257 this is how I tried to solve the problem.

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

I hate constructive algorithms

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

    Thanks for the constructive feedback

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

.

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

    Bro, did you find out your flaw. Actually I was trying but couldn't find out a testcase which you were missing. But I am pretty much sure that your code fails on the case where we can't take the same coloring for both of X's and O's..

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

      Yeah, I found a case in which I was changing more than k/3 tokens.

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

        Can you give that case.

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

          Yeah sure...

          6
            OO.XX.
            ...OXO
            X..X..
            XOOOXX
            X.XX.O
            ....XO
          

          Output:

          OX.XX.
          ...XOO
          O..O..
          XXOOXO
          X.XX.O
          ....XX
          

          There are 8 changed tokens but allowed are only (21/3) = 7

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

can someone explain problem D

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

    There are editorials from the author and also from other participants' comments. Try to read them.

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

I solved D using binary search. Take k=1 as special case and binary search from 2 to n. Anyone else did this? It passed but is it a correct solution ?

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

For problem D, if the check fails on index i, then shouldn't the answer be 1 for n-i+1 <= k <= n ? Consider 1 5 3 4 2. Check fails for i=3 and k=3 gives a permutation.

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

Thank You Monogon for such a nice contest, really loved the problems

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

Errichto did't intimidate Monogon from taking his top contributor spot on Codeforces!

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

Even though I didn't do well in this contest, I'd like to say that the problems were of great quality.

Kudos to all the authors!

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

lbyyds

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

.

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

Refer to the solution of F The struggling contestant by 1-gon it's quite a observation that many programmers and computer scientist tend to use Mathematical induction as a proving technique in lots of problems . It's quite a jugglery of the mathematical induction to prove the existence of such a solution !

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

Hello! I found this testcase of problem F

1
13
1 1 3 1 1 2 3 2 3 2 3 1 1

The correct answer is 6, but i can't get how to reach it. Can anybody help?

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

    Cut like this:

    1 - 131 - 12 - 3 - 2 - 3231 - 1
    

    Then rearrange to:

    1 - 21 - 3 - 131 - 2 - 1 - 3231
    
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't understand the tutorial for E. I thought if there's a cycle with positive weight also give a contradiction. For ex :

u1 -> u2 -> .. -> uk -> u1

Suppose each edge in cylce above is 1, then the weight of this cycle is positive. In other words, i can say : u1 > u2 > ... uk > u1 (?)

I think any cycle that exist must be 0-weight. Can anybody explain what was wrong with me T.T

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

    Since it is a bipartie graph, the cycle has an even length.

    If all edge are given directed as a cycle, there will be a negative cycle(all with weight -1).

    Otherwise, you can direct them in an alternating way, so $$$w_2 = w_1 + 1, w_3 = w_2 - 1 = w_1, \dots$$$. So there are no contradictions.

    UPD: If the sum of the cycle is positive, you can direct some undirected edges so that the sum is $$$0$$$.

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

      Thanks you! I got it. But "The property of shortest paths tell us..." what's the property which author referred to? (if you see me too weak to understand E, pls tell me and i will skip this :D)

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

1-gon Same problem as C1 in Hackerearth Contest 2 days back. Link

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

    Maybe it has similar ideas, but it's certainly not the same problem.

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

it's too hard to wait for 12 days without a contest :(

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

Can anyone explain why, in 1450H1, the final equation has a factor of 1/(2^F) instead of 1/2? I would suppose that since each appropriate parity subset of F is a bijection to a valid colouring with f(c) = 1/2 * |x-{size of subset}|, the constant factor is 1/2.

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

    There are $$$2^{F - 1}$$$ colorings.

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

      Thanks, took me too long. For the others:

      There are a total of $$$2^{F-1}$$$ possible colourings, since the last colour is fixed by the rest to maintain parity. We want the expectation / average, so that's why we multiply by $$$\frac{1}{2^{F-1}}$$$

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

How to approach this slightly modified problem b,

Instead of attracting all the balls (in the original problem) what if we can deselect any number of balls to attract in any operation.

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

    That was exactly the question I was solving needlessly and wasted around 1.5 hrs

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

    The answer would be the same, right, how will be different?

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

Can anyone help how does one get the idea of (i+j)%3 for the problems C1, C2?

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

    Working on small dense examples by hand, you might come across this pattern of every third diagonal.

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

I took a different approach to problem E.

I start by assigning a $$$a_{src}=0$$$ to a "source" node. According to this, all remaining nodes $$$i$$$ are associated with a set of possible values for $$$a_i$$$. For example, consider the example of the following graph:

4 3
1 2 0
2 3 0
3 4 1

Taking node 1 as the source, the set of possible values of $$$a$$$ associated with node 1 = {$$$0$$$}, node 2 = {$$$-1,1$$$}, node 3 = {$$$-2,0,2$$$}, node 4 = {$$$-1,1,3$$$}.

In fact, I can prove (using induction) that all such sets will be either continuous odd numbers or continuous even numbers. So, I can conveniently represent them as a pair $$$[i,j]$$$ denoting the range of the associated set {$$$i,i+2,i+4,...,j$$$}, which are stored in the vector $$$range$$$.

Now I start a dfs at the source, for an edge between nodes $$$u$$$ and $$$v$$$, set:

  1. $$$range[v]=[range[u].first-1, range[u].second+1]$$$ if the edge is undirected
  2. $$$range[v]=[range[u].first+1, range[v].second+1]$$$ if the edge is directed from $$$u$$$ to $$$v$$$
  3. $$$range[v]=[range[u].first-1, range[v].second-1]$$$ if the edge is directed from $$$v$$$ to $$$u$$$

If there is already some value of $$$range$$$ associated with $$$v$$$, take the intersection of the new value with the original value. If this intersection is $$$\phi$$$, the society cannot be capitalist. If the intersection is not the same as the original value, update $$$range[v]$$$ and call dfs on $$$v$$$, since the $$$range$$$ of other nodes may also need updating.

Repeating this process by keeping each node as the source iteratively, there will be at least one such source which gives the maximum income inequality as $$$\max\limits_{1 \leq i \leq n} (range[i].second)$$$. In such a case, setting $$$a_i=range[i].second$$$ for all $$$i$$$ gives a valid construction of the answer.

My submission: 100720392

EDIT: I have now concluded that the complexity of dfs is $$$O(nm)$$$.

For any node, the maximum range that can be assigned to it is $$$[-n,n]$$$. Every single time this range is updated, it must decrease by at least 2, since we always take the intersection of the original range and new range. Thus, each node can be updated at most $$$O(n)$$$ times.

Furthermore, every single time we update a node, we iterate over all its adjacent edges. If the degree of a node is $$$d_u$$$, the dfs will perform at most $$$n*d_u$$$ steps for node $$$u$$$. Summing over all nodes, $$$\sum n*d_u = 2nm = O(nm)$$$.

Thus, the solution runs in overall $$$O(n^2m)$$$ time which is just enough (for me, a privileged C++ user) to pass the time limits. But if you disagree, please feel free to hack the solution if you can. :P

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

    The ranges have size $$$O(n)$$$ and shrink every time dfs is called on it. An edge is processed every time one of its endpoints has a dfs call. This way, every edge is processed $$$O(n)$$$ times, so it seems your complexity guess is correct.

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

      Yes!! Thank you!

      Sorry, it seems I was in the middle of editing my comment just as you posted this one (xD). Thanks a ton though!

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

Nice Problem C!

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

In the non-optimized ver. of problem G, how did 3^C come out? Had trouble with bitmasks complexities.

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

    For each bitmask, you iterate over only its submasks, not all masks. For each position, (mask, submask) has 3 possibilities: (0, 0), (1, 0), and (1, 1). Therefore the are 3^C bitmask-submask pairs.

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

Also I would like to ask about the memory limit of G which is unusual, what kind of solutions did the author want to block?

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

    There is a solution with subset sum convolution that doesn't use the observation about overlapping ranges.

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

For problem B(Balls of Steel) how the answer can only be 1 and -1. Could any one please explain this to me.

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

    I proved my claim in the editorial. Basically you assume for contradiction that there is a solution with 2 or more moves, and show that it's impossible.