n0sk1ll's blog

By n0sk1ll, history, 5 weeks ago, In English

1689A - Lex String

Author: wxhtzdy

Hint
Solution
C++ Code

1689B - Mystic Permutation

Author: n0sk1ll

Hint 1
Hint 2
Solution
C++ Code (Main solution)
C++ Code (O(n) solution)

Riblji_Keksic found the O(n) solution.

1689C - Infected Tree

Author: n0sk1ll

Hint 1
Hint 2
Solution
C++ Code

1689D - Lena and Matrix

Author: n0sk1ll

Hint
Solution
C++ Code

1689E - ANDfinity

Author: wxhtzdy

Stupid Hint
Hint 1
Hint 2
Hint 3
Solution
C++ Code
 
 
 
 
  • Vote: I like it
  • +128
  • Vote: I do not like it

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

Very fast editorial. Problems were good also.

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

    Problem were really good, thanks [user:n0sk1||] and wxhtzdy and all the contributors of the contest. I was really a good contest for me.

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

I was not even able to solve A :(

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

Why DP in C? It's just overcomplication, isnt it?

UPD: Idk, i just... Bruh

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

    what's your approach?

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

      You can check out my solution https://codeforces.com/contest/1689/submission/160137279 . The idea is that we can make infection infect only one vertex at a time, or non at all, If vertex has two children, we delete one of them and make infection spread on the other child, so both child dies, this process continues unless one of their child has only one child so infection can not spread anymore, then you just cut one source and infection can not spread at all.

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

        What is the use of variable 'dis' in your code and why are you returning (dis+1) at some places, (dis+2) at other places, and just (dis) at some other places?
        Can you please explain a bit?

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

          It denotes amount vertex that dies, so if vertex has two child, both of them dies, so i do dis+2, if it only has one, only one dies, if it has none, then none dies and i just return dis.

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

      You can just simply use recursion. My solution: https://codeforces.com/contest/1689/submission/160139911

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

    ig we can just store subtree count of every node & later add by processing in valid manner

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

      yep, but is that not already considered dp?

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

    we can solve c without dp.the approch is simply follow along the infected path along the binary tree using dfs/bfs,take minimum of the available infected paths and saved =(n-(infected)) my solution approch

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

      Can anyone see why WA. 3rd Problem I'm storing the child counts in visited and then moving optimally along less children. 160139740

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

        you counter a case when the children is equal Thats the case when your approach doesn't work that's why we use dp to store both possible path and take the max

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

          Thanks very much, I was just coming to this solution too.

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

      I too have a similar approach it doesn't require dp just simple bfs and simple observation.

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

      Why do you multiply s by 2 here? mx=min(mx,(2*s)-1);

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

      I am also solving problem C using same concept but I am using bfs instead of dfs. But I get tle in test case2. Can anyone tell why my solution is getting tle. https://codeforces.com/contest/1689/submission/160208992

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

      can you please explain me the logic of 2*s -1 and 2*s in leaf node case and 2degree node respectively

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

    Yes it had much simpler solution

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

    Agreed. For anyone who isn't aware, the non-DP approach is to let $$$v$$$ be the least deep vertex with at most one child. Then, the number of vertices that must be lost is $$$d(v) + c(v) + 1$$$, where $$$d(v)$$$ is the depth of $$$v$$$ (where the root has depth $$$1$$$) and $$$c(v)$$$ is the number of children of $$$v$$$.

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

      I am probably being stupid, but why is d(v) being multiplied by 2?

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

        For each two-child vertex down which the virus spreads, you lose both the child onto which the virus spreads and the other child, which you must shut down to keep the virus from spreading onto the other branch.

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

      whats the proof for this?

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

        After reading Geothermal's second comment, I had to think carefully and visualize a tree that had layers of two-child vertices followed by a single- or no-child vertex. Then it became clear.

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

    Yeah, brute force worked, i also submitted dp solution later ,both solutions runtime was same.

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

    I hate you, i really hate you people

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

fastest editorial ever? nice

very fun, wish I could do more than 3

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

    I don't think so there was recently a contest in which they update the rating and the editorial was out the minute contest and system testing ended. It was Instant no delay.

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

In problem C, wish there was a test case in the sample, where the input had an edge connecting from child node to parent node.

Initially I assumed that, the edges were always from parent to child, and wasted time.

I know it is my fault for making wrong assumption. But still :(.

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

    So true dude i got three RE and as soon as i saw the test case and made a little tweak it worked

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

    I wasted half of my time trying to code a greedy algorithm, and only realized halfway through that it was supposed to be dp, so that was kinda sad lol.

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

      i also wasted alot of time on greedy and its implemetation,then in last 20 min all of the sudden observation came and coded it real quick and got ACed

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

Cool

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

O(n) solution for B.

The smallest possible lexicographic permutation is 1,2,3,4... Assume that this is the answer. Now just check if any element of the answer array matches with input permutation. if yes, swap it with next element. It's easy to see that no conflict would arise in this manner. There's edge case for last index, we have to swap it with previous element.

My submission- https://codeforces.com/contest/1689/submission/160104354

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

The problem IDs in the editorial are shown as the gym IDs (probably, some testing mashup). Please fix it.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -64 Vote: I do not like it
// My solution for A:

#include "bits/stdc++.h"
using namespace std;


void solve();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    int tc;
    cin >> tc; 

    while(tc--)  
    {
        solve(); 
    }
    return 0;
}
void solve(){
    int n, m, k; cin >> n >> m >> k;
    string a, b, c = ""; cin >> a >> b; 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = 0, turn = 0;
    if(a[i] > b[j])
    turn = 1;
    if(a[i] == b[j] && n > m)
    turn = 1;
    while(i < n && j < m)
    {
        if(turn == 0)
        {
            c += a[i]; i++;
            for(int t = 1; i<n && a[i]<=b[j] && t < k; i++, t++)
            c += a[i];
            turn = 1;
        }
        else
        {
            c += b[j]; j++;
            for(int t = 1; j<m && b[j]<=a[i] && t < k; j++, t++)
            c += b[j];
            turn = 0;
        }
    }
    cout << c << endl;
}
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fast tutorial Very nice problems More contests like these please!!

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

balanced round with good problems keep it up

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

cool problems and well organized overall a very good contest.thanks:)

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

Problem C can be solved greedily. I just find the shortest path from root to the node which have less than 2 children and infected those node and saved all other nodes by deleting the first node of every subtree connected to these infected nodes.

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

    Nice Observation! What is cnt in your code?

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

      cnt represent that the last node has any child or not . If the last node has no child then there is no subtree connected to that node and in that case there is one less node to delete. That's why when cnt is 1(no child) the output is n-2*(ans+1)+1 which is equal to n-(ans+1)-ans and in the case where cnt is 2(has one child) the output is n-2*(ans+1)

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

    I solved C absolutely the same way as you

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

    what does this part of the code do?


    if(sz<3){
            if(dis<ans){
                ans=min(ans,dis);
                cnt=sz;
            }else if(dis==ans){
                cnt=min(cnt,sz);
            }
            return;
        }
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If sz is less than 3 this means that the node has only one child or no child so the path ends here and I am just taking the minimum of all the path from root to the node having no or one child and cnt just stores that the last node has a child or not

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

Why is this getting MLE ?

My code for C : 160135752

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

    Your solve function is called recursively infinite times as it is calling its parent node in some test cases like the below one.

    Test Case:
    5
    2 3
    5 1
    4 2
    1 2
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Fixed , thank you !

      Still , it is curious why it got MLE instead of TLE in this case.

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

        I think it would be TLE if it was an iterative loop, but recursively 3 seconds is more than enough to exceed the memory limit.

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

The hint 3 in problem E tells that answer is 0, 1 or 2. But we have an answer 3 in the example.

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

    Perhaps they exclude the mandatory "+1" to the zeros initially

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

For B, lexicographicaly is supposed to be string ordering not integer ordering :((((((((((((

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

Can someone please explain problem C? Since it is a binary tree there will always be at max two edges from the root node. I calculated the indegree of both and subtracted the minimum to find the max nodes which can be saved but this approach is giving wrong answer on test 3. Pls Help

https://p.ip.fi/4svQ

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

    I'm not sure what you mean but you can make more than 1 saving move

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

they didn't thought that C can be solved using DFS?

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

For D, another approach is to use the fact that $$$abs(x) = max(x, -x)$$$.

Let $$$S$$$ be the set of black cell, then we need to minimize: $$$max(abs(i - x) + abs(j - y))$$$ for every combination of $$$1\leq i \leq n, 1\leq j \leq m, (x, y) \in S$$$.

This is just $$$max(max(i - x, x - i) + max(j - y, y - j))$$$.

Just expand the inner $$$max$$$ and we will have 4 cases to check, similar to the official tutorial.

160104327

I think this idea ($$$abs(x) = max(x, -x)$$$) is pretty common but still very powerful, probably would have taken much more time to solve D if I didn't know it.

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

    When I tested the round, I immediately recognized the problem as one where you need to transform the coordinates in such a way that the Manhattan metric becomes the Chebyshev metric (which corresponds to rotation by 45 degrees and appropriate scaling). $$$|x| = \max \{x, -x\}$$$ is basically why that transformation works. I was also opposed to adding this problem in the contest because 1658E - Gojou and Matrix Game is a strictly harder version of the problem.

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

    In the 4 cases that we make on expanding the max, there is an underlying condition for every case right, for example, only when $$$i \leq x$$$ and $$$j \leq y$$$, we get the Manhattan distance as $$$x + y - (i + j)$$$, but in your implementation, you have directly chosen the maximum value of $$$x + y$$$, (say it is $$${(x+y)}_{max}$$$) and you've taken the maximum of $$$cost$$$ and $$$(x+y)_{max} - (i+j)$$$ without checking if $$$i\leq x$$$ and $$$j\leq y$$$. Can you please explain the thought process behind this and why this works?

    Edit: I misunderstood what you meant by "expanding the inner max", I got it now, thanks.

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

      Yes, writing out the expansion more explicitly for anyone who doesn't see it, it is equal to $$$\max_{(x,y) \in S} \max(i-x+j-y,i-x+y-j,x-i+j-y,x-i+y-j)$$$ $$$= \max( \max_{(x,y) \in S} (i-x+j-y), \max_{(x,y) \in S} (i-x+y-j), \max_{(x,y) \in S} (x-i+j-y), \max_{(x,y) \in S} (x-i+y-j))$$$ $$$= \max(i+j + \max_{(x,y) \in S} (-x-y), i-j + \max_{(x,y) \in S} (-x+y), j-i + \max_{(x,y) \in S} (x-y), -i-j + \max_{(x,y) \in S} (x+y) ),$$$ and you can precompute each of the four terms $$$\max_{(x,y) \in S} (ax + by)$$$ for $$$a,b \in {-1,1}.$$$

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

Problem D can also be solved by dp.
But we have to maintain 4 dp tables. One table dp[i][j] stores max distance of a black point from i,j in top left of the matrix and other tables will store for other three part of matrix which is top-right, bottom-left and bottom-right . Max distance of a point from black point will be max of the value from all four table and then we can take minimum of all these and that will be our answer .

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

    Even just 2 dp tables are sufficient... One storing max distance of a black cell with x coordinate < i & other with x coordinate >= i for a given (i,j)

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

      nice solution. I missed the idea of using first and last rows per column

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

      can you explain more ? i didn't get what you mean by max dist. < i . Like what does this signify?

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

        For each point (i,j), we want to know the max distance of a black cell from it. Once we know this, we can simply iterate over each (i,j) & find the one which is having min value. Now, for finding this, I define 2 dp tables :

        dp1(i,j) : Max distance of a black cell from (i,j) considering all black cells with coloum no. < j.

        dp2(i,j) : Max distance of a black cell from (i,j) considering all black cells with coloum no. >= j.

        Now, let's try to build transition for dp1(i,j), it includes all black cells with coloum no. 0 to j-1. As per definition of dp1(i,j-1), it includes all black cells with coloum no. 0 to j-2.

        So, now dp1(i,j) = max(1 + dp1(i,j-1), max distance of a black cell in (j-1)th coloum from (i,j)).

        Similarly, dp2(i,j) = max(1 + dp2(i,j+1), max distance of a black cell in jth coloum from (i,j)).

        Now, max distance of a black cell from (i,j) = max(dp1(i,j), dp2(i,j)). You can check out my code : here

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

I was thinking of applying a greedy approach for problem C, why is it not enough to find the closest path from root to leaf or a node which has just 1 children. after we find the path length we can just get the answer by (N — (x + (x-1)) + 1 ( 1 for the case if the last node found had 1 child).

What i was thinking is for every step we have two choices either remove one branch or the other, when we remove one branch we also delete a node, thus (x + (x-1)), these are the nodes removed or infected, after that just subtract this from total N.

The approach is wrong but i can;t figure out why, can someone help please?

Okay, got the error, the approach was right, the problem was i was BFS so i had to take care of the fact that if there are two nodes in which one has only one child and there is other node which does not have a child, i will go with the one which does not have a child and in that case the formula will be n-(x+(x-1)) only

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

    From what I understand you are trying to say, your approach is correct! This is actually the same approach that Geothermal had: https://codeforces.com/submissions/Geothermal You may have had some calculation error. Here is what he had to say:

    "Agreed. For anyone who isn't aware, the non-DP approach is to let v be the least deep vertex with at most one child. Then, the number of vertices that must be lost is d(v)+c(v)+1, where d(v) is the depth of v (where the root has depth 1) and c(v) is the number of children of v."

    (Why is the depth multiplied by 2 in your code?) "For each two-child vertex down which the virus spreads, you lose both the child onto which the virus spreads and the other child, which you must shut down to keep the virus from spreading onto the other branch."

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

$$$O(n(log(max ai))^2)$$$ solution to E.

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

For what purpose there was this limitation in A, that "no character is contained in both strings."?

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

    If smallest character in s equals to smallest character in t, which should we choose?

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

      Sorry, I still dont get it, what is wrong with this submission 160146764 ?

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

        160162775 check this

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

        If you take a character from string a, you are not resetting the count for the other string to 0.

        Assume given strings are a = "aaacdd" and b = "bcde", and k=10. Your vector ab will be then ["ddcaaa", "edcb"].

        Initially, your cnt = [0,0] and ans is empty. After first three iterations, ans becomes "aaa", cnt = [3,0], and ab = ["ddc", "edcb"]. Now in fourth iteration, ans becomes "aaab" but cnt = [3,1]. It should become [0,1].

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

      Can you please check my solution if that condition is not included: comment link

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

0

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

anyone plz discuss the approach of problem D. it will be very helpful for me, why it's maximize i+j and i-j, and , minimized i+j and i-j also.

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

Not figuring out definitely correct (strict $$$O(nm)$$$ complexity) solution for D, but use some tricks to get it passed.

It is plausible to assume that $$$ans$$$ is close to the "center" of black cells (here I adopt $$$center=\frac{max-min}{2}$$$ for both x and y axis), then iterate over and move to adjacent cells util max Manhattan distance descend to optimum.

I'm not sure if max Manhattan distance has the same property of monotonicity as Euclidean distance (a classical problem is covering points on the plane with smallest circle). If that property holds, binary search may also work.

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

In problem C, can someone provide a smaller test case in which deleting the child with a higher subtree will lead to the wrong result? Thanks in advance!!

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

    1

    7

    1 2

    1 3

    3 4

    3 5

    2 6

    6 7

    here root 1 : left child subtree (with root 2) has the same number of vertices that can be saved by

    right child subtree(with root 3).

    so if you cut left child subtree in the end answer will equal 2

    but if you cut right child subtree in the end will equal 3

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

      For same number of subtrees, I deleted the one with higher number of children

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

        here both subtree of 2 and 3 have the same number of children

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

The tests for A are very weak. I can see many solution hackable. I can't see the hack button. But here is the test case:

1
4 4 3
aaab
aaad

if this works swap the strings

1
4 4 3
aaad
aaab

Example: https://codeforces.com/contest/1689/submission/160093968 :

correct answer: aaaaaab,
output: aaaaaad

UPDATE: Almost every solution is hackable. Why I can't see hack button?

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

1689E - Бесконечность can be optimized to $$$O(n A^2)$$$, where $$$A=\log{\max a_i}$$$
We can count $$$cnt[i][j]$$$ how many times pair of bits $$$i,j$$$ was in all $$$a_k$$$ it's works in $$$O(A^2)$$$ per element and then check if this grpah connected
To check if bit set just check $$$a[i][i] > 0$$$, if we have array $$$cnt$$$ DFS works in $$$O(A^2)$$$
So when we adding or subtracting 1 we can just update cnt we are doing it $$$O(n)$$$ times
code: 160147889

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

Oh! Problem D had such simple solution. But I overkilled it with binary search.

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

    Can you please explain how you used binary search I thought of doing so, searching for optimal distance but got dtucked on how to verify if the rhombus around all black points intersect at some pointfor current mid

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

      There are four sides in rhombus. In all the cells of two opposite sides i + j remains the same and in all the cells in other two opposite sides i — j remains same where i and j are row and column number. So I divided them into two sets of ranges of two types where in first type, each range is of the form [i + j — mid, i + j + mid] and in other type, ranges are of form: [i — j — mid, i — j + mid]. Then just find the intersection of both type of ranges and iterate over every cell (i, j) to check if i + j lies in intersected range of first type of ranges and i — j lies in the intersected range of second type of ranges.

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

dang I was really close with D, but I wrongly thought that 4 squares shouldn't be sufficient and end up making convex hull

B was too googlable, it was simply "minimum derangement" but overall the contest was nice!

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

First time my code get coincident with other. I don't know how. I use my local system to code not any online ide. Any one know how this happens. @codeforces admin

Attention!

Your solution 160095764 for the problem 1689A significantly coincides with solutions ATGP07/160094316, N_Assass1n/160095682, hydracody/160095764, Sattu_45/160095838, senju/160096436, Nonunou/160096758, madhurtoo/160099627, krishagarwal535/160100209, agamya.vrishabh/160104578, BrxDeputat/160105289, nestedwindow/160105290, b4t7r/160106016, Night_N0mad/160106327, tarun_1801/160106986, gabdyq/160107529, Harneet_9042/160108448, prachi_007/160109143, arjun_0207/160109508, tempMail1/160109881, ayush222sagar/160110162, drtank/160110887, codeblaster_20/160110959, Gurpreet_1/160111181, ArijitDalui/160111590, prachi15/160112081, nam_j/160112984, habib_toshev/160114126, Commander_coder/160114343, nj234/160114868, ramsampell_123/160114993, 2020uce0063/160115191, NoiceOp/160115224, BANDeputat/160115314, aditi.ojha.min20/160115506, aditi_ojha_21/160115648, rahgeer/160115718, kaushik_35/160119047, shreymishra2708/160119683, Avi_afrid/160119925, Chutkicoding/160120853, Shubhamshu/160123894, anipatil21/160124551, bapi123/160125895, seekingmygreat/160126053, Pranay_2020/160126387, sun_shine11/160126594, RandomNumber97/160126635, Shaun_2002/160126864, sahaj_279/160126885, roy0123/160127516, aks2001/160128701, 203ashish/160129355, Rxhul_12/160129697, ishitgarg1231/160130062, aman584/160130078, akashrs/160130220, Shake-Her/160130354, rohit_kumar/160131632, shubhanksagar3/160136047. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. Attention!

Your solution 160107390 for the problem 1689B significantly coincides with solutions Sattu_45/160099066, N_Assass1n/160100029, Nonunou/160100053, senju/160102702, Zer0/160103728, shubh_k_04/160103825, hydracody/160107390, Gurpreet_1/160107617, 2020uce0063/160108774, agamya.vrishabh/160109739, codeblaster_20/160109812, habib_toshev/160110709, prachi_007/160111563, madhurtoo/160111641, shreymishra2708/160112448, aditi.ojha.min20/160113447, aditi_ojha_21/160113816, gabdyq/160114250, arjun_0207/160114516, krishagarwal535/160114531, BANDeputat/160115107, ArijitDalui/160115210, Night_N0mad/160116674, ramsampell_123/160117422, rahgeer/160118106, tarun_1801/160118246, Chutkicoding/160118336, nam_j/160118957, ayush222sagar/160118998, ATGP07/160119810, bapi123/160121793, NoiceOp/160123135, tempMail1/160123286, Avi_afrid/160123337, BrxDeputat/160123536, Shake-Her/160124454, sahaj_279/160125689, kaushik_35/160125738, ishitgarg1231/160126911, devanshkapri/160126964, drtank/160126980, RandomNumber97/160127515, prachi15/160127769, aman584/160127809, seekingmygreat/160127922, akashrs/160128302, shubhanksagar3/160128904, rohit_kumar_/160128905, roy0123/160129195, nj234/160129276, Harneet_9042/160129384, Commander_coder/160129457, sun_shine11/160129480, aks2001/160131274, 203ashish/160131675, anipatil21/160131980, Shubhamshu/160132285, Rxhul_12/160133135, Pranay_2020/160133221, Shaun_2002/160134063. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

Hi Guys! I need a little help with question C. my solution keeps getting a MLE verdict. I have no idea why. I would really appreciate it if you can tell me how to optimize it. thank you :).

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

just realized, i was printing -1 directly after reading in n == 1 without further reading in the elements of the array, and hence failing pretest 2 in B. :/

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

Can someone explain D please. I don't understand what 4 regions is getting created

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

    The regions are top-left rectangle, top-right rectangle, bottom-left rectangle and bottom-right rectangle, which are created by lines parallel with coordinate axes passing through our yellow point.

    I'll add this in the editorial.

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

      what does i+j, i-j signify can you explain it more?

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

in D, As per editorial, we are selecting 4 points with different cases. Now what if you find answer to a point which is not able to belong to the correct case. I mean case1 is for both positive but is not getting achieved. explain plz?

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

Please tell me why my BFS code is not working on Prob C.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using ll = long long;

#define all(a)             (a).begin(), (a).end()
#define rall(a)            (a).rbegin(), (a).rend()
#define sz(a)              (int) ((a).size())
#define pb                 push_back
#define fi                 first
#define se                 second
#define f0r(i, a, b)       for(int i = (a); i < (b); ++i)
#define f0rr(i, a, b)      for(int i = (a - 1); i >= (b); --i)
#define trav(i, v)         for(auto &i : (v))

template<class T> using V = vector<T>;
template<class T, class T1> using P = pair<T, T1>;
template<class T, class T1> using VP = vector<pair<T, T1>>;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> T pow(T a, T b) { T res = 1; f0r(i, 0, b) res = res * a; return res; }
template<typename T> void ckmax(T &a, T b) { a = max(a, b);  }
template<typename T> void ckmin(T &a, T b) { a = min(a, b);  }

int dx4[] = {0, 1, 0, -1};
int dy4[] = {1, 0, -1, 0};
int dx8[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[] = {-1, 0, 1, 1, 1, 0, -1, -1};

const ll linf = 1000000000000000000;
const int inf = 1000010000;
// <===================================================================================================>

vector<vector<int> > g;
vector<int> subTree, vis;

void dfs(int u) {
   vis[u] = 1;
   trav(v, g[u]) {
      if(vis[v]) continue;
      dfs(v);
      subTree[u] += subTree[v];
   }
   vis[u] = 0;
}

int main(){
   cin.tie(nullptr)->sync_with_stdio(false);

   int tt = 1;
   cin >> tt;
   f0r(T, 1, tt + 1) {
      int n;
      cin >> n;
      subTree.assign(n, 1);
      vis.assign(n, 0);
      g = vector<vector<int>> (n);
      f0r(i, 0, n - 1) {
         int u, v;
         cin >> u >> v;
         u--, v--;
         g[u].pb(v);
         g[v].pb(u);
      }
      dfs(0);
      int ans = 0;
      queue<int> que;
      que.push(0);
      while(true || !que.empty()) {
         int u = que.front();
         que.pop();
         vis[u] = 1;
         vector<int> ver;
         trav(i, g[u]) if(!vis[i]) ver.pb(i);
         if(sz(ver) == 0) break;
         if(sz(ver) == 1) {
            ans += (subTree[ver[0]] - 1);
            break;
         }
         if(subTree[ver[0]] > subTree[ver[1]]) {
            ans += (subTree[ver[0]] - 1);
            que.push(ver[1]);
         } else {
            ans += (subTree[ver[1]] - 1);
            que.push(ver[0]);
         }
      }
      cout << ans  << "\n";
   }
   return 0;
}

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

    Please use spoiler to write your code.

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

Prob A is not diffcult, but cost me 48 minutes to solve it, becaue I add multi characters to string c in one operation. o(╥﹏╥)o

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

Can someone tell me in 1689D - Lena and Matrix why taking average of leftmost and rightmost row and column (i.e. x=avg of(max row i+ min row i) and y=(max column j+ min column j) and taking all pssible value of (x,y) by taking ceil and floor value(i.e. 4 case) and checking which gives minimum distance for all black co0rdinates is giving wrong answer.(160145986). Any counter example to show this method is wrong??

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

I have a doubt the code given for A gives wrong answer for

1

6 4 2

aaaaaa

aaaa

given_answer:aaaaaaaa

expected:aaaaa

I was thinking that we should also consider whether string a is small or stering b at a moment when both has same smallest character. Please correct me.

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

    you have to stop when any of the string is empty and since "a" is lexographically smaller than "aa" so its better to empty the second string first to get optimal string

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

      yaa exactly but many submissions including the editorial one gives the wrong answer as answer should be aaaaa. Correct me plz

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

    Actually in given question same character does not appear in both strings. But lets say we allow same character to occur, then the answer in your case would be $$$aaaaaaaaa$$$ (9 times $$$a$$$)

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

      Oh okay got it forgot to read that.

      Why the answer should be 9 times a we take 2 aa from string b then one a from string a and again 2 aa from string b. Now b is empty hence answer should be aaaaa.

      But yaa I have to read the problem more carefully

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

        Yes you are right here, lexicographically smaller string should be smaller!

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

The editorial's solution for problem D 1689D - Lena and Matrix may be too slow for languages like Python. I found a small speedup that allows Python code to pass the time limit.

Instead of "iterating over all squares in the matrix and finding the most distant black square", not all squares in the matrix actually need to be checked. For example, points outside the black diagonal rectangle (as shown in the editorial) clearly can't be optimal, and hence don't need to be checked.

Intuitively, points near the middle of the black diagonal rectangle have the best chance of being optimal and should be checked. I'm not sure how to prove that this is sufficient other than "Proof by AC" ;)

The time complexity is still O(nm) but maybe with a smaller constant factor.

Slow version, where all squares are checked (TLE in Python): https://codeforces.com/contest/1689/submission/160175658

Fast version, where only 4 middle squares are checked: https://codeforces.com/contest/1689/submission/160175205

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

A more complicated but mathematical(?) solution for D via direct analysis of manhattan distance.

First note that if any black square is between two other black squares in the same row or column then in the optimal configuration the longest distance will not be to that square. This can be shown by computing the manhattan distances to an arbitrary point directly. One of the squares on its left/right side will have greater distance. So removing those squares we have $$$O(n+m)$$$ black squares left.

Now fix some row $$$a.$$$ We find the optimal column(s) $$$b$$$ that minimize the distance for squares in this row. Thus, we want to minimize $$$\max ( |a-x_i| + |b-y_i| )$$$ for $$$b \in [1,m].$$$ Each of the $$$|a-x_i|$$$ are constants, so we have functions of the form $$$c + |x - d|.$$$ It's easy to see (by looking at the graphs) that the maximum of two such functions $$$\max(c_1 + |x - d_1|, c_2 + |x - d_2|)$$$ is another such function $$$c_3 + |x - d_3|.$$$ It follows that the function $$$f(b) = \max ( |a-x_i| + |b-y_i| )$$$ is bitonic, and we can binary search to find the optimal $$$b$$$ value(s) for this row.

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

    not only can we binary search we can solve a system of equations to get exactly an x and y that will minimize the manhattan distance!

    this is done by noting that the maximum distance for a number of points would be max( a-xi + b-yi, xi-a + b-yi, a-xi + yi-b, xi-a + yi-b ) where i is the ith black square

    then we can see that we can compute the max manhattan distance is

    max( a+b + max(-xi-yi),

    b-a + max(xi+yi), 
    
     a-b + max(-xi+yi),
    
     -b-a + max(xi+yi))

    to minimize the maximum manhattan distance would be the equivalent of solving

    a+b + max(-xi-yi) = -b-a + max(xi+yi)

    b-a + max(xi-yi) = a-b + max(-xi+yi)

    though the problem with this is that a and b are not always integers

    in my submission i checked the four nearest integer points ¯_(ツ)_/¯ couldn't think of a better solution

    https://codeforces.com/contest/1689/submission/160184723

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

In D, we are checking 4 points. But for each point we are checking, there should be 4 cases for signs. What if the points we have chosen can only make 3 sign cases and cannot make the 4th sign case. Explain please.

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

    Even if we have just one B all 4 cases will be covered.

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

      I mean while checking for a certain white element, the black which we considered giving maximum or minimum for (let's say) case 3(+-) is not being in case 3 with the current white we are checking.

      We take a black (2,3) with min i-j = -1 (case 3). When we are checking for white at (0,0) 0-2 = -2, 0-3 = -3, it belongs to case 4. So we should have chosen a different point which could have given a good case 3 with this point

      Actually the solution is correct and maybe it requires some extra proof. That's what I am asking

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

Hehe finally got my O(nm + number of black points) solution for problem D to work :)

just in case of a harder problem in which n = 10e9, m = 10e9, and only the black points are given

https://codeforces.com/contest/1689/submission/160184723

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

Can anyone explain why the maximum answer can be 2 for E?

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

    maximum 2 operations after all the 0s have been turned into 1s

    for example

    1000

    0010

    0010

    =>

    1000

    1100

    1000

    the algorithm in general would be

    find maximum ai & -ai and two numbers that ai & -ai = max(ai & -ai)

    add 1 to one such number

    minus 1 from another one such number

    the minus 1 would become 11111110

    the add one would become 10000001

    since largest ai & -ai all other (ai & -ai) < max(ai & -ai) would be connected to 1111110

    then 10000001 would connect to all ai & -ai == max(ai & -ai)

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

O(N) solution

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; while(t--){ int n; cin>>n; vector a(n); for(int &y:a) cin>>y; if(n==1){ cout<<-1<<endl; continue; } int prev,minm; minm=1; unordered_map<int,int> m; vector ans; int flag = 0; for(int i=0;i<n;i++){ if(a[i]!=minm){ ans.push_back(minm); m[minm]=1; minm++; while(m.find(minm)!=m.end()&&minm<n){ minm++; } }else{ prev = minm; if(minm<n) minm++; while(m.find(minm)!=m.end()&&minm<n){ minm++; } ans.push_back(minm); m[minm]=1; minm = prev; } } if(a[n-1]==ans[n-1]){ swap(ans[n-1],ans[n-2]); } for(int y : ans){ cout<<y<<" "; } cout<<endl; }

return 0;

}

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

can someone tell why this code is not giving correct answer on test case 88 expected 3 but found 2

include

include <bits/stdc++.h>

using namespace std;

//Speed

define Code ios_base::sync_with_stdio(false);

define By cin.tie(NULL);

define Asquare cout.tie(NULL);

//Aliases using ll= long long; using lld= long double; using ull= unsigned long long;

//Constants const lld pi= 3.141592653589793238; const ll INF= LONG_LONG_MAX; const ll mod=1e9+7;

//TypeDEf typedef pair<ll, ll> pll; typedef vector vll; typedef vector vpll; //typedef vector vs; typedef unordered_map<ll,ll> umll; typedef map<ll,ll> mll;

// Macros

define ff first

define ss second

define pb push_back

define mp make_pair

define fl(i,n) for(ll i=0;i<n;i++)

define rl(i,m,n) for(ll i=n;i>=m;i--)

define py cout<<"YES\n";

define pm cout<<"-1\n";

define pn cout<<"NO\n";

define vr(v) v.begin(),v.end()

define rv(v) v.end(),v.begin()

// Utility functions template void prll(T &&t) { cout << t << "\n"; } void prllarr(ll arr[], ll n){fl(i,n) cout << arr[i] << " ";cout << "\n";} template void prllvec(vectorv){ll n=v.size();fl(i,n)cout<<v[i]<<" ";cout<<"\n";} template ll sumvec(vectorv){ll n=v.size();ll s=0;fl(i,n)s+=v[i];return s;}

// Mathematical functions ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);} //__gcd ll lcm(ll a, ll b){return (a/gcd(a,b)*b);} ll moduloMultiplication(ll a,ll b,ll mod){ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;b >>= 1;}return res;} ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}

//Graph-dfs // bool gone[MN]; // vector adj[MN]; // void dfs(ll loc){ // gone[loc]=true; // for(auto x:adj[loc])if(!gone[x])dfs(x); // }

define loop(i,a,b) for(int i=a;i<=b;i++)

define revloop(i,a,b) for(int i=a;i>=b;i--)

define readv(vec) for(auto &x:vec){cin>>x;}

define printv(vec) for(auto x: vec){cout<<x<<" ";}cout<<"\n";

//Sorting bool sorta(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second < b.second);} bool sortd(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second > b.second);}

//Bits string decToBinary(ll n){string s="";ll i = 0;while (n > 0) {s =to_string(n % 2)+s;n = n / 2;i++;}return s;} ll binaryToDecimal(string n){string num = n;ll dec_value = 0;ll base = 1;ll len = num.length();for(ll i = len — 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;}

//Check bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(ll i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;} bool isPowerOfTwo(ll n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));} bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;} //Code by Abhinav Awasthi

define vl vector

define vii vector

define vll vector

//#define vs vector

define vb vector

define no cout << "NO\n"

define yes cout << "YES\n"

using namespace std; void inpv(vl& a,ll n){ fl(i,n){ ll te; cin>>te; a.pb(te); } }

include

include

include<math.h>

using namespace std;

define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);

define nl "\n"

define ll long long

vector size1; vector parent; vector<vector>graph(10);

vectorlength;

ll dfs(ll node,vb & visited,ll last){ if(visited[node]){ return length[node]; } visited[node]=true; for(ll i=0;i<graph[node].size();i++){ // cout<<graph[node][i]<<" "<<node<<endl; if(graph[node][i]==last){ continue; } length[node]+=dfs(graph[node][i],visited,node);

}
return length[node];

} ll sol(ll node,ll last){ if(node==1){ if(graph[node].size()==2){ if(length[graph[node][0]]>length[graph[node][1]]){ return length[graph[node][0]]-1+sol(graph[node][1],1); } else{ return length[graph[node][1]]-1+sol(graph[node][0],1);

}
    }
    else if(graph[node].size()==1){
        return length[graph[node][0]]-1;
    }
    else{
        return 0;
    }
}




else if(graph[node].size()==2){
    if(graph[node][0]!=last){
        return length[graph[node][0]]-1;

    }
    else{
        return length[graph[node][1]]-1;

    }

}
else if(graph[node].size()==1){
    return 0;
}
else if(graph[node].size()==3){
    if(graph[node][2]==last){
        if(length[graph[node][0]]>length[graph[node][1]]){
            return length[graph[node][0]]-1+sol(graph[node][1],node);
        }
        else{
            return length[graph[node][1]]-1+sol(graph[node][0],node);

        }
    }
    else if(graph[node][1]==last){
        if(length[graph[node][0]]>length[graph[node][2]]){
            return length[graph[node][0]]-1+sol(graph[node][2],node);
        }
        else{
            return length[graph[node][2]]-1+sol(graph[node][0],node);

        }

    }
    else{
        if(length[graph[node][1]]>length[graph[node][2]]){
            return length[graph[node][1]]-1+sol(graph[node][2],node);
        }
        else{
            return length[graph[node][2]]-1+sol(graph[node][1],node);

        }


    }
}

}

int main() { fast_io int tt; cin>>tt; ll c=0;

while(tt--)
{
    c++;

   ll n;
   cin>>n;
   graph.clear();
   graph.resize(n+1);
   length.clear();
   length.resize(n+1);
   vector<ll>gg(n+1,1);
   length=gg;
   ll root=-1;


   fl(i,n-1){
    ll a;
    ll b;
    cin>>a>>b;

    graph[a].pb(b);
    graph[b].pb(a);
   }

   vb visited(n+1,false);
   ll ans=dfs(1,visited,-1);



  // cout<<ans<<endl;
   ll ans1=sol(1,-1);
   cout<<ans1<<nl;





}

}

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

whats wrong in this..? giving WA on test 2

ll dfs(ll node,vb & visited,ll last){ if(visited[node]){ return length[node]; } visited[node]=true; for(ll i=0;i<graph[node].size();i++){ // cout<<graph[node][i]<<" "<<node<<endl; if(graph[node][i]==last){ continue; } length[node]+=dfs(graph[node][i],visited,node);

}
return length[node];

} ll sol(ll node,ll last){ if(node==1){ if(graph[node].size()==2){ if(length[graph[node][0]]>length[graph[node][1]]){ return length[graph[node][0]]-1+sol(graph[node][1],1); } else{ return length[graph[node][1]]-1+sol(graph[node][0],1);

}
    }
    else if(graph[node].size()==1){
        return length[graph[node][0]]-1;
    }
    else{
        return 0;
    }
}




else if(graph[node].size()==2){
    if(graph[node][0]!=last){
        return length[graph[node][0]]-1;

    }
    else{
        return length[graph[node][1]]-1;

    }

}
else if(graph[node].size()==1){
    return 0;
}
else if(graph[node].size()==3){
    if(graph[node][2]==last){
        if(length[graph[node][0]]>length[graph[node][1]]){
            return length[graph[node][0]]-1+sol(graph[node][1],node);
        }
        else{
            return length[graph[node][1]]-1+sol(graph[node][0],node);

        }
    }
    else if(graph[node][1]==last){
        if(length[graph[node][0]]>length[graph[node][2]]){
            return length[graph[node][0]]-1+sol(graph[node][2],node);
        }
        else{
            return length[graph[node][2]]-1+sol(graph[node][0],node);

        }

    }
    else{
        if(length[graph[node][1]]>length[graph[node][2]]){
            return length[graph[node][1]]-1+sol(graph[node][2],node);
        }
        else{
            return length[graph[node][2]]-1+sol(graph[node][1],node);

        }


    }
}

}

int main() { fast_io int tt; cin>>tt; ll c=0;

while(tt--)
{
    c++;

   ll n;
   cin>>n;
   graph.clear();
   graph.resize(n+1);
   length.clear();
   length.resize(n+1);
   vector<ll>gg(n+1,1);
   length=gg;
   ll root=-1;


   fl(i,n-1){
    ll a;
    ll b;
    cin>>a>>b;

    graph[a].pb(b);
    graph[b].pb(a);
   }

   vb visited(n+1,false);
   ll ans=dfs(1,visited,-1);



  // cout<<ans<<endl;
   ll ans1=sol(1,-1);
   cout<<ans1<<nl;





}

}

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

Can someone point out my mistake in C!? What I did is: At each level of BFS, I found the node with largest number of nodes in subtrees. Added that amount to result and continue BFS with rest nodes of that level. My Solution

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

    Well, that does not work. The optimal solution is not to allways choose the bigger of the two subtrees. Instead, we have to choose the one where we can stop the infection at the earliest step. That is, where the path to the first vertex with less than two childs is shortest.

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

For 1st problem I tried a test case 1 5 5 2 aabbc aabbd The correct answer for this should be aaaabbbbc, but even their solution is giving aaaabbbbd. If someone is getting correct answer please check by reversing the string order and please correct me if a I am going wrong somewhere.

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

    The question stated: no [same] character is contained in both strings.

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

Hi guys, can someone explain why this code doesn't work. I'm stuck in this problem and keen on to solve it with this logic, here is code and i think easy to understand. https://codeforces.com/contest/1689/submission/160231154 C problem

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

Can we do D in O(K) where K denotes the number of black squares?

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

I think there is an $$$O(n$$$ $$$log(max(a_i))$$$ $$$+$$$ $$$log^2(max(a_i)))$$$ solution for problem E. Details is as follows:

First of all, the current solution can be sped up to $$$O(n$$$ $$$log^2(max(a_i)))$$$ by using dynamic connectivity or creating a spanning tree which connects all the nodes for every $$$a_i$$$, updating it for every $$$+1$$$ or $$$-1$$$ operation and running DSU to check if the bits are connected. That way, the precomputation part will be $$$O(n$$$ $$$log(max(a_i)))$$$, and the checking part can be done in $$$O(log^2(max(a_i)))$$$.

For the second optimization, I claim that only checking $$$log(max(a_i))$$$ times is sufficient for us to determine whether there exists a construction for answer $$$=$$$ $$$1$$$.

First of all, we have to precompute the connectivity of the 30 bits in the given configuration (after adding $$$1$$$ to every $$$a_i$$$ $$$=$$$ $$$0$$$) using DSU. Then, we store the index of the LSB (least significant bit) of every connected component in a set (which I'll call $$$R$$$). To check answer = $$$0$$$ we simply have to check if $$$|R|$$$ $$$=$$$ $$$1$$$.

Lemma 1: $$$+1$$$ operations only work if $$$|R|$$$ $$$=$$$ $$$2$$$ and $$$min(R_i)$$$ $$$=$$$ $$$0$$$.

Proof of Lemma 1

Lemma 2: $$$-1$$$ operations only work when LSB of current value $$$\geq$$$ $$$max(R_i)$$$ and the current component doesn't disconnect after the operation.

Proof of Lemma 2

Lemma 3: We will find a solution after checking at most $$$log(max(a_i))$$$ distinct values that has LSB $$$\geq$$$ $$$max(R_i)$$$.

Proof of Lemma 3

Hence, we can find the answer with overall time complexity $$$O(n$$$ $$$log(max(a_i))$$$ $$$+$$$ $$$log^2(max(a_i)))$$$. The $$$O(n$$$ $$$log(max(a_i)))$$$ is from the precomputation for the graph, and $$$O(log^2(max(a_i)))$$$ is for the queries.

Here is my implementation of the above solution. If you spot any flaws in my solution, please comment below; I would very much appreciate it. Also, sorry for my bad English ._.

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

how B can be optimized to O(nlogn)

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

B- Mystic Permutation's O(n) solution was awesome :)

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

https://codeforces.com/contest/1689/submission/160132878 Can anyone help with the test where my solution to C gets runtime error.

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

Problem C can be solved using a simple preorder traversal, with only an adjacency list as extra memory. Essentially:

dfs(current, current_kill, &min_kill):
   if current has 0 child:
        min_kill = min(current_kill, min_kill);
   else if current has 1 child:
        min_kill = min(current_kill+1, min_kill);
   else:
        dfs(current.left, current_kill+2, min_kill);
        dfs(current.right, current_kill+2, min_kill); 

If the current node has no children, then the infection has reached it's end, and the current killed node count can be compared to the global min_kill count.

If the current node has one child, it can be stopped by pruning that one child. This ends the infection, and increases the kill count by 1 extra, so we compare current_kill+1 instead.

If the current node has 2 children, we will try pruning each child. This causes the child to die, and the other node to be infected, so dfs is called again with current_kill+2.

This strategy will explore every path that the infection can take and store the minimum killed nodes in a single variable.

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

I tried the approach of Manhattan distance and rotating technique for problem D.Many people have solved this problem by DP. Can any one please explain your DP appraoch?

Thank you in advance for helping.

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

n0sk1ll, How to prove the solution for B?

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

Is there rigorous proof for question D?

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

I have some questions about the solution to problem A. What if I have taken all the characters in string A but there is still more than k characters in string B?

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

My Approach for problem C:

D0 = distance of closest leaf node from root.

D1 = distance of closest 2 degree node from root (Also consider root if degree of root = 1)

Answer = min(n - 2*D0 - 1, n - 2*D1 - 2)

Idea: we want minimal infection spread, therefore we will force the spread of infection to nearest cut-off point and that can only be a leaf node or a 2 degree node.

My Solution