ch_egor's blog

By ch_egor, 7 months ago, translation, In English

Thanks for the participation!

1445A - Array Rearrangment was authored by meshanya and prepared by ch_egor

1445B - Elimination was authored by Helen Andreeva and prepared by ismagilov.code

1444A - Division was authored by vintage_Vlad_Makeev and prepared by grphil

1444B - Divide and Sum was authored and prepared by NiceClock

1444C - Team-Building was authored by V--o_o--V and prepared by wrg0ababd

1444D - Rectangular Polyline was authored by Zlobober and prepared by DebNatkh

1444E - Finding the Vertex was authored by V--o_o--V and prepared by 300iq

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +121
  • Vote: I do not like it

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

very fast tutorial thanks.

»
7 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Great sets of problems with short statements!

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

Thanks for the quick tutorial!

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

How the heck was this really 14 hours ago? xD

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

    It was created 14 hours and kept as a draft and now it is made public.

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

    might be uploaded 14 hours ago, but the link is shared now to us

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

    prepared earlier and made private. made public only after the contest

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

    I see this type of comment in every editorial!

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

I do not understand the sentence: "Any difference |pi−qi| in our sum will be the difference of one element of R and one element of L." Sombody explain the meaning of it?

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

    That means either pi belongs to R and qi belongs to L, or pi belongs to L and qi belongs to R. Since this is true for all pi and qi, then the sum of |pi — qi| is the same as the sum of R — L

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

      The key point is that for any pair pi,qi it is true that one of the if from set L and the other from set R. Unfortunatly the sentence does not say that. Instead it states it as a property of the sum, which is confusing.

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

        can you please elaborate.. I cannot find the connection between L and R being sorted and this logic.

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

          L is per definion the lower half, and R the upper half. They are not sorted, but each element in L is smaller than each element in R.

          Then, if you have any permutation of all elements, cut them in two sets of same size and sort the two halfs/sets according to the statement. ie left one ascending, right one descenting.

          Then it turns out that for all p[i],q[i] the two values are from original L and other from R. That is true independend of any sum, so it is not a property of the sum, but a property of the way the sorting of the halfes is defined.

»
7 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Why does this give WA for (C) Division : https://codeforces.com/contest/1445/submission/97331021 ?

Fails at 7th Test (Passed the Pretests)

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

    In the first WA testcase, the numbers were $$$p=2^4 \times p_1 \times p_2$$$, $$$q=2 \times p_1$$$, where $$$p_1,p_2$$$ are some large primes. Your solution printed $$$2^4 \times p_2$$$, where the correct answer is $$$p_1 \times p_2$$$

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

    Mine WA at 18th T_T Link to solution

»
7 months ago, # |
  Vote: I like it +39 Vote: I do not like it

What does $$$O(n^2 \log n \ldots n^4)$$$ mean, wtf xd?

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

    Well... It is something between $$$n^2 \log n$$$ and $$$n^4$$$ :) It depends on your $$$T(n)$$$.

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

    It means that it is between $$$O(n^2 \log n)$$$ and $$$O(n^4)$$$ depending on your implementation. I agree, unexplained arbitrary notations should be avoided...

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

:)

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

Need Help in C: Given that p divisble by q : Can anybody tell me that is'nt it that if we multiply all divisors of q by p/q we will always get the largest integer if we only take those integers (divisor*p/q) which are not divisible by q.please correct if i am thinking wrong. link to my solution — https://codeforces.com/contest/1445/submission/97351609

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

    I think this idea is correct,only a small correction:- We will not only get the largest integer,we have to find the largest integer from all the possible integer we get from (divisor*p/q)

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

For Div1 Problem B, I just made random tc for n = 1, 2, 3 and solved on paper. Then I found that cost is always same and got AC xD

»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I misread non-increasing as non-decreasing in problem B and worked almost 2 hours on it(

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

    same

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

    I'm still confused with the solution provided above , can you please eloborate it !

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

      should i help or is it done by now?

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

        yes please explain, unable to understand it completely. Suppose there is someone who scored 'a' in first contest, and there is at least score 'b' in second contest, then how the person scoring c (c>=b) , and there in 100th position? shouldn't the person scoring 'b' present at the last position of the second contest. Did I miss something in the question?

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

Problem statements were really very straight forward...No time wasted in reading useless story and understanding problem statements

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

Can anyone help with counting $$$С_{2n}^{n}$$$ without overflow?

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

    Use Fermat's little theorem to find the modular inverse of n! via fast exponentiation.

    Basically k / x is congruent to ka (mod m) if m is prime and a=x^(m-2), so you can just find n! mod m and (2n)! mod m, and then use exponentiation to get (n!)^(m-2) mod m. The answer is just (2n)! mod m multiplied with (n!)^(m-2) mod m twice, modulo m the whole thing.

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

    You can use modular inverse and store them like this 97357968. I think it is a good template

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

    https://mathworld.wolfram.com/BinomialCoefficient.html

    in this link see the definition of Binomial coefficients for nonnegative integer y. For calculating 2n! use Fermat theorem

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

Div2 A, why do we have to check for all i? Like after sorting one array in descending order, shouldn't it be sufficient to check a[0]+b[0] and a[n-1]+b[n-1]? Can someone please give an example where this fail?

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

    You have to sort both the arrays & then reverse any one array and then check a[i]+b[i]

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

    I am curious about this as well.

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

    Let us consider the following test case

    1
    3 4
    1 3 3
    3 2 1
    

    Here, a is sorted in ascending order. And b is sorted in descending order. also, a[0]+b[0] = 4, which is equal to 4, and a[n-1]+b[n-1] = 4, which is equal to 4.

    However, a[1]+b[1] = 5, which is greater than 4

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

Did someone managed to solve div1B without the observation that any partition holds equal sum?

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

Can anyone please tell me why is my code giving wrong answer on test 18 for problem C- Division.

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

Thanks for update the rating fast!

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

Div2 A, instead of sorting the arrays like the tutorial, i checked if the sum of all elements in a and b is less than or equal n*x (Also automatically print "No" if any element is equal to x). It work on the 1st pretest, but got TLE on the 2nd one. Can someone show me where i did it wrong?

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

My rating goes bruh 'cause I forgot to reset res = 0 after each testcase when solving C lol

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

Can someone please explain solution of Problem Div2C/Div1A more clearly?

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

    cases

    1) if p%q!=0, then answer is p itself

    2) else we need a largest factor of p such that it is not divisible by q
    let's say the prime factorization of p is 2^x*3^y.. and for q as 2^a*3^b.., as p%q==0 then x>=a, y>=b and so on for every prime factor of p.

    Now is the trick/move, we can find possible x of p by removing some factor of p from prime factorization of p, for eg. if I remove 2^(x-a+1), you can see that p/2^(x-a+1) is no more divisible by q. That's it you have to try removing different prime's power and the one with maximum p/prime^(x-a+1) is the answer.

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

      Your explanation is really very much nice. Loved it and understood it just by reading once. Wanted to thank you and also I have a doubt. Won't the prime factorization takes O(sqrt(p)) time and won't it be of the order 10^9. Isn't the time constraint of 1-second means 10^8 operations?? Or finding the prime factorization of q will be enough??

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

      thanx...nice explanation

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it
What's wrong ???
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Have some patience, it will automatically update in some time.

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

    how did you enable dark mode??

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

      There are many extensions on the Chrome web store. I use "Stylish". It has both codeforces and codechef dark modes. Although they are not completely optimised for visibility.

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

Can someone explain me div2 B in easy way. I just can't understand the editorial. Thanks in Advance!!!

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

    I've marked down it here. Let me clarify in English as follows.

    We can prove the answer=max{a+b,c+d} from 2 aspects: ①prove answer>=max{a+b,c+d}②construct a scene that answer=max{a+b,c+d}.

    Let the 100th(of the sum score) person named x and his sum score to be p. It is clear that at most 99 people get a higher score than x. The highest 100 people in Problem 1 all have a sum score no less than a+b. It is impossible that they 100 all get the sum score higher than x, which means p is no less than a+b. Similarily we can get p is no less than c+d. So p is no less than max{a+b,c+d}.

    Then construct the scene: suppose the highest 100 people of Pro 1 all get a score in Pro 1 and b score in Pro 2, the highest 100 people of Pro 2 all get c score in Pro 2 and d score in Pro 1, and the others all get 0 in Pro 1 and 0 in Pro 2. Then p = max{a+b,c+d}.

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

Please give a detailed explanation of Div 2 C

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

    yeah me too, please someone explain!!

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

    I understood one approach. Here it is:
    if $$$p\% q\neq 0$$$ then $$$x=p$$$
    else we can represent $$$p$$$ and $$$q$$$ as follows:
    $$$p={p_1}^{k_1}*{p_2}^{k_2} \dots {p_y}^{k_y}*{p_{y+1}}^{k_{y+1}} \dots {p_m}^{k_m}$$$
    $$$q={p_1}^{l_1}*{p_2}^{l_2} \dots {p_y}^{l_y}$$$ where $$$p_1,p_2 \dots p_m$$$ are prime numbers.
    Here $$$k_1 \geq l_1, k_2 \geq l_2, \dots ,k_y \geq l_y$$$ because $$$p\% q=0$$$
    Now we have to take some factor of $$$p$$$ such that it is not divisible $$$q$$$. We can do this by taking some prime number power equal to one less than corresponding power in prime factorization of $$$q$$$ or you can say that we have to divide $$$p$$$ by that prime factor until $$$p$$$ is not divisible by $$$q$$$ . We can do this for all prime factors of $$$q$$$ and take the maximum one. Here is my submission

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

      Exactly my approach. But here's what happened to my submission

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

      You have done sieve upto 2e5+9 only right, how does it work when q is divisible by a prime number greater than N?

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

        What is N here?

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

          N used in nubir345's code = 2e5+9

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

            see this line:

            if(temp>1){
                v.eb(temp);
            }
            

            You should see that if there is such a prime then there can only one such prime with that of power 1. So after the loops, if temp>1 then it means that temp is a prime. And it is taken into consideration.

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

    I don't know if it will make more sense or not the way I thought is ,

    Let's call the power of a prime number in prime factorization of a number prime count.

    if a number(x) has at least one prime count greater than another number(y) than y%x!=0 Suppose , x=2*2*2*2*3

    and y=2*2*3*3*3*5

    then y/x will be something like (3*3*5)/2 which won't be a integer.

    so now for the given two numbers p & q , we need to find a 'x' that where p%x==0 & x%q!=0and we have to make it the biggest. So we start by making x=p (in another way saying taking all the primes in p) then checking for every prime in q can we make the prime count of q greater than that of x. We print which ever gives the largest number.

    vector<ll>primes;//all the primes in the prime factorization of q.
    for(ll i=0;i<primes.size();i++)
    {
        ll x=p;
    
        while(x%primes[i]==0)
        {
           x/=primes[i];
           if(x%q!=0)
           break;
        }
        
        ans=max(ans,x);
    
    }
    

    so suppose ,

    p=2*2*2*2*3

    q=2*2*2*3

    then x will be =2*2*3

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

Can anyone tell how the induction worked in A ? Like i did it in contest , was just curious about proof by induction !

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

    same here. I have no clue how they did it. Maybe I am too dumb to understand. Someone.. please help!

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

I passed Div1 D with $$$O(n^2C/bitset)$$$ using "malaysian knapsack", $$$C$$$ is the sum of length.

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

    What is a "malaysian knapsack"?

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

Can someone please explain div2 b in an easier way?

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

Div2 D/Div1 B is a beautiful problem, with a wonderful proof, thanks

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

    So sad I was not able to see this during contest. Intuition really plays a big factor in that I think. I straight went to calculating combinations.

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

Is codeforces using 32 bit platform architecture while checking problems solved in Python ? sys.maxsize giving wrong answer

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

1444B — Divide and SumF how to think like that ? can some one explain the way of thinking step by step ? Please

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

    Think of it this way-> Lets say the array is sorted, then the problem get reduced to choosing a subsequence of n elements, reverse it and then find the "cost". Now try to find which elements will always contribute a negative value ( that is -a[i]) and which will contribute a positive value (that is + a[i])............you will realise that elements from 1....n always contribute a negative value, while elements n+1.....2n contribute a positive value. In the end just multiply the final answer with the number of possible combinations.

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

In the editorial of Problem C, why q is not divisible by x?

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

proplem b was not clear enough and the proplem must be more than that

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

    yeah... It took me one hour to understand.

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

solution 1444B — I think it should be 2n choose n instead of n choose 2n

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

The problem B of div 1 is from a math olympiad book "lecture note on mathematical olympiad courses for junior section volume 1"

chapter 7 testing question B problem number 5

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

How can one solve Div2D if p and q are both sorted in non-decreasing order? (spent hours trying to upsolve this variant then saw the editorial and was like f**k me :P )

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

    same here. QAQ

    I came up with a $$$O(N^2)$$$ solution, which I calculated the appearance of each pair $$$(a_i,\ a_{i+1})$$$ (sorted). Wondering if it's possible to reduce it down to $$$O(N)$$$?

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Problem E appeared at the eleventh POI.

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

Can Anyone tell me "what are the prerequisites to solve div2 C and D problem? " Eagerly waiting for your answer...

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

Hello everyone. I understand the solution idea for problem D of Div 2 -- Divide and sum. But if anyone can explain how to get the intuition for that kind of idea would be really helpful. Thank you.

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

How do u calculate the time complexity for the solution of problem C ?

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

Can someone explain , why the solution got WA ? Thanks in Advance!! Problem — Div2A Link to my solution :https://codeforces.com/contest/1445/submission/97363313

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

    You didn't sort

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

      Yes you are right but it should still work because I started count of j from n-1 and started traversing array b (2nd array) from the back i.e. (n-1)th element , So it **must ** work fine. Thanks for replying.

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

        The problem got ACCEPTED when I removed the two for loops for checking if(a[i]==x) and b[i]==x and if true then print "NO" and return. But for the sake of learning I want to know what's wrong with this approach . Someone please help! Thanks.

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

    Sorry I didn't see in the problem that the arrays are already sorted.

    The problem is there are multiple cases in ONE test case, and if you are exiting the input with return (in one solve() iteration) once you found something >=x, the other numbers left in a,b array won't be read, therefore all the following inputs are wrong.

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

      ohh! yes you are right! Really, Thanks a lot!

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

There should be a special tag for problems like 2D/1B: LOL problem

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

The way I thought about problem DIV2-D : Every element either gets added or subtracted, if we consider individual contribution of elements.
Added : when the corresponding element in other sequence is lesser;
Subtracted: when the corresponding element in other sequence is greater;

Let's now see when an element is subtracted : Consider p, q be the non-decreasing and non-increasing sequences respectively;

=> p[1] <= p[2] <= ....... <= p[n] ------- (1)
=> q[1] >= q[2] >= ....... >= q[n] ------- (2)

Let's say p[i] contributes it's negative, i.e. it gets subtracted, Then we can say from (1) that number of elements greater than or equal to p[i] are n-i; Also since q[i] >= p[i] (as p[i] is being subtracted), all of (q[1], q[2] .... q[i]) >= p[i];
Now we can say that atleast (n-i) + i = n elements are greater or equal to p[i];

Similarly we can derive the condition for the other case !

Which proves that for a value to contributes it's negative it has to be in first half of the sorted array of all values !
Hope it helps, sorry if this approach is mentioned above, I dint read all the comments !

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

In Problem A- I don't understand why ma is less than or equals to q. Can someone explain how this constraint can be derived?

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

There is a spell mistake in solution of 1C.

Para.4, the last word "answer" was mistaken for "asnwer".

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

Fun Fact — sinus_070 was the first person to get an AC on 1B/2D. That's because he created the same problem on topcoder a few months ago. Click 1 Click 2

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

    Yeah, I think he also commented the same on the announcement blog.

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

In Div1C, there are lots of submissions AC using DSU to find the number of "bad pairs" instead. Could anyone explain a little bit about this solution? Thanks so much <3.

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

    DSU without path compression can cancel the previous merge. So you can add all the edge between two groups, using DSU to judge whether this group pair is 'bad', then delete the edges and restore the DSU.

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

      I tried to use dsu during the contest.But will "delete the edges and restore the DSU" get TLE?

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

        I think one edge can be added or deleted up to k times.(unless compress the connected component of same color)

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

          An edge which connect two different group would be added and deleted just once. Initially add all edges that the two node which it connect belong same group. Then select two group (ignore pairs which don't appear), add all edges between them, check if this pair valid, and delete these edge.

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

            Thank you very much . I understand.

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

    You may see the technique using DSU with rollback to check bi-graph in this problem 813F - Bipartite Checking.

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

    Wow thanks <3

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

Verdict shows accepted then why my rating decreases?

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

In problem C, just missed the case when q itself is a prime number, otherwise I would have got pupil.

https://codeforces.com/contest/1445/submission/97396204, with out any use of sieve of eratosthenes.

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

Great selection of questions. Liked it

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

Hello, Can anybody expand on the proof by induction for Array Rearrangement Problem (Div.2 A) ?

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

Can somebody please explain me the logic of div 2 C. Please..

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

    I can tell you my logic which got accepted. for q, i calculated it's prime factors and their powers (how many times a particular prime no occured) . i stored this in a vector of pairs and then checked whether p is divisible by all prime factors of q or not. if not then p is the ans. else suppose the power of a prime factor of q in p is p1 and in q it is p2. so, i divided p by pow(pf,p1) and multiplied by pow(pf,p2-1). i did this for every factor of q and calculated the maximum number formed out of them. sol link- https://codeforces.com/contest/1445/submission/97400076

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

      Can you please tell me what is wrong with my code I tried to implement the logic you told me, but its giving me WA. My submission:-97407542

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

      Can you please explain me a little why you are at first removing all the factor of that prime and after that multiplying it by p2-1, What's the intuition behind that?

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

        let q be of the form 2^p1*3^q1... .then q will divide p only if p has atleast power of 2(same implies to other faCTORS) equal to p1 in it . therefore we reduce power of 2 (for example) in p to p1-1 and then the number so formed will not be divisible by q.so we reduce power of such prime factor in p such that it reduces value of p by least amount .

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

Am I the only person who felt Div2-D is easier than Div2-C ?

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

    Div2-D is easy once you see that property that the sum is same for all permutations. If not, then not. Additionally the statement was formulated in a way that it was easy to get it wrong concerning the ordering of the two halfs L and R.

    Div2-C on the other hand is fairly clear, all that division and things. What else can we do than a prime factorization of the only value where we can do it? Once realized that it is not so hard to use the fatorization to construct ans.

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

Can anybody please explain me the editorial of problem A. Div2 ? I am not getting it please!

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

    Consider the smallest value in a[], min(a[]). Which one of b[] values would be "the best" to pair with that?

    Well, in b[] there is a biggest value, max(b[]). If $$$max(b[])+min(a[]) > x$$$, then there is obviously no solution.

    Else it is optimal to "get rid of max(b[])" by using it. Then repeat with the next smallest value in a[]... same again, you will pair it with the then biggest value in b[].

    You end sort a[] ascending, and b[] descending, and checking all pairs a[i]+b[i].

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

About 1444C - Team-Building, can anybody please explain me the sentence "If the path of the cycle in this component ends in the same side where it has started, then it has even length, and odd otherwise."? Thanks in advance.

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

How to solve 1444B - Divide and Sum if $$$f(p,q)$$$ set to be $$$f(p,q) = \sum_{i = 1}^n x_i y_i$$$

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

    Now, I know how to do it in $$$O(n^2 \log n)$$$ time complex and $$$O(n^2)$$$ space complex if $$$f(p, q)$$$ is bilinear.

    Just note that if $$$x_i$$$ belong to the left side, then $$$y_i$$$ belong to the right side, and vice verse.

    So we only have to consider $$$f_k(p, q) = \sum_{i = 1}^k x_i y_i$$$ with $$$x_k$$$ in the left side and $$$y_k$$$ in the right side.

    And the answer with be $$$\displaystyle 2 \sum_{p, q} \sum_{k = 1}^ n f_k(p,q)$$$

    In order to compute $$$\displaystyle \sum_{p, q} f_k(p, q)$$$, we only have to computer sum of $$$k$$$-subarry of left and right side. donated by $$$(l_1, \cdots, l_k)$$$ and $$$(r_1, \cdots, r_k)$$$, and then $$$\displaystyle \sum_{p, q} f_k(p, q) = \sum_{i = 1}^k l_i \cdot r_i$$$.

    the origin time complex is $$$O(n^3)$$$, but there is a convolution in above computation, so we can solve this problem with time complex $$$O(n^2 \log n)$$$ with the help of NFT.

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

Please help, I want to know where and why O(r) code for nCr mod p fails!!!

long long nCr(int n, int r){
    if(r>n){
        return 0;
    }
    int i= 0;
    int t =r;
    long long ans = 1;
    while(t--){
        ans = ( (ans*(n-i))/(i+1) ); // ans is always less than p, so it won't overflow, right??
        ans = ans%p;  
        i++;
    }
    return ans%p; 
}
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Division under mod does not work like that.

    For better implementation see https://cp-algorithms.com/combinatorics/binomial-coefficients.html

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

    since i + 1 may not divided by ans, since ans = ans % p

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

    Suppose a = 6, b = 2 and c = 5(we only care about b|a) We can find (a/b)%c=3, (a%c)/(b%c)%c=1/2, and (a/b)%c,(a%c)/(b%c)%c are often different.

    One occasion when they equal is b%c=1. Prove as follows: let b=qc+1 and a=tb=tqc+t, obviously (a/b)%c=t%c and (a%c)/(b%c)%c=t/1%c=t%c.

    Another equation[Fermat Little Theory] is for all integer k and a prime p we have k^p=1(mod p), so k^(p-1)*k=1(mod p).

    Thus we have (a/b)%p=((ab^(p-2))/(b^(p-1)))%p=ab^(p-2)%p, then use 2-base quick pow.

    For detail code you could concat by my passage and turn to the last page.

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

how to solve problem D if it was given that both p & q should be non-increasing order or non-decreasing order?

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

    sort the origin array $$$a$$$ and then the answer for both case is

    $$$ \displaystyle 2 \sum_{k = 1}^n \sum_{j = 2k}^{n + k} \binom{j - 1}{k - 1} \binom{2n - j}{n - k} a_j \quad - \quad 2 \sum_{k = 1}^n \sum_{i = k}^{2k - 1} \binom{i - 1}{k - 1} \binom{2n - i}{n - k} a_i $$$

    time complex $$$O(n^2)$$$

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

can someone explain Div2 B?

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

.

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

I am having some problems in 1445A — Array Rearrangment . Can't understand what is a and what is b

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

Can someone explain how to compress the bipartite component for each color in Div1 C. After DFS or BFS I can mark each node to 0 or 1 depending on its bipartite component. How can I use this marks to compress components to just a few nodes or I need something else?

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

What does this mean in the tutorial for "Elimination"?: The answer is at least max(a+b,d+c) because we have at least 100 participants with the sum of a+b and at least 100 participants with the sum of d+c

Why? Why dod "we have at least 100 participants with the sum of a+b and at least 100 with the sum of d+c"?

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

Can someone please explain why my div1-b solution is failing on test case — 8. Div1-B Solution

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

The answer for the test case (P=557307185726829409 && Q= 746530097)according to the judge is X=1 why cant we have X=674968226.