azureglow's blog

By azureglow, 4 months ago, translation, In English

Thanks for your participating!

author: 74TrAkToR, developer: marzipan, zwezdinv

Tutorial is loading...

author: OR_LOVe, developer: marzipan

Tutorial is loading...

author: azureglow, developer: marzipan

Tutorial is loading...

author: OR_LOVe, developer: zwezdinv

Tutorial is loading...

author: marzipan, developer: marzipan

Tutorial is loading...

author: zwezdinv, developer: zwezdinv

Tutorial is loading...

author: 74TrAkToR, developer: 74TrAkToR

Tutorial is loading...

author: platelet, developer: errorgorn

Tutorial is loading...
Tutorial of Good Bye 2023
  • Vote: I like it
  • +460
  • Vote: I do not like it

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

Ok, why is the editorial being downvoted now?

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

where is the tutorial for problem G?

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

Great contest! Hope you all have a good new year!!! :)

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

Please don't downvote the tutorial,it's always helpful.

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

downvote, if you liked editorial

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

Where is tutorial of G?

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

    It was removed since the author's solution was incorrect.

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

Bro expects to get upvotes

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

    C'mon, what's done is done. I wasn't a fan of the contest either but dwelling on it when the rating change has been established is not going to achieve anything.

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

Started as Good bye 2023, ended up with RIP 2023

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

Hello azureglow,

Really nice editorial!

Could you please add spoiler tags for each hint? Would be really helpful.

Thanks and wish you a Happy New Year!

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

Can some explain me the solution of E please some what elaborately?

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

    First, note that you can calculate the maximum answer by considering for each node: the two largest diff values from that node to any nodes in its subtree.

    So what we are doing is taking a tour of the entire tree, and updating the diff values from each node in a subtree to the current node that we are visiting. If the activity of our current node is x, then we add 1 to the diff values of all nodes in the subtree such that the sample path to them does not contain the activity x. This can be achieved by simply adding 1 to the diff values of the whole subtree, while just subtracting 1 from the subtrees of nodes in which the first additional instance of activity x is seen (basically if any node in the subtree has value x, we don't need to consider any of the nodes in this new nodes' subtree, as we have already accounted for the diff value change). We can find the nodes in a subtree with activity x in log time with a set, and after we account for the additional instances of x, we can remove them from the set, so each node is only considered at most once in this set. After we are done visiting a node, we add it to the set as well.

    Now to find the largest diff values for each subtree, we consider each child of the current visited node separately. We can do a range query over the entire subtree of each child to find the largest diff value, and multiply the two largest values of different children.

    So we want to support both range updates and range queries to the diff values, which is achieved with a lazy segtree. The segtree will contain the nodes in order of our tour, so subtrees will always be contiguous, and for each node we can simply store the range of its subtree in our segtree, which we then use for range updates and queries.

    I don't really have a sample code, but you can probably just look at any submission to E for an example of implementation.

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

      nice explanation, thanks!

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

      this may be a dumb question but why can't we just use a simple DFS to find "the two largest diff values from that node to any nodes in its subtree"

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

        If you do this for every subtree, then it takes n^2 time, which will TLE

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

          but since we DFS from the root of the entire tree, isn't it true that we will go through every subtree with a single DFS? it's like DP on tree (but without the second DFS)

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

            How would you "find the two largest diff values from that node to any nodes in its subtree" for every node with just a single dfs?

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

      I have implemented this but it gives WA on test case 88 of test 2. The problem is I'm not using sets to retrieve the nearest nodes in the subtree that match the current color. But I can't figure out what's wrong with my 'easy' approach though wherein once I reach any node of color v[i], I push_back the current node to the last parent that had v[i]. Can anyone help me please? Thank you!

      Submission: 239931057

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

        You have to update the value of mp[v[node]] to its original value when the whole subtree dfs is completed. For reference, you can see my solution.

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

At least, nice editorial in some ways, thank you.

However, I think, for a single day, we contestants have proven to you that, if you cannot do something, learn from others, learn from participants, learn from ones with a much higher rating (exclude me, though).

In that case, can you stop writing the long, tedious, lengthy, cumbersome, voluminous and confusing solution to H? It should be quite simple and can be described much shorter...

Also I have already seen a number of solutions to G which have been proven to have correct complexity. Why don't you show your original solution (you should have written one before the contest is started, shouldn't you) and try to analyze it with a similar method? Even if it is totally wrong, can it be better if you just ignore it and explain, there's a little mistake but our solution is proven by AC, ..., etc.? We want to see all your problemsetters' attitude towards everybody's anger!

And after all, let's don't downvote him. He has received too much. Please downvote 74TrAkToR as much as you want, sir, that's what you really should do —— ban him from coordinating shit contests.


Q: What is "H2. wMatrix Rank (Hard Version)"?

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

    I want to know the authors for each problem.

    And indeed, G has solutions, given by djq_cpp and ksun48

    G has WRONG pretests, and that affected ksun48 in the contest!

    For H, the official solution is ridiculously verbose. In the contest, I referred to MSE/A1117521 and MSE/A2147194. This is tractable for anyone studied linear algebra and combinatorics.


    BTW, I upvoted the tutorial, because the authors deserve it.

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

Can anyone explain me E? Here is what I understand so far, we will traverse all vertices, suppose we are at node x, we will consider this as our lca, then for each child subtree we just need the maximum distinct and second maximum distinct and the subtrees that we select must be different, then we multiply them both(also considering the color of current node x). It is written in the tutorial to use euler tour, suppose I am doing the euler tour, what should I add or subtract in the euler tour array?

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

    .

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

      and how will that help to get our answer, if you can please elaborate, that would be helpful.

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

      more specifically, when we are doing these +1 and -1 operations, I'm not getting how the children subtrees would give maximum distinct activities across a path and not for the whole child subtree

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

        I finally understand it. We need to maintain: the value diff(u, i) for all the node u's descendant node i. To avoid the repeated calculation of the same color, we need to subtract 1 for those that has the same color as u. Then we can calculate the first and second maximum. And finally for node u's parent v, diff(v, i) would be diff(u, i)+1, so we need to +1 to the subtree of u (assume that no repeated color exists. If yes, when visit v, we will subtract 1 for the repeated color). Here is my submission

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

nvm

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

Can anyone explain C to me, I couldn't understand it at all

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

    it's sad:(

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

    let there be m total numbers and total sum = sum out of those m numbers x numbers are odd not that which ever player's turn it is does not matter the new number added to the array is as ((a[i] + a[j]) / 2) / 2 is even so if a[i] and a[j] are of same parity the score will reamain same but if a[i] and a[j] are of different parity then the score decrease by 1 so for first player it is optimal to choose a[i] and a[j] of same parity (more specifically both should be odd) and for second player will chose ai and aj of different parity. you might have a question why first player tries to choose ai and aj both. it is because if he choose both odd then there will be fewer chance of the second player choose different parity numbers. so if there are X odd number then the first player will choose 2 odd numbers and insert an even number total score remain same SUM. X -> X — 2 now the second player will chose 1 odd and 1 even score will become SUM — 1 and X -> X — 3. now this pattern will continue till X >= 3 if X is 2 then first player will both odd numbers and the score remain same SUM. if X = 1 then the it has to be chosen atleast once so the score will decrease by 1 SUM -> SUM — 1. simple formula to calculate this is ans = (SUM — (X / 3) — ((X % 3) % 2)). hope this helps. here is my submission 239685245 to understand better what i'm saying. please forgive my english

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

      I have a similar code, can I send it to you?

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

        yes share it here

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          int a[N];
          void solve()
          {
              int n;
              cin>>n;
              for(int i=1;i<=n;i++) cin>>a[i];
              if(n==1){
                  cout<<a[1]<<endl;
                  return;
              }
              if(n==2){
                  cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<endl;
                  return;
              }
              cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<' ';
              ll even=0, odd=0;
              if(a[1]&1) odd+=a[1];
              else even+=a[1];
              if(a[2]&1) odd+=a[2];
              else even+=a[2];
          
              for(int i=3;i<=n;i++){
                  if(a[i]&1) odd+=a[i];
                  else even+=a[i];
                  if(odd&1) odd--;
                  else cout<<odd+even<<' ';
              }
          }
          

          What am I wrong here?

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

            as much as i can understand you code you subtracting 1 from ans for each odd number but have to subtract 1 for every 3 odd numbers

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

              if the sum of the odd numbers is odd, then I decrease the sum of the odd numbers by 1. You say it should be done every 3 odd numbers. I didn't understand why

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

                for even numbers no affect on the final result but for odd there is two steps done repletely which are

                1 — choose 2 odd and do the operation to don't waste it's value

                2 — choose 1 odd + 1 even and do operation to decrease the value by 1

                so here we get that there is decreasing by 1 per 3 odd numbers also you can check my answer 239675910

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

                  Thank You so much :)

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

                  input: 5 7 13 11 19 1

                  output: 7 20 30<- okay but after 48 why not 50 ? 7, 13, 11, 19 7+13 11+19 20+30=50 WHY ?!

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

                suppose there are 6 odd number 1 3 5 7 9 11 First -> remove 9 11 insert 20 A = {1 3 5 7 20} Second -> remove 7 20 insert 26 A = {1 3 5 26} First -> remove 3 5 insert 8 A = {1 26 8} Second -> remove 1 and 26 insert 26 A = {8 26} First -> remove 8 26 insert 34 A = {34} ans = 34 notice that there are 6 odd numbers first first 2 turns SUM decresed by 1 then for next 2 turn SUM decrease bu 1 ans = (36 — (6 / 3) — ((6 % 3) % 2)) = 34

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

                  I wrote it a little differently but it was accepted

                  int a[N];
                  void solve()
                  {
                      int n;
                      cin>>n;
                      for(int i=1;i<=n;i++) cin>>a[i];
                      if(n==1){
                          cout<<a[1]<<endl;
                          return;
                      }
                      if(n==2){
                          cout<<a[1]<<' '<<(ll)((a[1]+a[2])/2)*2<<endl;
                          return;
                      }
                      ll sum=0, odd=0;
                      for(int i=1;i<=n;i++){
                          sum+=a[i];
                          if(a[i]&1) odd++;
                          if(i==1) {
                              cout<<sum<<' ';
                          }
                          else{
                              if(odd==3) {
                                  --sum;
                                  odd=0;
                              }
                              if(sum&1) cout<<sum-1<<' ';
                              else cout<<sum<<' ';
                          }
                      }
                  }
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  great continue upsolving GL&HF

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

      Thank You so much too :)

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

      This was a very good explanation. Thank you. It was helpful.

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

Wanderfull round guys. People who are downvoting everything are a punch of noobs actually

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

[ Deleted ]

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

    can u stop whining everywhere bruv, we get it but this is the editorial

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

      [ Deleted ]

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

        wdym lmao, go cry about it in the announcement or something, there has already been enuff complaints , bruh this shit is past and irrelevant, in the editorial at least

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

          [ Deleted ]

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

            it's clear that you're Folka but in 2nd account

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

              I don't even have any other accounts!

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

                ok maybe I'm wrong idk

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

Just a request If you are going to make this contest unrated, do it this year itself please. I understand why most people are unhappy with the contest and therefore I am fine with it being converted to an unrated one. But I also don't want to end 2023 with a rating of 1383 and then wake up in 2024 seeing myself back at 1270. So this was just a request, hope you consider it :)

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

Can anyone prove this to me or explain why?

In this case, b=a⋅p, where p is the smallest prime factor of x. Then x=b⋅p=b⋅ba

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

    So (b mod a = 0) means that a is a divisor of b. If b and a are the first and second biggest divisors of some number x respectively and a is a divisor of b, a must be the greatest divisor of b. To show by contradiction: assume a isn't the greatest divisor of b. Then there is some middle number between a and b, call it c, which divides b. Since x % b = 0, x % c must be = 0, and a and b wouldn't be the first and second largest divisors of x.

    Now how do you find the greatest divisor of b? By dividing b by the smallest divisor of b, which will always be the smallest prime factor of b, call it p. So a = b/p, or b = ap.

    Now we show that, assuming b and a are the first and second greatest divisors of some number x and b % a = 0, one solution for x = bp.

    We will show that, assuming x = bp and b % a = 0, the second greatest divisor a = b/p.

    Since p is the smallest prime factor of b, p is also the smallest prime factor of bp. So in order to get the greatest divisor of bp, we just divide by p. Our greatest divisor of x = bp is b, which is what we want.

    Now we are left with b as the greatest divisor of x = bp and we can pull out another smallest prime factor of b to get b/p = a. And so a is then the second greatest divisor of bp. Or is it?

    What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?

    Well let's assume that the second greatest divisor, a, of x = bp is bp/s rather than bp/p^2. Recall that, in this case, a = bp/s must be the greatest divisor of b. So b/(bp/s) must be an integer. b/(bp/s) = s/p which is not an integer since s and p are both primes. So a = bp/s doesn't work. s can be generalized to any single prime factor of b where s > p.

    And of course, when dividing by two prime factors of bp to find a, it will always be correct to divide by the two smallest primes, which is p^2, otherwise a wouldn't be the second greatest divisor.

    Now we have shown that, for the case where b % a = 0, one solution for x = bp where p is the smallest prime factor of b. And since a is the greatest divisor of b, we can compute this easily by doing b^2/a.

    Hope this helps. I guessed the solution in the contest and thought about it later and realized it had a nice little proof.

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

      What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?

      here you mean to say a=bp/ps and not a=bp/s, right?

      please ignore this comment, i had misread and codeforces isn't letting me delete this

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

        I meant to say a = bp/s because if a were bp/ps = b/s then a wouldn't be the second greatest divisor of bp since there is b/p > b/s and bp % (b/p) = 0.

        In this part of the explanation I was basically showing why a cannot be bp/s.

        Edit: haha ok I see your edit too. Unfortunately codeforces doesn't let you delete comments lol

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

Don't just write the statement (for this case, the answer is this and for that it is that) . Prove your Solution ,that is what editorials are for.

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

My proof for problem H doesn't use any generating function and I find it more natural. I have very bad latex skills so I couldn't really manage to write everything so I'll link some pictures of my draft if someone is interested in the computations.

Disclaimer: I don't do math in english so my wording might be inaccurate sometimes (although I think you should roughly get the idea if you're familiar with the concepts I'll use)

The general idea is the following:

Let $$$S_r = {\{M \in \mathbf{Mn(\mathbf{F_q})} | rank(M) = r\}}$$$.

We are interested in the cardinal of $$$S_r$$$. As the constraint is on the rank of the matrix, it's pretty reasonable to solve this by considering equivalence classes.

Let's consider the group morphism:

$$$(P, Q) -> (M - > PMQ^{-1})$$$

where P and Q are in $$$\mathbf{GLn(\mathbf{F_q})}$$$.

It is a group action.

The orbits of this action are fixed by the rank (two matrixes are equivalent iff they have the same rank, this is a consequence of the rank theorem (more specifically, the fact that restricting a linear application to a supplementary of the Ker gives an isomorphism)).

Having this group action in mind, we get that

$$$|S_r| = \frac{|\mathbf{GLn(\mathbf{F_q})} \cdot \mathbf{GLn(\mathbf{F_q})}|}{|Stab_r|}$$$

(my cdot here should be an x but idk how to type this :/)

Now, to compute $$$|Stab_r|$$$, the easiest matrix to pick is $$$J_r$$$ (the canonical representant of the equivalence class of matrixes of rank r, a matrix that has 0 everywere and 1 on the first $$$r$$$ positions of the diagonal).

Now, $$$P, Q$$$ are in $$$Stab_r$$$ iff P Jr = Jr Q

I'm unable to type the whole thing because my latex is bad but essentially it is just about writing P and Q as block matrixes (with dimensions matching Jr), it gives an isomorphism between the stab and:

$$$GLr(Fq) \cdot GL_{n-r}(Fq) \cdot GL_{n-r}(Fq) \cdot M_{n, n - r}(Fq) \cdot M_{n - r, r}(Fq)$$$

(again the cdots should be x)

Now you're only left with some powers of q and some cardinal of $$$GLn(F_q)$$$ to compute.

This is easy to compute as we can see a matrix M in GLn(F_q) as a free family of n vectors of the space (F_q)^n (so a basis).

Thus, by the usual basis construction process, there are q^n — 1 possibilities for the first vector (everything except 0), then q^n — q possibilities for the second vector (everything that is not in the subspace generated by the first vector), then q^n — q^2 for the third etc

details about the cardinal of the stab

details about the final result

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

    Alternatively, to obtain a matrix $$$n \times m$$$ of rank r over $$$F_p$$$, you can :

    • Choose a subspace of $$$F_p^n$$$ of dimension r : there are $$$(p^n - 1) \cdots (p^n - p^{r - 1})$$$ ways to choose $$$r$$$ independent vectors, but each subspace is counted once for each of its basis, of which there are $$$(p^r - 1)\cdots (p^r - p^{r - 1})$$$

    • Given a basis of this subspace, you need to choose $$$m$$$ vectors in $$$F_q^r$$$ such that the resulting subspace is of dimension $$$r$$$, which is the same as choosing $$$r$$$ vectors in $$$F_q^m$$$ such that the resulting subspace is of dimension $$$r$$$ (this can be seen by swapping the rows and columns of the matrix). Therefore you have $$$(p^m - 1)\cdots(p^m - p^{r - 1})$$$ possibilities

    In the end, you get the wanted formula $$$f(n, m, r, p) = \displaystyle\prod_{j = 0}^{r - 1} \frac{(p^n - p^j)(p^m - p^j)}{p^r - p^j}$$$ which can be trivially calculated in $$$\mathcal{O}(r)$$$ and easily in $$$\mathcal{O}(1)$$$ amortized over $$$r = 0 \ldots k$$$

    By the way very nice draft pictures and even nicer profile picture !

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

      orz, I think this is roughly the same thing except you implicitly compute the cardinal of the stabilisator which makes things easier

      I guess the power of a Jambon beurre is unfathomable

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

What's the proof for n+2 in problem D? When we have 2 number rhat we should fill??

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

Here in problem B, I Understand the toturial and the code. But I don't know WHY ? okay we have two cases:

case 1 where (b%a != 0) , here LCM is the answer. but why? why X= LCM? Can't it be X>LCM or X<LCM ? WHY X=LCM ?

case 2 where (b%a == 0), Here we assume that there is a smallest factor P of X. Then we assume that this smallest factor of X makes the following rerlation (b= P.a) valid ..WHY ? Then we assume that X=b.P WHY?

IS there some mathimatical proof or only intuation?

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

    If d divides x then x/d divides also x. a and b are the biggest divisor smaller than x. Conversely x/a and x/b are the smallest divisor bigger than 1. Here two cases are possible : either they are two DIFFERENT prime factor p and q, this corresponds to case 1. Either they are p and p^2 which correspond two case 2.

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

      first, thank you bro for replying.

      I get that If there are two largest factors (a , b) of (X), Then (q=X/b ,p=X/a) are the two smallest factors.

      here you say "either they are two DIFFERENT prime factor p and q"

      but the question did not obligate a a&b to be primes, much less p,q. I didn't understand this point. please explain more

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

        Okay, you understand that $$$p$$$ and $$$q$$$ are the two smallest factors greater than $$$1$$$ of $$$x$$$.

        but the question did not obligate a a&b to be primes, much less p,q. I didn't understand this point. please explain more

        The fact that $$$p$$$ is prime and $$$q = p^2$$$ or $$$q$$$ is prime is just a general property of the two smallest factors greater than $$$1$$$ of any integer (that has two such factors). Here is the proof:

        Claim: $$$p$$$ is prime.

        Proof (by contradiction): Suppose $$$p$$$ is the smallest factor greater than $$$1$$$ of $$$x$$$ and $$$p$$$ is not prime. Since $$$p$$$ is not prime, it can be represented as $$$p = st$$$ for some integers $$$1 < s, t < p$$$. Now, $$$s$$$ is a factor of $$$p$$$ and $$$p$$$ is a factor of $$$x$$$; thus $$$s$$$ is a factor of $$$x$$$. But $$$s < p$$$, so $$$s$$$ is a smaller factor than $$$p$$$ — a contradiction. Thus, $$$p$$$ must be prime.

        Claim: Either $$$q = p^2$$$ or $$$q$$$ is prime.

        Proof (by contradiction): Suppose $$$q$$$ is the second smallest factor greater than $$$1$$$ of $$$x$$$, $$$q \ne p^2$$$ and $$$q$$$ is not prime. Since $$$q$$$ is not prime, it can be represented as $$$q = uv$$$ for some integers $$$1 < u, v < q$$$. If $$$u = p$$$ and $$$v = p$$$, then $$$q = p \cdot p = p^2$$$ — a contradiction. Otherwise, either $$$u \ne p$$$ or $$$v \ne p$$$. Now, both $$$u$$$ and $$$v$$$ are factors of $$$q$$$ and $$$q$$$ is a factor of $$$x$$$; thus $$$u$$$ and $$$v$$$ are factors of $$$x$$$. But $$$u < q$$$ and $$$v < q$$$, so $$$u$$$ and $$$v$$$ are smaller factors than $$$q$$$. One of them might be equal to $$$p$$$ which we already considered but one of them must be not equal to $$$p$$$ but instead, be a new, smaller factor of $$$x$$$ we didn't yet count — a contradiction, since $$$q$$$ was meant to be the second smallest factor. Thus, $$$q$$$ must be prime or $$$q = p^2$$$.

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

          @vgtcross fantastic! thank you, bro. I'm presuaded that p must be prime and q must be either prime or p^2.

          and form above, @123gjweq2 proved that ifb%a=0 and are the two greatest divisors of X, then a is the greatest divisor of b. Thenb/a gives the lowest divisor of b, which he assumed to be the lowest divisor of X which is p.

          which gives the following equation: p= b/a thenx/b=b/a then x=b^2/a. All is well, if we proved that assumtion that the lowest factor of b is the same as the lowest divisor of X.

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

    For case 1 it is the lcm of a and b due to the reason that the lcm will be the smallest number to exist for a and b such that both a and b are its factors. get it?? that is like the definition of lcm.

    for the second case we assume p is the smallest factor of X because it is given that b will be the largest factor of X. therefore by this relation b*p = x as b is the largest factor p has to be the smallest factor. for example for x = 64 its factors(except 1 and 34 ofcourse) are: 2, 4, 8, 16, 32. to make 64 we take one factor from left (2) and one from right (32) and so on.

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

      first, thank you bro for replying.

      LCM of a and b is the smallest number that can be devided by the two factor (a,b) of a givin number (X). But what problem B here asks us is to give him the number with largest two factors a,b . then we deducte that X can be devided by a and b. and LCM is the smallest number that can be divisable by a and b. But can we deducte that a and b will be the greatest divisors?

      I feel there is a strong relation, but I don't see why LCM MUST be used logically or mathimatically?

      here is an example, 63 has the following factors: 1 3 7 9 21 63 the largest two factors here (21,9) okay?

      but if I give you (7,9) with your definition, you will give me 63, but 63 has (21,9) as largest divisors not (7,9)

      do you see what I'm trying to get to?

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

        Your doubt is very valid. I see what you are trying to get to.
        However the problem statement is not asking for a $$$x$$$ in such a general sense for any given $$$a < b$$$. The statement is more like: "If I take the guarantee that $$$b$$$ and $$$a$$$ ARE CERTAINLY the two greatest divisors of some $$$x$$$. Can you find that $$$x$$$ for me ?"

        If you understood what I mean you will also understand that although you can calculate an answer for the case $$$(7,9)$$$, it is not a valid test input.
        That is to say the case $$$(7,9)$$$ is beyond the scope for the problem.

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

          first, Thank you @SXZZ5 for replying.

          you're right. I've noticed that a while after asking. Seizing the opportunityof of you being here, Could you tell me why we considered that in case b%a=0 that the lowest divisor of b is the same as lowest divosr of X (let it p) leading us to the solution that x= b.p= b.b/a.

          I knew the proof that a is the largest factor of b. So dividing b/a will give the lowest divisor of b. why must this lowest divisor apply to x itself as well?

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

            https://mirror.codeforces.com/blog/entry/124138?#comment-1103110 See this comment for an alternate way of arriving at the $$$x = b\cdot \frac{b}{a}$$$ solution for the case $$$b\;mod\;a = 0$$$.

            For the short answer to why smallest factor of $$$b$$$ should be the same as the smallest factor of $$$x$$$ consider the opposite case.
            Let's say the smallest factor of $$$x$$$ is smaller than that of $$$b$$$. But,then that would mean that $$$b$$$ is no longer the largest divisor of $$$x$$$, which is a contradiction to the requirement. This proves why smallest factor of $$$x$$$ cannot be smaller than that of $$$b$$$.

            Similarly consider the smallest factor of $$$x$$$ is larger than that of $$$b$$$. But, that is simply not possible. How can the smallest factor of $$$x$$$, be larger than the smallest factor of some intermediate factor $$$b$$$ of $$$x$$$ ?

            Thus, with these two contradictions smallest factor of $$$b$$$ must be the same as smallest factor of $$$x$$$.

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

As a failure after taking this contest, I realized that I feel more like a failure than a failure.

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

What does "And we still have $$$2$$$ numbers left, let's construct them as follows:$$$ 9...6...1 , 1...6...9$$$ where in the gaps between the digits there should be $$$(n−3)/2$$$ zeros, these will correspondingly be the squares of the numbers $$$1...3,3...1$$$ with $$$(n−3)/2$$$ zeros in the gaps between the digits." mean? I don't get it.(D. Mathematical Problem)

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

    for n=3 it corresponds to 13 and 31 whose square are 169 and 961, for n=5 to 103 and 301 whose squares are 10609 for n=7 to 1003 and 3001 whose square are 1006009 and 9006001 and so on

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

Thanks for a wonderful contest.

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

in problem D, you just tell a simple solution, where is the proof? where is it???

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

    $$$13^2=169,103^2=10609,130^2=16900$$$

    $$$(10^k+3)^2=10^{2k}+6\times 10^k+9$$$

    adding 00 to the end of number = adding 0 to the end of its square root

    961 is just the same

    We can generate $$$n-1$$$ numbers in this way. Add 196000000 to reach $$$n$$$.

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

    $$$(3\cdot10^x + 1)^2 = (3\cdot10^x)^2 + 2\cdot(3\cdot10^x)\cdot1 + 1^2 = 9\cdot10^{2x} + 6\cdot10^x + 1$$$

    Here, the number of zero digits between $$$3$$$ and $$$1$$$ in $$$3\cdot10^x$$$ is $$$x-1$$$.

    The numbers $$$9\cdot10^{2x}$$$ has $$$2x$$$ trailing zero, and the number $$$6\cdot10^x$$$ has $$$x+1$$$ digits. So when you add them, the number of zero digits between $$$9$$$ and $$$6$$$ is $$$2x - (x+1) = x-1$$$. Likewise, if you add up the whole thing, the number zero digits between $$$6$$$ and $$$1$$$ is $$$x-1$$$.

    So, we can say that numbers of form $$$9...6...1$$$ are always square of the integer $$$3...1$$$.

    Same proof for $$$1...6...9$$$.

    And you can always append two zeros to a number by multipling by $$$100$$$. If the original number is can be written as $$$x^2$$$, where $$$x$$$ is some integer, the resulting number will be $$$x^2 \cdot 10^2 = (10x)^2$$$, still a square of an integer.

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

I tried a lot but am not able to fit the solution of E in the time limit. Can someone please help me ?

Link — https://mirror.codeforces.com/contest/1916/submission/239811018

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

How would someone think of a solution for problem D during contest? It looks like a very specific observation to make.

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

    i just check all squares some size and find this, uisng c++)

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

    I did a brute force and find the answers for n=5. There are only 2 answers, one is the sample and the other has the multiset "16900". The fact that it contains two zeros made me feel it a key to the solution. Then everything is trivial.

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

    D was despicable. It looks like someone reverse-engineered the fact that you can add 0's between 1 and 3 and still get something that looks like 169, and built a whole problem about that. This type of problem is intensely annoying; while verifying and using the pattern is trivial, finding it is often torturous and menial.

    Personally the way I found it was by noticing that n is always odd, so maybe it doesn't work in evens because solution wants us to multiply by 100 which is a square, and then i permuted 0's in 16900 and realized oh hey it's still a square sometimes.

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

    Any square will be of the form: $$$(c_1.a+c_2.b)^2$$$
    -> $$$N_i$$$ = $$$( c_1^2\cdot a^2 + (2\cdot c_1c_2)\cdot (ab) + c_2^2\cdot b^2 )$$$.

    We'll keep $$$a,b$$$ as powers of $$$10$$$, so that the only digits in our answer are : $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2)$$$.

    By obvious reasons, $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2)$$$ should be unique and $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2) \lt 9$$$
    This gives us the value of $$$c_1,c_2$$$ to be either of $$$1,3$$$.

    Now, any number will have $$${1,6,9}$$$ and their length and relative position can be adjusted by using suitable powers of $$$10$$$ as values of $$$a,b$$$. The rest is trivial ig.

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

Alternative solution for D:

Here

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

In problem D, it seems that there is no answer for n which is even, can anyone prove this?

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

    I have found through brute force programs that there are existential answers when $$$n$$$ is partially even, for example when $$$n = 8$$$ we have the following squares numbers that fit the requirements:

    10582009
    19802500
    25090081
    25908100
    80910025
    81090025
    81902500
    95082001
    

    At the same time, it can be verified that $$$8$$$ is the minimum even number that satisfies solvability.

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

can problem E be done by dsu on tree?

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

Thanks for not restricting O(nmlog(n)) in F :)

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

    Approach smjhado yrr

    74traktor's editorial is Ultra annoying

    Seems as if he is explaining his soln to himself, rather than someone else :/

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

      My solution is based on the following observation(much like 74traktor):

      Given a graph G with no articulation point, with Vertex set $$$V$$$, for any $$$v$$$ $$$\in$$$ V, you can always find a neighbor $$$n_v$$$ of $$$v$$$ such that contracting $$$n_v$$$ to $$$v$$$ edge, also leads to a graph with no articulation point.

      Proof: Is a bit unstructured to write for now, will add it later.

      Given this we can get an answer by the following algorithm:

      Create a graph with all people as nodes and all friendly connections as edges. Given the above observation pick an arbitrary node $$$v$$$ and keep on contracting one of it's neighbors into $$$v$$$, $$$n_1 - 1$$$ times.

      Label all nodes contracted into $$$v$$$ as computer scientists, and rest as mathematicians.

      Why is this a valid solution?: Since we always merge two ends of an edge, all the nodes contracted in $$$v$$$ are connected, Hence all computer scientists are connected. Also since after all the contractions we still get a graph with no articulation points(by above property), removing $$$v$$$ from graph all other nodes are still connected, hence all mathematicians are also connected.

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

        Thanks a lot. Very well explained!

        I think we can prove it as follows: Lets consider the case where all nodes connected to v(heavy node) are cut vertices, and let these cut vertices form a set C. Lets condense any group of light(original) nodes into 1 node, which will still be a connected component if the a vertex in C is removed. Let these condensed nodes form a set D.

        The new graph has C + D + v vertices. We can see that no node in D, can connect 2 non-adjacent nodes in C, otherwise some vertex in C stops being cut. So since all nodes in D are only connecting adjacent nodes in C + v OR are leaves, we can remove them without hurting inter relation among nodes of C + v.

        Finally, we could see that all vertices in C, among themselves: (should be a connected component + shouldn't form a cycle = should be a tree) + can't be leaves = not possible

        Edit: one correction

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

There is also a more straightforward solution to Problem D.

Initially my aim was to find a pattern by obtaining some other answers through a brute force program.

But I found a set of squares whose size is much larger than $$$99$$$.

This means that when $$$n$$$ is small we can preprocess the answer or brute force enumerate it, and when $$$n$$$ is large we can just add the corresponding number of zeros to the end of the numbers in this set to get the answer.

Here is an example of a set of squares with size $$$143$$$ when $$$n = 11$$$.

Spoiler

Here's my submission from the competition:239697493

I found a legal set for $$$n = 13$$$, and chose to preprocess the answer rather than brute-force it in the program because the answer was larger for $$$n = 11$$$.

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

For the second question, Can anyone explain me how the p will be the smallest prime factor of x in b = a.p ? If you have some resources to study about it, share that too. Thanks in advance.

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

We want to find the number of ways to choose n vectors that spans exactly some k -dimensional vector space, but this is hard

It is not difficult. Consider some basis in a k-dimensional subspace and n vectors. Which decompositions are suitable for us? For the first vector we will be satisfied with everything except 0, i.e. $$$(p^n - 1)$$$. For the second vector, everything is suitable except the expansion in the first vector, multiplied by a constant, so that there are 2 linearly independent vectors, i.e. $$$(p^n-p)$$$. And so on, we get

$$$(p^n-1)(p^n-p)...(p^n-p^{k-1})$$$

I'm sorry for my English(

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

Nice contest. Was problem E solvable in java with given time limits? zwezdinv. I think I did exactly what's mentioned in editorial in 239700440, but couldn't get it to pass.

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

Bad round but good editorial.

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

video sol for ( Problem E — Happy Life in University ) ( Hindi Audio ): Youtube Link

In an interesting way such that a newbie could also understand.

Topic used : Euler Tour, Segment Tree Lazy RMQ (Range maximum query)) ;

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

D could be made pretty easy using precomputation of squares on a constraint of 1e6. and then usign it in every case to get all values corresponding to given length

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

Can anyone tell me where can I learn math for Cp? This round made me realize that I should learn.

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

I have understood D solution. But is there any other methods to do it or the more relevant question, how do I reach to such a solution. Like which topics shall i cover more?

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

In problem D, for the alternate solution, how would you know that at n = 11 you can generate 99 such answers? And how would you generate the squares in O(sqrt(10^n))?

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

Can anyone explain F? I did dfs from each node and cut whenever a dfs subtree has size n1 or n2 (240093733) and it says MLE.

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

Alternative way to think of the observation for Problem B for the case when $$$b\;mod\;a = 0$$$.

First, lets step back and think about $$$b$$$. If it has to be the biggest factor of $$$x$$$, what do you know about the quotient $$$x/b$$$ ?. We can claim that the quotient must be prime.
Proof by contradiction: If the quotient is composite, we can easily shift even one prime factor in the factorisation of the quotient into $$$b$$$ to get a yet bigger factor $$$b'$$$ of $$$x$$$. That would be a contradiction.

On similar lines what should be the quotient $$$x/a$$$ if $$$a$$$ has to be the second largest factor of $$$x$$$ ? Well, it is clear that the quotient can be a prime or a composite both. If it is a prime, it must be different from $$$x/b$$$ and the rest is fine.

Let's focus on the case if $$$x/a$$$ is composite. For this case, we can claim that $$$a$$$ must divide $$$b$$$ and that the corresponding quotient must be a prime.
Proof by contradiction: Assuming the quotient is composite, we can certainly "shift" some factors into $$$a$$$ so as to get a larger $$$a'$$$. This possibilty of getting a larger $$$a'$$$ is infact unavoidable/guaranteed but that would defeat the constraints of the problem. So, the only way to make it work is iff this $$$a' = b$$$ and that this is the only possible $$$a'$$$. This inturn implies that $$$b/a$$$ must be prime (because then there will only be a single prime factor available for the "shifting" into $$$a$$$. This way, $$$a' = b$$$ is deterministic/guaranteed). In any other case(that is $$$b/a$$$ being composite) there is another $$$a_{alt}$$$ between $$$a'$$$ and $$$b$$$.

So, till now we are convinced that if $$$(b\;mod\;a = 0)$$$ then $$$(b/a)$$$ must be a prime number. This means we can choose any multiple of $$$b$$$ and that will still be divisible by $$$a$$$ too. But also by arguments in point 1, we will/can only consider prime-multiples of $$$b$$$ as prospective values of $$$x$$$.

Let us say we took $$$x = y\cdot b$$$ where $$$y$$$ is some prime. Also, lets say that $$$b/a = z$$$ where $$$z$$$ is some other prime (WHICH WE JUST PROVED). Now, we claim that it must be that $$$z = y$$$ or else $$$a$$$ won't be the second largest divisor of the chosen $$$x$$$.
Proof by contradiction: Note that $$$b \cdot y = a\cdot z\cdot y$$$. Assume $$$y \neq z$$$ then that would mean $$$a\cdot y$$$ divides $$$x$$$. But $$$a\cdot y > a$$$ which means we just found a new divisor between $$$a$$$ and $$$b$$$. This is a contradiction to the requirement of $$$a$$$ being second largest divisor of $$$x$$$.

With this in mind, which prime-multiple of $$$b$$$ should we choose as the appropriate $$$x$$$ ? That exact-same prime which we get as the quotient $$$b/a$$$. If we don't do so, $$$a$$$ will not be the second largest divisor for any other prime-multiple of $$$b$$$.

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

In problem F: 'Otherwise, consider a cut vertex such that, if removed, at least one of the resulting components will not have any other cut vertices.' How do we prove that such cut vertex exists?

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

    I came across the same question after reading the editorial
    I'll write a stricter proof

    Consider two sets of vertices $$$L$$$ and $$$R$$$, where $$$L \cup R = V$$$, $$$L \cap R = \varnothing$$$, $$$L = {1}$$$ at the beginning and $$$R$$$ is connected since there are no cut points. Now we can always choose a vertex $$$v \in R$$$, delete it and add it to $$$L$$$, while $$$L$$$ and $$$R$$$ remain connected (which is the invariant).

    Let's look at non-cut vertices in $$$R$$$. If $$$L$$$ is connected to any, we can choose one arbitrarily and the invariant holds.

    Now, let's suppose all the neighbors of $$$L$$$ in $$$R$$$ are cut vertices. If not all cut vertices are neighbors of $$$L$$$, any vertex that is not a neighbor of $$$L$$$ is a cut vertex in the starting graph, which contradicts the statement.
    Otherwise, all cut vertices are neighbors of $$$L$$$ and we can build a tree on cut vertices and choose any list in this tree. This cut vertex is also a cut vertex in the starting graph, since the hanging strongly connected component is not connected to $$$L$$$ or other vertices in $$$R$$$, which contradicts the statement.

    QED

    74TrAkToR, maybe improve the editorial for problem F, please

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

solution to problem C

In each operation, there is a chance that the total sum (sum) could be reduced by 1. Player One's goal is to keep the sum as large as possible; Player Two's goal is to keep the sum as small as possible.

All actions of Player One aim to avoid triggering the operation that reduces 1; there are two conditions to achieve this: 1. Select two odd numbers; 2. Select two even numbers. Both of these operations will increase the value of even numbers in the array by 1;

Player Two aims to trigger the operation that reduces 1 as much as possible. There is only one condition to achieve this—select an odd and an even number. Since Player One's action will surely leave an even number, Player Two can select an odd number and the even number left over from Player One's previous round, triggering the operation that reduces 1 as long as there are odd numbers in the array. For this reason, Player One needs to reduce the number of odd numbers as much as possible. The optimal operation for Player One is to select two odd numbers because this can consume the largest number of odd numbers, and an even number must be left after this operation.

If there are still odd numbers in the array at this point, Player Two can trigger the operation that reduces 1. Therefore, during this entire process, if there are 3 odd numbers, Player Two can most certainly trigger the operation that reduces 1.

Through this analysis, we can understand that under the optimal operation of both players, the operation that reduces 1 must be triggered for every 3 odd numbers. Thus, all we have to calculate is the number of groups of three odd numbers, which is certainly the total loss in this game. At the same time, we need to consider whether the odd numbers left after grouping three odd numbers into a group will cause new losses. In this case, the number of odd numbers could only be 0, 1, or 2. We also need to consider whose turn it is at this time. Since Player One eliminates two odd numbers and Player Two eliminates one odd number to complete a group, any remaining odd numbers should be Player One's turn. Therefore, in this case, when the number of odd numbers is 0 or 2, the optimal solution for Player One is to eliminate the two odd numbers. When the number of odd numbers is 1, no matter whether the player chooses to eliminate it immediately (causing the sum to be reduced by 1) or escape and leave it to Player Two (who will certainly choose this odd number and the even number left from the last operation, causing the sum to be reduced by 1), the player will inevitably bear the cost of reducing the sum by 1. Thus, we learn that the answer for every k numbers is pre[k] — odd_num/3 + ((odd_num%3)&1).

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

Can someone please explain B? Also in the tutorial they said "First case: b mod a = 0" but 3%2 is not equal to 0. Please help me out

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

    mod 3 is not 0 then we will follow the second case ans = a*b/gcd(a,b)

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

In B, I had a doubt, when b % a == 0, how do we know p is the smallest prime factor of x where p = b / a. Is it because a and b are largest divisor ?

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

Sorry, but there is an error in the editorial for problem D: it should say $$$(n-1)/2$$$ zeros instead of $$$(n-3)/2$$$ zeros. It sounds unimportant but this typo could confuse some people.

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

1916B - Two Divisors 240657753 My code was like that

If (LCM(A,B)==B) then print:=(B/A)*LCM(A<B) else print:= LCM(A<B)

The issue arises when A = 15 and B = 60, resulting in an output of 240. However, for 240, A should be 80, B should be 120. indicating that the solution is not optimal. Can anyone suggest an optimal solution?

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

    The issue is that your input is not a valid case. There is no integer such that its two greatest divisors are 15 and 60. For anything to have a divisor of 60, it will have a divisor of 30, making your case invalid.

    That being said, the code works successfully, and outputs the right value of 240 for the proper inputs A = 80, B = 120.

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

I have a similar code, can I send it to you?

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

I have a similar code, can I send it to you?

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

interesting

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

244455567 Can someone help me why this greedy algorithm doesnt work. I cant check the test inputs because ""wrong answer 30955th numbers differ — expected: '4', found: '6'""

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

In problem b, in second case, I can't understand this "gcd(a, b) = x / p.q". Help me please!