Karavaiev's blog

By Karavaiev, history, 6 weeks ago, In English

Thanks for participating!

1521A - Nastia and Nearly Good Numbers

Tutorial
Solution

1521B - Nastia and a Good Array

Tutorial
Solution

1521C - Nastia and a Hidden Permutation

Tutorial
Solution 1

1521D - Nastia Plays with a Tree

Tutorial
Solution

1521E - Nastia and a Beautiful Matrix

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

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

Karavaiev can you give a proof or some intuition on why the greedy works in problem D ?

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

    We can keep for each subtree of r three states:
    1) the minimal solution without r in the initial tree. x1
    2) the minimal solution when we add an edge from the root of the subtree to r. x2
    3) the minimal solution for (2) that disconnects the root of the subtree and r. x3
    always x1 >= x2 >= x3; and x1 <= x3 — 1;

    for each subtree, if x3 == x1 we will run (3)
    else if x2 == x1 we will run (2)
    else, we will run (1) and remove the edge between r and the root of the subtree,
    which means to run (3).

    after we run this for each subtree, r is connected to his parent and to some bamboos. to calculate 1, 2, 3 just means to remove some arbitrary edges.

    x1 == x2 != x3 if and only if the degree of the root is lower than 2. Therefore, we won't remove the edge to the parent only if r is connected to less than 2 childrens and we receive the greedy solution.

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

    (1) ensures that we do not break any linear chains (bamboos)
    (2) is the case of an inverted Y shape. One of the 3 edges needs to be broken.
    Let's take an edge between 2 nodes A, B: A — B. It can be noted breaking any edge from A, except A-B will not affect any decision on B's edges except A — B.

    Now, note that the 2 bottom nodes of the inverted Y will be having a degree of atmost 3, because of steps (2) and (3). So, by removing the edge to the parent, we get an inverted V shaped chain.

    (3) If a node has more than 2 children, all but 2 will have to be removed for a chain. The edge connecting the node and the parent will be removed based on the parent's degree, subsequently in the DFS.
    Using the independence mentioned above, we can remove any of C — 2 nodes. (C = no. of children)

    The strategy ensures that only forced/inevitable deletions are done, as an argument for optimality.

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

    Let's say we decide to remove some $$$k$$$ edges when we are at a vertex $$$v$$$. It is always beneficial to remove the edge from $$$v's$$$ parent to $$$v$$$ because — removing it can only decrease the answer for the remaining tree

»
6 weeks ago, # |
  Vote: I like it -127 Vote: I do not like it

problem (A+B) videoTutorial : https://youtu.be/eoG05DnVQik

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

Qs regarding problem D. So we need to remove x edges. But to remove x edges choose cant we use this greedy strategy: choose the vertex x with maximum deg (if its greater than 2). go over adj[x]-choose vertex y with maximum degree. Then let us delete the edge x-y. Continue this process till there are no vertices with degree greater than 2.

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

    Edges: a0-a1, a1-a2, a2-a3, a3-a4, a4-a5, a1-b1, a2-b2, a3-b3, a4-b4 Next vertexes have 3 degrees: a1, a2, a3, a4

    Optimal solution is to remove a1-a2 and a3-a4 But if you remove a2-a3 on the first step you will need to remove extra two.

    So you can't randomly pick vertexes with max degrees.

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

My Problem D solution is different, I am in the middle of writing a community editorial for it, will be released soon :)

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

My Solution to problem D: https://codeforces.com/blog/entry/90476

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

below is my (not the cleanest) implementation of solution 2 in the editorial of problem C. code here. i also searched for the minimum (or the index that had value 1) instead of the maximum. the idea is the same but the implemention is slightly different.

EDIT: i made the code easier to read by removing my template

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

The solution of problem A can also be

$$$A(B-1)+A(B+1)=2AB$$$

since we have

$$$gcd(B,B-1)=gcd(B,B+1)=1$$$

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

    Why do you need the gcd condition?

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

      I think he added the gcd condition to prove that A(B-1) & A(B+1) are not divisible by AB and are nearly good

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

        It directly follows since both are -A and A mod AB.

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

          Indeed. I added the GCD condition only because that was my first thought, thanks for your reminding!

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

What If A==12,B==6, then 72 84 are good,12 is nearly good

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

    Read the problem statement carefully! For A=12,B=6 -> 72 is good and 84,12 are nearly good.

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

      sorry i got it , i used to understand that if one number can be divided by both 12 and 6 ,it is good ,but i ignore one thing , it must be divided by A·B

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

        i unknowingly assumed that if a divides n, and b divides n, then a*b also divides n.

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

Hey, can anyone tell what's wrong with my solution to problem B? what I have done is to check the gcd of each pair and continue in case its 1 and if its not 1 then replace the larger of the 2 consecutive numbers with the smallest prime number greater than the min of(ai,ai+1) and so on.I have also provided a case for those cases where the primes become equal after changing. In other words, I still can't find an error in my solution. Any help will be gladly accepted. my solution:115610004

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

    Your first issue is that your 'b' array isn't big enough, as it potentially needs to store 2 * n many things, and therefore doesn't output everything it needs to.

    However in addition to that, your solution still fails when that is fixed on test cases such as

    1 
    3 
    77 15 5
    

    as the second element is changes to 7.

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

      ohh right, I never thought of this case. Thanks a lot!!!

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

      i have found an easy solution for B.

      AS we don't need to minimize the number of operations, hence we can think of replacing all the numbers by 2 consecutive prime numbers.

      As the element in the array can go upto 10^9 , our job is to find 2 prime numbers that are just greater than 10^9 which are 100000007 and 1000000009.

      so just replace the elements with these 2 primes alternatively.

      code

      Here is my solution 115905873

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

    i did a similar thing. what i did was for every pair i replaced the first number with the minimum of the two and the other one with minimum+1 such that all numbers become consecutive and thus, coprime and the total number of steps would always be n-1(<n). I cant seem to find why this approach shouldn't work.

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

      that won't work, making the i th and i+1 th terms coprime doesn't mean that the i-1 th and the i th will remain coprime anymore after the i th is changed(considering the ith > (i+1)th)

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

        I have implemented a similar approach but it changes the larger number such it takes into account that the number preceding it and followed does match the condition

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

    I came up with the following solution for problem B. We can always make the array good in at most n/2 (floor value) operations. What the question says is that the input values of the array is restricted to 10^9 and we can choose any values less than 2*10^9 and replace. So we can choose any prime number greater than 10^9 like 10^9+7 and then for each alternate pair of indices (like 1 and 2, 3 and 4...), we can find the minimum value of the two, and put it in the first index, and for the second index we can simply put the prime value chosen. Hence our array will look something like (arr_element,prime_num,array_elem,prime_num...). So we can simply print all the pair of indices, and their minimum and the prime number chosen, without even checking the array.

    • »
      »
      »
      29 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if we find gcd(a[i],a[i-1])!=1 we print previous index, current index, min of these two, 10^9+7. then do a[i-1]=min a[i]=10^9+7. continue traversing the array.

      I am doing this but my test case fails, can you tell me why?

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

        So is it like you are making the changes only when you get the GCD not equal to one?

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

Another approach for B:

Observation : minimum element in the whole array wont be changed. Let the index of min element be 'mn'.

Fact : Consecutive elements are always relatively prime.

Approach : The idea is to make the array a sequence of alternate integers containing either a[mn] or a[mn]+1, such that a[i] != a[i+1].

There will always be N-1 such operations.

eg: a[ ]={9 6 3* 11 15}; ('*' denotes minimum element)

after all operations a[ ]={3 4 3* 4 3}.

Here's the code.

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

    I had the similar logic, but I started giving mn + 1 , mn + 2 , mn + 3... to the right as well as to the left of the min element.

    eg: a[ ]={9 6 3* 11 15}; ('*' denotes minimum element)

    after all operations a[ ]={5 4 3* 4 5}

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

In 1521A — Nastia and Nearly Good Numbers why a + a*(b-1)=a*b isn't working??

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

    It does work, except when b is 2 because of the problem asking for 3 unique numbers. See my code for one way of getting around this.

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

    if (b == 2) b = 4; x = a; y = (b — 1) * a; z = a * b; cout << x << " " << y << " " << z << "\n";

    for b==2 , use this condition , then it will work , for b==2 , the problem was that x and y were becoming same

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

    change it to a + a*(2*b -1) = 2*a*b

    it solves the problem of 3 unique numbers

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

    If you try this solution for test case a=13 and b=2 ,it won't work. You will get x=13 ,y=13 and z=26 but in the questions it's mentioned that x, y and z all three are distinct/different.

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

Hi, I have doubt for question A, I wrote that if B > 2, then z = AB, y = A, x = (B-1)A and if B = 2, I wrote x = A , y = 3A and z = 2AB, and for B = 1 is trivial. Is my solution wrong ?

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

    z should be 4ab

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

      Where do you mean ?

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

        look when b==2 , then x=A , y=3A so z should be x+y so 4AB (B because z should be mutiple of AB) hence when b is 2 so x=A,y=3A,z=4AB

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

          No even z = 2ab = 4a = a + 3a (since b = 2) is a multiple of AB = 2a

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

            ohh sorry! , i didn't notice that , i did same thing as you are saying for b==2 , you can check that out

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

              So if my solution is correct, then will I get any score(I am new to this site) ?

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

                If I were you, I will probably first check the checker log and see if there is any issues with your solution. Also, your solution does not account for integer overflow (when the number exceeds the integer limit which is the case here as A*B can go up to 1e12), so that is why your solution got a WA. You should probably use long long or other 64bit equivalent instead of integer to fix this.

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

                  Thank you for helping and am I allowed to check the 'checker log' during the contest ?

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

                  No, it is a feature that is only allowed off-contest, so it would be a smart idea to practice a lot beforehand so that you won't make these types of mistakes.

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

                  oh I see, anyway i started learning coding only a week ago, so i don't know much of coding anyway i will practice

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

    I looked at your code and you've got variables of type int, because of that a*b gives you integer overflow, try using long long instead of int and note that instead of %d u should use %lld

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

Also for B, generating 2 primes bigger than the max of array and then replacing every adjacent pair whose gcd is not 1 with their minimum and a prime (one of those alternatively) would work. I find this idea more intuitive.

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

    This is exactly what I did.

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

    Why do you need two primes?

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

      so that we don't replace two adjacent elements with the same prime number. consider the case 3 3 3

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

Another approach for problem B: Just replace elements at odd or even positions with 1e9 + 7, while maintaining the condition mentioned in problem.

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

    Yes, I exactly did the same thing. Took 1e9+7 and then for all the odd indices, replaced them with the minimum of the pair, and the even indices with 1e9+7.

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

    I'm also doing the same thing, why this does not work?

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

      Try: {2, 15, 6} You would actually shift '6' from 2nd index to 1st index, and then gcd(2, 6) > 1.

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

Can anyone explain how problem A gives yes when A=2 and B=2 ? I don't find a constraint in the problem that says the given integers are distinct.

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

    one solution is 2 4 6 . 4 is divisible by (A*B)=(2*2). 2 and 6 are divisible by A=2.

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

      OH my bad. I messed up in reading the problem statement. I thought good numbers are divisible by A and B . Its A*B :( . Thanks.

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

    4 6 10 is a valid output for A = 2 and B = 2.

    A number being divisible by A and B does not imply that it will be divisible by A*B. Here 4 is divisible by A*B but 6 and 10 are not (Although they are divisible by B they satisfy the condition for being nearly good)

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

can anyone tell what's wrong with my solution to problem B?.my solution is https://codeforces.com/contest/1521/submission/115603967

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

In the author's solution of problem C what the use of us array ? can anyone explain ?

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

WHAT'S WRONG IN MY SOLTION FOR PROBLEM C ,IT IS GETTING IDLE LIMIT EXCEEDED.CAN ANYONE PLEASE HELP WITH IT https://codeforces.com/contest/1521/submission/115666166(HERE IS MY SUBMISSION)

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

My Solution to problem B was different from the editorial. since all Ai<=10^9 and x,y<=2*10^9

So i filled MD=10^9+7 in alternate places. That way adjacent number always have gcd=1.

let a1,a2,a3,a4....an be the array then print k=floor(n/2) lines

each line four integers i=1;i<=n;i+=2 : i i+1 min(a[i],a[i+1]) MD

Eg: 5 2 4 6 3 5

OUTPUT 2 1 2 2 MD 3 4 3 MD

final array 2 MD 3 MD 5

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

    can you please tell what's wrong with my solution. 115603967

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

      Consider the test case:** 7 20 14.** Your code will first check 7 and 20, nothing wrong, then it will check 20 and 14, their GCD is 2, and so your code will replace 20 with 14 and 14 with 1e9+7. The resultant array is 7 14 1e9+7, but now the GCD of 7 and 14 becomes 7 and hence your solution fails.

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

$$$C$$$ can also be done in $$$4$$$$$$\lfloor \frac {n} {3} \rfloor$$$ $$$+$$$ $$$2$$$ queries, though my solution uses $$$3$$$ more queries

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

    Yes, I think my solution 115611578 also takes around $$$ \frac{4\cdot n }{3}$$$ in the worst case and $$$n$$$ queries in the best case.

    I restore $$$3$$$ elements in $$$4$$$ queries but if I find position of element $$$1$$$ or $$$n$$$, then I can easily find rest of the elements in $$$1$$$ query per element.

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

      omg orz i cant believe somebody actually wrote the bash sol

»
6 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

problem (A+B) videoEditorial : https://youtu.be/eoG05DnVQik

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

    Isn't pupil a bit too early to create video editorials for others? I think you should wait some time and start doing those when you are very good at them, because only then you can create quality video editorials.

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

      In fact he recorded the video in between the contest running. Its not a good strategy to just give up on contest when you still have 30 mins remaining with you.

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

in problem D, based on the question shouldn't the ans be just either 0 or 1?

question in brief:

In one operation:
1. remove any existing edge.
2. add an edge between any pair of vertices.

minimum operations to get a bamboo from a tree.

solution:
case1: if tree is already bamboo ans is 0.
case2: we can remove an edge from any leaf node and add an edge between vertices other than the leaf.
hence, we got a bamboo(i.e leaf node) from a tree?

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

Can someone hack this solution for C? I think I have used 1.66n queries in the worst case, n for finding the position of 1 and 0.66n for the remaining elements. In some cases I have used random numbers.

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

    So I tried hacking it. Consider this Testcase

    At the end we have 2 1 those are the first two numbers you deduce. Then there is this pattern reapeating and increasing: 3 5 4 then 6 8 7 and so forth. This pattern forces your programm to always pass through i -= 3; in your for loop. The last if condition if (val > mn2) then randomly either does a second query or it doesn't.

    I then started 50 tests with this locally and got these query-amounts:

    Query Amounts

    Some of the cases would've broken the $$$3n/2+30$$$ limit. So $$$3n/2$$$ seems to be some kind of worst case average of your algorithm and I am not sure how to further hack it.

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

      Thanks. Maybe repeatedly trying to uphack with this test case can work. Also you can include the same case again in a test as the limit on sum of $$$n$$$ over all test cases is $$$2 \cdot 10^4$$$.

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

        Here you go, it's hacked now. :D

        Although I guess it is not a good test case per se, since there are those "+30" free guesses.

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

          Thanks. Those +30 free guesses are there in all test cases, so why is this one not a good case?

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

I have a doubt in question A: Consider the case:

1
87 87

Won't it be impossible to generate three number such that exactly one is good and the other two are nearly good? All three numbers would simply be good?? Am I misunderstanding something?

More simple I have doubt when A equals B, shouldn't the answer be NO?

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

    In this case $$$87$$$ is nearly good. Or $$$2 \cdot 87$$$. It is not good though, since it is not divisible by $$$87 \cdot 87$$$

    $$$87 \cdot 87$$$ is a good number. Or $$$2 \cdot 87 \cdot 87$$$

    So $$$87$$$, $$$(87-1)\cdot 87$$$ and $$$87 \cdot 87$$$ would be a valid solution.

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

      Ohh I missed that, I just assumed that A.B meant it should be divisible by A and B both, didn't notice it should be divisible by their product too :(

      Thanks.

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

for the 2nd problem could a possible logic be that we find the gcd of two consecutive numbers and if it is not 1 then we replace a[i] with the minimum of the two values and a[i+1] with the next smallest prime after a[i]. So for eg if a = 9 6 3 11 15 then after the 1st iteration, we get 6 7 3 11 15, i.e. selecting the 1st two since gcd(9,6)!=1 and then replace it with the min i.e. 6 and the next with 7 (smallest prime after 6). This logic is showing the wrong answer. Can anyone pls let me know the fault?

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

hey,can anyone tell what wrong with my solution https://codeforces.com/contest/1521/submission/115629013 Firstly,I take starting of 2 no and if one of them is minimum,let 1 no is minimum than 2 no change to first no +1 but if 2 no is minimum than first no change to x*y+1 where y is 2 no and x is previous no that came befor 1 no in array.

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

1521A: If A%B==0 then two other numbers which are divisible by A is also divisible by B then all three are good,is that case not considered. Please help if i missed something

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

    if X%(A*B)==0 then x is good, not if x%b=0 let x=4 a=4 b=2 here, X%(A*B)!=0 x%(4*2) not equal to 0 but x%4=0

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

      thanks i missed that A.B i thought divisible by A and B is good.My bad

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

No contest this coming week ??

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

Another easy approach for B is that to change every odd index to the left and right to the minimum element to a prime which is greater than 1e9 . Every element of the array is less than 1e9 and the constraint for choosing x and y is 1 < x,y <= 2e9 .

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

For the task D, editorial gave a nice greedy solution. I did it using DP. But I see flows mentioned in the tag. Can someone explain how do we do it using flows?

Thanks.

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

Problem D, test case 1

Why wouldn't this be valid operations?

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

I have solved B , the approach i followed is , try to make adjacent elements consecutive. for that i will first make either all odd position or all even position equal to smallest number in the array. then will replace all the position left with smallest element +1 . i got WA stating the array is not good . I commented out the part where i print the array . And getting the array good but still getting this WA . Please help where i am getting wrong. Your text to link here...

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

Proof of problem $$$D$$$ greedy solution:

Starting from the deepest nodes, if we have a node $$$x$$$ having parent $$$p$$$, where $$$x$$$ has $$$k$$$ leaf children where $$$k>1$$$, we know that $$$x$$$ at the end should have at most $$$2$$$ adjacent nodes anyway, so we give priority to first removing the edge to $$$p$$$, as this edge may give the opportunity for $$$p$$$ in its turn to remove less edges, while the edges to $$$x$$$'s children are guaranteed to not give any such future opportunities. So removing the edge to $$$p$$$ will sometimes be better, and in the worst case will be similar to removing one of the children edges. This logic continues to be applicable as we go up the tree.

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

    I had a trouble understanding how "giving priority to removing the parent-facing edge" also works when a node $$$x$$$ has non-leaf children; I cannot believe my intuition. Now, I understand it systematically after reading your comment many times.

    Let's define the problem as finding the set of edges to remove that is of minimum size. Of course, there are multiple optimal solutions. $$$SS_0$$$ is the set of such solutions.

    Starting with the original tree $$$T_0$$$ and its nodes that have only leaf children, applying "giving priority to removing the parent-facing edge" on each node $$$x$$$ gives us a forest consisting of bamboos and a smaller tree, $$$T_1$$$. We now have the set of edges removed from this phase, $$$R_1$$$. There exists $$$S_1 \in SS_0$$$ such that $$$R_1$$$ is a subnet of $$$S_1$$$. Why?:

    • For each node $$$x$$$ from above, consider the $$$T_0$$$ as two trees separated by the parent-facing edge ($$$e \in R_1$$$) of $$$x$$$.
    • If all $$$S \in SS_0$$$ does not contain the $$$e$$$ (meaning the $$$e$$$ has survived from removal), we can always delete* the $$$e$$$ and restore any child-facing edge of $$$x$$$, keeping these unchanged, the degree of $$$x$$$ and the total number of edges removed. (*Here, delete is meant to "delete from a tree", not "delete from a set")
    • Repeating it, we can transform any $$$S$$$ into $$$S_1$$$.

    Let's denote the set of all such $$$S_1$$$'s as $$$SS_1$$$. For $$$T_1$$$ and $$$SS_1$$$, we can apply similar reasoning. The only difference is that we pick nodes whose children are linear chains or leaves. A linear chain acts like a leaf.

    Repeat until $$$T_i$$$ reaches the empty tree. We eventually get the optimal solution $$$S = \bigcup R_i$$$.

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

Problem D reminds me of a Vietnamese fairy tale — The hundred-knot bamboo :))

I'm wondering if anyone of the problemsetter have read this :))

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

i have found an easy solution for B.

AS we don't need to minimize the number of operations, hence we can think of replacing all the numbers by 2 consecutive prime numbers.

As the element in the array can go upto 10^9 , our job is to find 2 prime numbers that are just greater than 10^9 which are 100000007 and 1000000009.

so just replace the elements with these 2 primes alternatively.

code

Here is my solution 115905873

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

i want help

i have tree node from 1 to N and u and v (basically edge b/w nodes) how to find the number of children for each node from 1 to N

ex N=11

1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11

for node 2-> 6 3-> 2 4->2 5->2 6,7,8,9,10,11->0

i have used DFS but get TLE any optimization

my approach --->

void dfs( un<ll, vector>mp, int parent, int &count)

{

for(auto i:mp[parent]) {

dfs(mp, i,(++count));
}

}

void solve() { int noChild[n+1]={0};

for(int i=2; i<=n; i++)
{
     int count=0;
    dfs(mp,i,count);
    noChild[i]=count;
}

} }

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

I think Problem E doesn't need to sort. We only need to fill the most frequently occurring numbers x first. Because the order of other numbers doesn't matter. It's easy to prove.

my solution

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

For the problem A: For the input 56 8 the answer of Jury is 56 448 504. For A = 56, B = 8, X = 56, Y = 448, Z=504. A divides X and B divides X B divides X and B divides Y A divides Z and B divides Z. So all tree are good numbers. How could that be a correct answer?

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

Can someone explain to me why I am getting TLE in this question. Here is my solution:-

https://codeforces.com/contest/1521/submission/115881089

I broke all edges as given in the tutorial and then applied bfs to find the endpoints of the small bamboo trees.

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

i dont really think i've understood the editorial of problem D.

according to the statement, cant we hack it with the following?

1
10
2 8
2 5
2 4
8 1
8 7
5 6
5 3
4 10
4 9

but the std to D has run correctly.

could anybody pls explain it to me? thank you and sorry for my poor English and maybe impolite wording :)

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

Could someone please provide me a commented code for problem D?

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

How to solve problem E using DP

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

With quite a bit of trouble I managed to solve 1521E - Nastia and a Beautiful Matrix.

First I solved a different problem(because I'm dumb and can't read problem statements). The original one asks for both the main and the off diagonal to have different numbers or a number and a hole(0 is not treated as a number).

Now m, k, and a_i elements be the same and for the 2x2 submatrixes you have the following rules:

  • The 2 elements of the main diagonal are different. 0 is a number not a hole.
  • At least 1 element is 0.

This one also has a constructive solution. This one 116955492. If you solved the original one try to solve this one without looking at the solution. It has a more subtle solution in the sparse case.

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

can anyone tell me why https://codeforces.com/contest/1521/submission/117051622 its showing runtime error

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

Can someone explain me problem B -> "Nastia and good array"