Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

vovuh's blog

By vovuh, history, 4 weeks ago, In English,

Thanks to Rox and _overrated_ for help with problem ideas and preparation!

1294A - Collecting Coins

Idea: MikeMirzayanov

Tutorial
Solution

1294B - Collecting Packages

Idea: MikeMirzayanov

Tutorial
Solution

1294C - Product of Three Numbers

Idea: MikeMirzayanov

Tutorial
Solution

1294D - MEX maximizing

Idea: Vovuh

Tutorial
Solution

1294E - Obtain a Permutation

Idea: Vovuh

Tutorial
Solution

1294F - Three Paths on a Tree

Idea: MikeMirzayanov

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

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

An even simpler solution to A; first check that a+b+c+n is divisible by 3, then check that (a+b+c+n)/3 is no less than a, b, and c.

def main():
    def solve():

        a, b, c, n = map(int, input().split())
        if (a + b + c + n) % 3 != 0:
            print("NO")
        else:
            m = (a + b + c + n)//3
            if m < a or m < b or m < c:
                print("NO")
            else:
                print("YES")

    q = int(input())
    for _ in range(q):
        solve()


if __name__ == "__main__":
    main()
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the reason behind this, if m < a or m < b or m < c?

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

      You cant give negative coins to make the equality condition.

      A + a = B + b = C + c = m
      so m - a >= 0 && m - b >= 0 && m - c >= 0
      this must hold otherwise the answer is NO. 
      
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      m represents the total coins that person would get at the end of the entire transaction.Since we are only adding coins and not removing coins from any person the final sum present with each of them should be greater or equal to the initial amount of coins

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

      because if A + a = B + b = C + c ,then 3 | (A + B + C + n),m = (a + b + c + n)/3,So m is what happens when they finish n(sorry,my English is so bad)

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

    man me too thought the same algo for this problem.

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

    Your solution seems to be correct...By mistake I downvoted it and now can't change it to upvote...Sorry for that

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

Here is a typo in explanation of problem E, answer for each column is "min(n — cnt[i] + i)"

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

rohit_varma**Can someone tell me the validity of solution approach of problem C given in editorial ,I want to know the intuition behind how this approach is leading us to the correct solution?**

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

    Instead of three distinct number you can consider two number a and d(b.c) where a is the least factor of n and d(b.c) is another or greatest factor of n. Then try breaking d into b and c such that a, b and c are not equal. For example 24. Smallest factor is a=2 and another factor is d=12. Further break d into it's own factor b=3 and c=4 such that they are not equal.

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

    Although my approach is a bit slower than editorial's, it is very intuitive. Find all distinct factors of N other than 1 and N. This can be done in O(sqrt(N)). Sort these factors. Run two nested loops over the factors. Outer loop picks the value for A. Now we have to find two distinct factors of N / A. Since the factors are sorted, we can use a two pointer approach and find it in one iteration of the inner loop. The idea is something like this: Let L = 0, R = size of factors array — 1. Repeat while L < R: If factors[L] * factors[R] < N / A, increment L. If factors[L] * factors[R] > N / A, decrement R. If factors[L] * factors[R] == N / A, we have found our answer. Make sure to not use the same factor that was picked by the outer loop.

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

Anyone give me the intuition that how to solve E.

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

    I also want to know how to solve E.

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

    I think this problem is the most difficult one of all the six problems.

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

    First you have to see that for each column minimum operation have to be calculated now for each column you have to see how much circular rotation is needed for each element in the column now u have the count of each type of cyclic rotation some elements need 1 rotations some 2 etc.. now using this data we can say that n — (count of ith rotation) + i is needed to set the column calculate minimum of this now add minimums of all column

    Sry i am bad in explanation

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

    Lets just take a look at only one column. We can rotate the column or modify one elememnt per move.

    We should admit that these moves are REVERSIBLE, so it's the same problem as: "We need to rotate the disordered column and THEN modify its element to get the standard column". So we create an array Moves[N] (means if we firstly rotate the column i times, and the total moves we need to get the standard column is Moves[i] , Moves[i] is initally assigned n + i since we suppose that every elements need to be modified), but some elements (for example: element "x") don't need modify IF (x is in the standard column). Thus we need to do Moves[the right the rotating times]--; And the answer for this column is min{Moves[i] (0 <= i < n) } The final result is the sum of each column's answer.

    Hope i could help you. qwq.

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

    For E you can divide it into subproblems 1. Solve Each column as an independent entity 2. How to solve? 3. Notice columns are in form of m*i+(j+1), here 0<=i<=n-1, jth column number , remove (j+1) all column are in same form. 4. Each column- Now make a dictionary to count number of elements in that rotation(how far that element is from it's actual position) (you can see in this solution 69363795 ) and first check element is valid or not. now run through the dictionary (d[x]=y) ans = min(x+(n-d[x]), ans) (ans = n initially)

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

    Maybe I am too late to answer, the obvious observation is all columns are independent. Now, to solve each column, you need to find a rotation, which sets most of the numbers at their position and rest will be fixed by modifying. How do we get our best move ? We may have best number for rotations from 0 to n-1, where n is the number of elements in that column. We run a loop from 0 to n-1, and calculate the element required at ith position, in column. Now we need to know, where is this element in original column, and hence the required number of rotation. We store these required number of rotations by each element. Now, if there is a rotation value 2, which appears 3 times, that means, by rotating 2 times, we will get three elements at their position. So if a rotation x appears y times, that means x moves will fix y elements at their position, and we will need n-y moves to fix rest of elements. We need the minimum value for this. That query for original positions of values can be done by storing original values and their positions in a multimap.

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

      well explained. Thanks, But how would you account for duplicates values in the same column, which position would you consider.

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

        Aren't all numbers in the matrix unique ?

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

        We will consider all the duplicates, that's why I mentioned a multimap.

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

Wow, test cases on F is very tight.

Anyway, I'm very impressed by Mike's sol. It's neater than DP

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

In problem D I dont understand this

"Firstly, let's understand what the operation does. It changes the element but holds the remainder modulo x. So we can consider all elements modulo x."

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

    Suppose you're having a number 'A' and whose modulo by another number x be 'Ra'. So if you increase or decrease the number 'A' by 'x' the modulus will remain unchanged. Although the resulting number (A (-/+) x) will change but modulus of this with x will not!!!

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

    In case 1: x = 3 then: if ($$$cnt_0 == k$$$) ($$$cnt_0$$$ declared above) you can take the elements in this $$$set = {0,3,6,9,12,...}$$$ by increasing x or decreasing x. if ($$$cnt_1 == k$$$) you can take the elements in this $$$set = {1,4,7,10,13,...}$$$ by increasing x or decreasing x. if ($$$cnt_2 == k$$$) you can take the elements in this $$$set = {2,5,8,11,14,...}$$$ by increasing x or decreasing x. Suppose $$$y = min(cnt_0 = 5,cnt_1 = 3,cnt_2 = 4)$$$ Obveriously $$$cnt_1 = 3$$$ is the least. then $$$set_0 = {0,3,6,9,12}$$$ $$$set_1 = {1,4,7}$$$ $$$set_2 = {2,5,8,11}$$$ $$$mex(set_0 \cup set_1 \cup set_2) = ((x = 3) \times (cnt_1 = 3) + 1) = 10$$$ So the answer is 10. So at the begining you can consider all elements modulo x.Because this operation has no effect on the final answer Sorry for my bad English

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

      if using your formula minimum value of MEX is 1,because whatever value of x multiple cnt,in the end of it you always add 1.

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

        In my method,we get the answer 10.$$$set = (set_0 \cup set_1 \cup set_2) = {0,1,2,3,4,5,6,7,8,9,11,12}$$$.$$$mex(set) = 10$$$ is the biggest answer that we can get. $$$1 = 3 * 0 + 1,4 = 3 * 1 + 1,7 = 3 * 1 + 1,10 = 3 * 3 + 1..$$$.This method just generates this sequence.1 is the element a_i mod x in this sequence.1 mod 3 = 1,4 mod 3 = 1,7 mod 3 = 1...

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

Sorry, but where in problem D does it say that we can do infinite and more than Q moves on each iteration?

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

An easier to understand approach for`those who are not getting the formula mentioned a #include <bits/stdc++.h> using namespace std;

typedef long long ll; typedef unsigned long long ull; typedef long double ld;

define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int main() { fast ll t; cin >> t; while (t--) { fast ll a, b, c, n; cin >> a >> b >> c >> n;

ll maxi = max(a, max(b, c));

    a = maxi - a;
    b = maxi - b;
    c = maxi - c;

    n = n - (a + b + c);

    if (n < 0 || n % 3 != 0)
    {
        cout << "NO"
             << "\n";
    }
    else
    {
        cout << "YES"
             << "\n";
    }
}

return 0;

} `

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

Can anyone please explain D in a better manner?

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

    In one move you can choose any element $$$a_i$$$ and change it to $$$a_i:=a_i+x$$$ or $$$a_i:=a_i−x$$$ any number of times only with the condition that $$$a_i$$$ never becomes negative. If you have an element of the form $$$kx + c$$$ in which $$$0 \leq c < x$$$, it could change to $$$c, x + c, 2x + c ... (k-1)x + c, kx + c, (k+1)x + c$$$ and so on. For example, if you have $$$0$$$ as an element, then, it can stay at $$$0$$$ or change to $$$x, 2x, 3x$$$ and so on. As a consequence, in this particular case, all the numbers $$$a_i \equiv 0 (mod x)$$$ can take the place of any of them. In general, if $$$a_i \equiv b (mod x)$$$, you can change that $$$a_i$$$ to any number that has the same remainder $$$b$$$ after dividing it by $$$x$$$. So your $$$mex$$$ start with the number $$$0$$$ because the first number you need. Then, on each query you are going to add on an array one more element with the remainder that the number of that query has. Let's suppose you are still in $$$0$$$ and you read a number whose remainder is $$$0$$$, you decrement the frequency in your array with index $$$0$$$ by one and while your $$$mex$$$ can increase, you repeat that before going to the next query because you can have many numbers with remainder $$$1$$$, $$$2$$$, even until

    $$$x-1$$$

    that can increase the $$$mex$$$. The time complexity is $$$O(n)$$$ because there will be at most $$$n$$$ times in which you could substract one to the frequency of a remainder in the array.
  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    When we are doing modulo of each input and storing there cnt . It mean we can generate number till the min(cnt0,cnt1,…,cntx−1)*x.

    Example: suppose x is 4

    and cnt[0]=3,cnt[1]=2,cnt[2]=3,cnt[3]=3

    0 1 2 3

    0 1 2 3 ( we can add x=4*1 to each and we can generate next four number) [ 4,5,6,7]

    0 . 2 3 ( here we can add x=4*2 to each and we can get = [ 8,-,10,11]

    so MEX is 9

    So our ans should be the min( of all count )*x + we can go to the next row and can pick all those which are before the (y = min(of all cnt) )

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

Can anyone explain Problem D. I can't get it

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

For Problem F:

How to prove that 2 endpoints of a diameter will result an optimal answer ?

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

    You can check that the optimal answer always goes through the midpoint of diameter

    Update: What I am writing is serious! Not for joking

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

    proof by contradiction .Suppose take any three paths not involving the diameter .Then take the diameter and connect one of the vertices of diameter with vertex on three paths and take one of the branch .Since the branch left has length shorter than the diameter hence contradiction .

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

I have a somewhat different approach to F. We store the maximum , second maximum and 3d maximum for all subtrees. This can be easily done using dfs. Then we loop for all nodes. Answer is either m1 + m2 + m3 or m1 + m2 + max(some m2 in the subtree of the node). All this info can be maintained in a single dfs. https://codeforces.com/contest/1294/submission/69415213 If anyone is further interested in the approach, I would be happy to elucidate it further.

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

    Hi can you please explain what maximum here means? maximum distance node in each subtree?

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

      Yes, the maximum distance node from the current node considering only the current node's subtree. Same goes for second and third maximums.

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

Who knows where to read about multi-source bfs?

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

    Link : This isn't too detailed, but you get the gist.

    It would also be interesting to see that we can also do multi-source shortest path using Djikstra's, for which I have a gfg link : Link

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

What is the DP approach for F?

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

    just like dp finding diameter of tree

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

    https://codeforces.com/contest/1294/submission/69449118 You can view my code.

    dp[i]->the i-th vertex is the root,and choose the vertex as a/b/c,another two is under the i-th vertex.

    dp[i]

    =max(

    dp[j]+1 there is a path between the i-th vertex and the j-th vertex ,

    the biggest two deep[j] + 2 deep[j] is the number of paths between j and i

    )

    You can change the i-th vertex to its kids,and update the value in O(1)!

    Total complete in O(n).

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

Probably overkill for C, but a randomized solution over divisors works and is really easy to code. The sieve in my solution is unnecessary (but can help if n was bounded above by say, 1e7).

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

why is there a stress on finding the third vertex c in F when we already know the edges in a diameter will already contain the maximum number of edges as asked??

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

    because you have to find maximum no. of unique edges between a-b, b-c, and c-a. so, if your diameter have n-1 edges then you can pick any vertex, but if less than n-1 then you have to find 3rd vertex in order to make unique edges maximum.

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

Can somebody explain why my solution to problem D( MEX maximizing) is getting TLE'd Submission Link

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

    Can you explain what you are trying to do? It's looking too complicated, have a look at this http://codeforces.com/contest/1294/submission/69410745

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

      My approach is as follows:- My current mex is mx and it is the first element in map with value 0.for all 0<=i<mx value in map is 1. now if yj entered is greater than mx then I am trying to cover up the value just greater than mx whose value in map is 0. Similarly for the case when mx > yj. if mx = yj then finding the next uncovered value in map and updating mx.

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

        I am not sure but I think this -> while(mp[key]) key++; is responsible for TLE, if the key is not present, it will be dynamically allocated and if it is present it will take O(log(n)) time. Try to get rid of the map.

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

In problem F Why always take diameter?

»
4 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

include<bits/stdc++.h>

using namespace std; int main() { long long int t,a,b,c,n; long long int l,s,m,x,d;

cin>>t;
while(t--){
    cin>>a>>b>>c>>n;
    l=max(a,max(b,c)); /// large
    s=min(a,min(b,c)); ///small
    m=(a+b+c)-(l+s);  /// middle
    d=(l-s)+(l-m);   

    if((n-d)%3==0 && d<=n) 
       cout<<"YES\n";
    else cout<<"NO\n";

}

return 0;

}

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

Seen lot of solutions up here for "A" . Well I think I did the better implementation (no sort needed just the max).

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,a,b,c;
        cin>>a>>b>>c>>n;
        ll m=max(max(a,b),c);
        ll dif=m-a + m-b + m-c;   // one of them will results in zero ,you know that
        n-=dif;
        if(n>=0 && n%3==0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
  return 0;
 }

And "E" was a good greedy question I must say :)

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

I have used the same approach as the editorial. Why am i getting WA on E. link to my solution. Thank you for your efforts

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

In problem E Can anyone tell me why this is true, I'm not able to understand?

" if ai,j%m≠j (% is modulo operation) then there is no such cyclic shift."

Thank you!

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

    Means that particualr aij value does not fit in the jth that column, aij value must be change in that case

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

    It is because all numbers in the j-th column must have j as a reminder when divided by m. It's clear to see why this is true looking at the image in the problem. So, numbers that don't have this property don't belong to the j-th column, therefore there's no cyclic shift that will put them in place because they don't belong to that column.

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

    Draw a 3x3 matrix : { {1,2,3} , {4,5,6} , {7,8,9} } ; add (-1) with all elements ; mod all elements by column_number ; thus see for yourself

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

My submition is of O(sqrt(n)) single loop only https://codeforces.com/contest/1294/submission/69338578

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

Can someone elaborate bit more on "Then we need at least 2c−b−a coins to make a, b and c equal." ?

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

    Let C be the largest coin , so we need to add c-b coins to make b=c and c-a to make a = c. hence in total we need c-a + (c-b)

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

69433414 for part A ,my code was running fine on IDE but didn't work on codeforces . Can someone suggest me some correction?

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

    For dist == n, your code is printing YES two times

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

    I guess you missed else on 20th line Your code printing twice

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

[DELETED]

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

what is the "obvious dynamic programming solution" for problem F?

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

    Oh, I got it. You just have to root the tree and for each node check if this node is the node with degree = 3 in the answer. (in case that the tree has no node with degree >= 3 we can just print two nodes with degree 1 and another arbitrary node).
    For each node u with degree >= 3 we will maximize between the two following cases :
    1- sum of the maximum length of a path to a leaf passing through 3 different children of u starting from u (if has at least 3 children)
    2- sum of the maximum length of a path to a leaf passing through 2 different children of u starting from u and the maximum length of a path going to a leaf from parent of u starting from u (if u has parent)
    Of course we need to maintain the leaves that give us optimal answer.

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

How to approach E if you could shift the columns downwards also ?

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

    This is a good question.

    What we are doing at the moment is calculating the cost for all $$$n$$$ rotations.

    I think we would do the same thing except that we would calculate the cost for all $$$2n$$$ rotations.

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

Promble F:

Help! Can anyone prove why we should get the diameter first? Why we will get the best answer in this way?

I can't prove it.

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

    We can try an exchange argument.

    Suppose we have chosen 2 nodes $$$u, v$$$. If $$$u, v$$$ lie on the diameter, then we can extend $$$u, v$$$ to the diameter ends and get a larger answer.

    If $$$u, v$$$ do not lie on the diameter, then we can get a bigger answer by choosing the diameter. (Since the definition of the diameter is the two nodes who are furthest apart.)

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

      For 2 nodes it's pretty obvious, How did you prove it for 3 nodes ?

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I very nice contest. The problems were very Mathematical and interesting.

Here are my solutions

  • $$$A$$$ — Simple observation
  • $$$B$$$ — Greedy $$$+$$$ Sorting
  • $$$C$$$ — Prime Factorisation $$$+$$$ Observation $$$+$$$ Case Analysis
  • $$$D$$$ — Invariant $$$+$$$ Greedy
  • $$$E$$$ — Treat each column independently. For a column, find the cost of each of the $$$n$$$ possible rotations and choose the best rotation.
  • $$$F$$$ — Find the diameter of the tree using $$$2$$$ DFS. Then, do multi-source BFS from every vertex on the diameter and find out the furthest vertex from the diameter.
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the useful editorial and new codeforces problems

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

    Could you explain your approach or intuition behind your solution too?

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

      Let $$$MEX$$$ the current MEX. If $$$y_{i} = MEX$$$ then the $$$MEX$$$ increases by one, if it is smaller or larger, then can we use it to improve our $$$MEX$$$ soon, how do we do this?
      Let $$$D$$$ be an unused $$$y_{i}$$$, if $$$MEX \equiv D \pmod{x}$$$ then we can use $$$D$$$ to improve $$$MEX$$$. The numbers we use are not going to be changed in a future query because if we do this our $$$MEX$$$ would go down since the smaller number not used would be less than the $$$MEX$$$

      So in each query we try to improve the $$$MEX$$$ as much as possible. For this we have an $$$ST$$$ array of size $$$x - 1$$$, so that $$$ST_{i}$$$ is the number of times we have the unused element $$$i$$$.

      Sorry for my English (Google Translator). XDXDXD

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

My approach in c :

First let's analyze the problem. We have to find out if n can be expressed as a multiple of 3 distinct values. Suppose we have a number with prime factorization of n = 2^2 * 3^3 * 5^1. Now if you distribute the prime factors into three numbers (for example a = 2 * 3^2, b = 3, c = 2*5, Here no new power of any factor has been created but we have just distributed the existing powers), without knowing anything else we can say a*b*c = n. So this problem can be translated to, "can we distribute the prime factors of n into a,b,c such that a!=b!=c."

Solution plan: Suppose given number is n = 2^2 * 3^3 * 5. We will select a = 2 (shortest prime factor), b = 3 (second shortest prime factor) and c = n / (a*b). (all the rest prime factors). (Thus we don't actually need the powers of all prime factors rather all the distinct prime factors).

Algorithm:

1. Find out NUM = distinct prime factors of n. Store them in a vector V.

2. if(NUM == 0) n is prime, ans is no.

3. if(NUM == 1) a = V[0], b = V[0]*V[0], c = n / (a*b). if(a*b*c == n && a!=b && b!=c && c!=a && c > 1) ans is yes. print a,b,c.

4. if(NUM == 2) a = V[0], b = V[1], c = n / (a*b). again check the same condition as 3.

5. if(NUM >= 3) a = V[0], b = V[1], c = n / (a*b). print a,b,c.

When NUM >= 3 there always exists an answer because there are already at least 3 distinct prime factor.

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

can someone please explain me , problem d?

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

In problem F, we can use dfs instead of multi-source bfs.

Let $$$u$$$ and $$$v$$$ be the endpoints of a diameter. Then, it's always optimal to take vertex $$$w$$$ which $$$dist(u, w)+dist(v, w)$$$ is maximal as the third vertex ($$$dist(x, y)$$$ is distance between $$$x$$$ and $$$y$$$).
Let $$$r$$$ be the intersection of $$$w$$$ and the diameter. Then, the answer can be expressed as follows: $$$dist(u, v)+dist(r, w)=dist(u, v)+\frac{dist(u, w)+dist(v, w)-dist(u, v)}{2}=\frac{dist(u, v)+dist(u, w)+dist(v, w)}{2}$$$
Since $$$dist(u, v)$$$ is the diameter, we should maximize $$$dist(u, w)+dist(v, w)$$$.

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

Anyone can offer a DP solution for problem F? Thanks!

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

I don't know how to get the conclusion of C question solution? In particular, the meaning of the first two cycles is not very clear. And why "no" is output when used.size() < 2.

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

Let's take a moment to appreciate the elegance of the rounds prepared by vovuh.

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

in Question 1 why condition 2c-b-a exist? I mean why 2 multiplied by c and the 3 elements need to be sorted?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it
    I'll tell you a simple solution, which might give you an intuition
    $$$a + A = k$$$ (some value)
    $$$b + B = k$$$
    $$$c + C = k$$$
    add all these three equations
    $$$a+b+c+(A+B+C)= 3*k$$$
    $$$a+b+c+n= 3*k$$$
    $$$\frac{(a+b+c+n)}{3}= k$$$
    So check if $$$(a+b+c+n)$$$ is divisible by $$$3$$$
    now $$$k= \frac{(a+b+c+n)}{3}$$$ and since
    $$$a + A = k$$$ this implies $$$k-a=A$$$
    $$$b + B = k$$$ this implies $$$k-b=B$$$
    $$$c + C = k$$$ this implies $$$k-c=C$$$
    Since the above 3 should be +ve, check if $$$k > max(a,b,c)$$$
    So effectively check 2 things
    1. if $$$(a+b+c+n)$$$ is divisible by $$$3$$$
    3. if $$$\frac{(a+b+c+n)}{3} > max(a,b,c)$$$
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why are we taking the remainder that has the smallest count?

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

69553041 (Problem -E) Can someone please tell me whats wrong in this solution... I am getting wrong ans on test case 62

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

For Problem B, Can someone tell me how to take a Hashset, or List or anything with <Integer,Integer> and sort it in java? Thank You.

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

Can someone explain div 1 C. I don't understand editorial after third paragraph :(

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

Submission : https://codeforces.com/contest/1294/submission/69645922

My Approach: I am just trying the brute force approach by taking maximum distance separated nodes from any one of the leaf nodes.

Then, I am finding all the vertices between both the maximum separated vertices. After that, I am finding the node which is farthest from any of the middle vertexes that are not in the path of our pre-chosen 2 vertices.

Can anyone help me figure out why I am going wrong?

Thank you :)

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

How to do F with DP?

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

If someone looks for linear solution of D here it is https://ideone.com/nJhASn

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

Could someone help me understand the intuition of why (i−pos+n)%n gives the number of cyclic shifts on problem E

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

what is the dp approach for problem F?

thanks in advance.

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

Can someone clarify in problem F, choosing diameter is part of a optimal solution. Thanks in advance.

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

In the Question E,it should be clearly mentioned that those operations are separate.It created a confusion because it was written "one move" as : In one move, you can: __ choose any element of the matrix and change its value to any integer between 1 and n⋅m, inclusive; take any column and shift it one cell up cyclically (see the example of such cyclic shift below). It seemed as if we Change any element of matrix then its necessary to do cyclic shift.

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

ans += string(r, 'R'); ans += string(u, 'U');

please explain lone of code.

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In Editorial for C, why do we take the lowest factor of number (or why not we consider all the factors of number)?