ProgSlacking's blog

Codeforces Round #641 Editorial
By ProgSlacking, 3 weeks ago, In English,

You can view Chinese editorial here: https://www.luogu.com.cn/blog/Caro23333/codeforces-round-641-zhong-wen-ti-xie

Div2.A Problem and editorial by ProgSlacking

Editorial
Code

Div2.B Problem and editorial by ProgSlacking

Editorial
Code

Div1.A Problem and editorial by mydiplomacy

Editorial
Code

Div1.B Problem and editorial by A.K.E.E.

Editorial
Code

Div1.C Problem and editorial by A.K.E.E.

Editorial
Code

Div1.D Problem and editorial by Fulisike

Part of solution by Elegia

Editorial
Code

Div1.E Problem and editorial by A.K.E.E.

Editorial
Code

Div1.F Problem and editorial by Fulisike

Hard version solution by Elegia

Editorial for easy version
Code
Editorial for hard version
Code

You can also view Div1.F editorial by Elegia here: https://codeforces.com/blog/entry/77280

Anyway, hope you like these problems and thank you for participating!

 
 
 
 
  • Vote: I like it
  • +291
  • Vote: I do not like it

Comments Comments (309)
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

Video Editorial for Div2C/Div1A

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

    Thanks for the video tutorial! What is the time complexity of calculating the prime factors of n numbers in your code for Div1A?

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

      $$$O(VALMAX$$$ $$$log$$$ $$$VALMAX)$$$, where $$$VALMAX$$$ is the biggest value in input

      → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    stefdasca you being an orange we expect you to upload atleast Div1B&C

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

      I never upload right after contests video solutions for tasks I'm not 100% sure I used a right approach.

      As an example, I FST'd Div1B yesterday, it's easy to guess what everyone would've told me in comments soon after if I uploaded them.

      Also, I'm planning on doing video tutorials for more problems, but I don't have much time for this right now.

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -38 Vote: I do not like it

        There are few blue coders who upload video editorials for Div1A(very well explained) so i would request you to upload Div1B&C instead of Div1A.

        If you are not 100% sure about your submission then you could just comment down something when editorial is out and if your submission gets accepted, edit the comment and post the link of the video.

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

      lol pupils should not expect anything. He can solve that , he just makes them for lower rated people like you , so you should thank him.

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

    i kept on MLEing for problem C, although I had the right idea the whole time (i think I did solution 2). What can you use to calculate the number of pairs besides stuff like maps and arraylists, which MLE? Is there a way to do it in o(1) space? I literally spent 1h30m trying to implement this goddamn problem and I don't think I've ever been more tilted at a codeforces problem than this one https://codeforces.com/contest/1350/submission/80029151

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

Thanks for Editorial. Really enjoyed the contest. Problems were very interesting

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

    Video editorial Div2 B

    Video editorial Div 2C/Div1A.

    Video Editorial Div2D/Div1B

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

      Thank you!

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

      Great approach.

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

      striver_79 Great Job Buddy!

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

      Thank you, very informative one. Is it some identity or you found the pattern during the contest?As I was struggling to find sets s1,s2,..sn.

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

      can you please tell how to recognize that Div2 B was a DP problem?Thank you in advance.

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

        well i am not a experience programmer though i think i can help here you. See we are going throught multiple of each index because that is the only value which is divisible by particular index. Now supoose we start from index 1 then all multiple would be n — 1 because 1 can divide all of them so we will fist save all the answer which satisfy the condition that is arr[i] > arr[1]. Now when we move to second index then multiple of 2 would be 4,6, 8.... and so on so if any of these indces satisfy the condition then the answer would be update by the previous answer from index 1 + current index and new index would be added too in this. So here we can clearly see that previosly we saved answer when we checking of 1's multiple and now we got new index which is divided by 2 so these sequence would looks like 1, 2, and multiple of 2 where 1, 2 sequecne answer was already saved in dp. Sorry for any grammatical mistake can't give time to correct it any try to find something else if it can't help. I could try only.

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

      In the tutorial u have devided 10*8 by their GCD which returns the GCD of the LCMs of the pair. How it works , please? striver_79

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

        Read about GCD's associative property or checkout the comments in my video, I have given an explanation.

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

Good problems!

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

nice problem set (math)

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

can anyone plz check my solution for div2 C (it got accepted during contest) https://codeforces.com/contest/1350/submission/79877064

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

Anyone else solved D1C using bitsets?

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

    Bitsets are expected to get MLE or something else. I'm curious about your solution XD

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

      Well, I have noticed two facts (both are proven in the editorial):

      1. Preperiod of the grid is at most $$$n + m$$$.
      2. Period of the grid is at most $$$2$$$.

      So I have written a function go(vector<bitset<1000>>) which would give me the next iteration in $$$O(nm/64)$$$. It is not hard to come up with a boolean function $$$f(val, l, r, d, u)$$$ which would give the result for the next iteration ($$$l, r, d, u$$$ are the values of adjacent cells). So using this formula we can compute a whole row in $$$O(m / 64)$$$.

      Now for queries with $$$p < n + m$$$ I use scanline, and for $$$p \geq n + m$$$ I look at the parity. So I am using $$$O(nm(n + m)/64 + t)$$$ time and $$$O(nm/64 + t)$$$ memory.

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

Another good Chinese round !

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

In d1C, you have used grid instead of cell, for example

for a bad grid $$$\dots$$$

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

save some problems for IMO

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

I would like to give an interesting (although not optimal in terms of complexity) for div 1C. Observe the grid will "converge" to a length 2 cycle after some sequence of move. You can find that out by writing a brute force solution. With some guessing, you may find out you need around $$$n + m$$$ steps to converge, which is consistent with the results in the editorial.

The problem is brute force requires $$$O(nm(n + m) + t)$$$ which is too slow. However, we can speed up the brute force using bitset. By shifting and some bitwise operations, you can check and update the whole row at once. You may also want to use the rolling array technique to fit in the memory limit. The complexity after optimization would be still $$$O(nm(n + m) + t)$$$ but with an additional $$$1/64$$$ constant, which should fit in the time limit.

79891996 The solution is badly written, serve as proof-of-concept only.

Fun fact: with the rolling array technique, my solution uses less memory compared to most solutions.

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

    Yeah, we once wanted to hack your solution by modifying ML or TL, but in the end we decided to only hack bitset solutions which are bad at optimizing their memory usage.

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

      I don't really think you can hack this solution (not hacking a lot of bfs solutions). In my experience $$$O(n^3/64)$$$ works noticeably faster than $$$O(n^2logn)$$$ for $$$n = 5000$$$.

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

    Could you explain a bit about what you mean by rolling array technique ? Prelimnary google search doesn't seem to give anything worthy.

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

      I think it's somewhat the same as scanline. You can understand it this way: you only need to store one iteration at a time. When you've answered all the queries for the iteration $$$p$$$, you can change it to the iteration $$$p + 1$$$.

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

        Okay, got it. Had a look at STommydx solution. Basically offline query sorting, till N+M maximum. interesing, thanks.

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

What does this sentence means?

Let $$$E_x$$$ be the sum of probability times time when the game end up with all biscuits are owned by the x-th person

Nice editorial but i wish your English was stronger :(.

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

    Suppose $$$S_x$$$ is the set containing all the situations that the game end up with all biscuits in $$$x$$$-th player. And for a situation $$$t$$$ we denote its probability to occur by $$$P(t)$$$ and its time by $$$L(t)$$$, then $$$E_x = \sum\limits_{t\in S_x} P(t)L(t)$$$.

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

      Thanks for the comment, now i understand it better(you can use "multiplied by" instead of "times").

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

Can someone explain Div1D better? Thanks

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

    I used Generating Function to solve, and maybe it is easier to come up with such solution if you are familiar with them.

    First, let $$$a_k$$$ be the probability of ending the game in $$$x$$$ turns. Let $$$A(x) = \sum_{k=0}^{\infty} a_kx^k$$$. Then our objective is to find $$$A'(1)$$$, where $$$A'(x)$$$ is the derivative of $$$A(x)$$$.

    Finding $$$A(x)$$$ is hard, so we should multiply something to it to make it easier. From now on, for convinience, assume the game doesnt end even if the ending state occurs. Let $$$b_k$$$ be the probability of one person having all biscuits after moving k steps starting with the state, and that it is the first time that person owns all biscuits. Let $$$B(x) = \sum_{k=0}^{\infty} b_kx^k$$$. Then, we realise that $$$A(x)B(x)$$$ is the generating function of the sequence $$$c$$$, where $$$c_k$$$ is the probability of a person owning all biscuits after $$$k$$$ steps (also enforce that it is the first time that person owns all biscuits). Denote generating function of $$$c$$$ as $$$C(x)$$$.

    $$$C(x)$$$ can be written as sum of $$$D_i(x)$$$, where $$$D_i(x)$$$ is the generating function for the sequence $$$d_{i,k}$$$, where $$$d_{i,k}$$$ is the number of ways to reach the state that $$$i$$$-th person has all the biscuits the first time after $$$k$$$ steps. Consider $$$D_i'(1)$$$, which is the expected number of steps to reach that state. We realise that this value is only dependent of $$$a_i$$$, $$$n$$$, and total number of biscuits. Let's denote it as $$$e_{a_i}$$$. The $$$e$$$ forms a Markov Chain and you can solve all values of $$$e$$$ in $$$O(n*log)$$$.

    Finally we will go back to the original formula, $$$A(x)=\frac{\sum_{k=1}^{n} D_k(x)}{B(x)}$$$.

    Then, $$$A'(1)$$$

    $$$= \frac{B(1)(\sum_{k=1}^{n} D_k'(1))-(\sum_{k=1}^{n} D_k(1))B'(1)}{B(1)^2}$$$

    $$$= \frac{n(\sum_{k=1}^{n} e_{a_i})-n(n-1)e_0}{n^2}$$$

    Which can be computed in $$$O(N)$$$ easily.

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

      This is pretty much the same as the editorial.

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

      is there a non generating fn solution, or pretty much you have to calculate a derivative to get the formula?

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

      Can you help me with the formula for calculating e, I found Markov chains, but we have 3 * 10 ^ 5 different states, and this is a fairly large matrix, please

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

There is a 1200 points difference between problem C and problem D. Has anyone seen a bigger difference?

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

Tricky Questions

I was fooled by the D2/B problem into n^2 DP, it blocked my mind.

After that my confidence was lost and finally I gave up. and now I found out how iterations were made in the problem and it is kind of like the iteration we make while sieving primes.

Overall, it is depressing!!!

Still, I would like to appreciate and say very good work done by the writer!!

Thank you for the contest

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

    You may feel depressed but you learned something. When you come upon this pattern again, you will find it and solve a problem. Good luck in the future!

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

      solution link

      I used the n*sqrt(n) but I got WA on pretest 2 could you please tell me where I went wrong ? sxpg

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        ← Rev. 4   Vote: I like it -7 Vote: I do not like it

        You should initialize count[] with all values equal to 1 instead of 0. j<=sqrt(i) is risky too, sqrt gives float and can create numerical errors. For example, sqrt(25) might give 4.999999997 instead of 5 and you will miss this 5. Better to check j*j<=i

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

          thank you, after making those changes I got AC.

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

          bro that hint even helped me....Now i initialized the array with 1 and its accepted. Just one change...!! That had put me into depression in live contest ;-<

          → Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you help me with my submission? I don't understand how it gets TLE. https://codeforces.com/contest/1350/submission/81596038

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

Another interesting solution for Div2 C is that the value of gcd of all pairs whose smallest index is 'i' is LCM(a[i], GCD of all a[j] s.t. j>i). The value corresponding to "GCD of all a[j] s.t. j>i" can be easily found using suffix array.

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

    You can use prefix gcd https://codeforces.com/contest/1349/submission/79820899

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it -17 Vote: I do not like it

      I did it according to your solution but getting WA. Please have a look :

      #include<bits/stdc++.h> #define ll long long #define pb push_back #define rep(i,a,n) for(ll i=a;i<n;i++) #define per(i,a,n) for(ll i=n-1;i>=a;i--) #define fi first #define se second #define maxi LONG_LONG_MAX #define maxn 200005 #define VL vector #define all(x) (x).begin(),(x).end() #define flash ios_base::sync_with_stdio(false);cin.tie(NULL);

      using namespace std;

      ll lc(ll a,ll b) { return a/__gcd(a,b) * b; }

      int main() { flash

      ll n;
cin>>n;

VL a;

rep(i,0,n)
{
  ll x;
  cin>>x;
  a.pb(x);
}

ll g=0,res=0;

rep(i,0,n)
{
  res=__gcd(res,lc(a[i],g));
  g=__gcd(g,a[i]);
}

cout<<res<<"\n";

      }

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

      Wow, that's elegant! Could you explain how this works? Not sure how to intuitively think about it in terms of prefix gcd.

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

        It's the same as jatinmunjal2k's solution but with < instead of > so prefix instead of suffix.

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

    value of gcd of all pairs whose smallest index is 'i' is LCM(a[i], GCD of all a[j] s.t. j>i)

    do we get this through observation or there is some mathematical reason behind it

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

In div2C, doing what is said in the problem statement sufficed: 79904920 (After the contest but I am kind of disappointed)

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

please insert sample code of editorials , that will be better to understand .

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

Can someone explain the transformation formula in easy, mostly non mathematical, words?

$$$f_i = \max\limits_{j\mid i, s_j<s_i} {f_j + 1}$$$

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

    It means maximum $$$f_j$$$ for all $$$j$$$ such that $$$j$$$ divides $$$i$$$ and $$$s_j < s_i$$$.

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

Good problems(especially div2d)! Thanks!

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

Div 2B can't we solve 2B by making an unidirectional graph and finding the longest path?? can anyone see my solution and tell me what's wrong with that.(my submission 79865870)

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

    We can, your solution doesn't calculate longest path correctly, i prefer using dp to calculate it.

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

      can you please tell me what's wrong with my longest path calculation.

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

        I think the check of the vis[] in dfs function is not correct. It should be removed there, allways traverse into child node.

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

    DFS would work, but not with a "visited" array. You DFS from 2 and tick 12 as visited, then you DFS from 3 and miss an edge from 3 to 12.

    Also, I think it might get TLE.

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

      now i see whats wrong. Thanks for the help

      but it got accepted and not tle luckily

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

        Share your dfs approach, I was thinking to solve it using dfs

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

          79911714

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

            @nnsp635, I implemented your approach but getting TLE on 34th test case, need help, Thanks 79948181

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

              consider using array of vectors instead of map<int,vector> because every-time you want the vector associated to a node,the map has to search for the key and consuming time. (and make the array of vectors global so that you don't have to pass it every-time)

              anyway use dp for better results

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

    If you are curious how to use DFS for it, run a DFS and if you are at vertex $$$v$$$, then set $$$ans_v$$$ equal to $$$\max\limits_{u\,\in\, g_v} ans_u + 1$$$, do it right before ending the function.

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

      I read in a book "Algorithms" by Dasgupta & Papadimitriou that every DP problem has a directed acyclic graph hidden in it. This is a nice example!

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

Can anybody explain what that weird symbols mean in Div.1 B solution?

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

    $$$∃$$$ means for at least one $$$\dots$$$

    $$$∀$$$ means for all $$$\dots$$$

    For example $$$∀ 1 \le i \le n, a_i = 0$$$ means for all $$$i(1 \le i \le n)$$$, $$$a_i$$$ is equal to 0 but $$$∃ 1 \le i \le n, a_i = 0$$$ means for at least one of $$$i(1 \le i \le n)$$$, $$$a_i$$$ is equal to 0.

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

      Why is this approach wrong for Div2B? int dp[n+1]={0}; dp[1]=1; for(i=2;i<n+1;i++) { vectorv; for(j=1;j*j<=i;j++) { if(i%j==0) { v.pb(j); if(i/j!=j) v.pb(i/j); } } for(j=0;j<v.size();j++) { if(a[v[j]]<a[i]) { dp[i]=max(dp[i],dp[v[j]]+1); } } } int mx=0; for(i=1;i<n+1;i++) { mx=max(dp[i],mx); } cout<<mx<<"\n";

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

        Change int dp[n+1] = {0}; to int dp[n+1] = {1} :), also i prefer to iterate over $$$n+1$$$ and set $$$dp_i$$$ equal to 1 by myself.

        → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +40 Vote: I do not like it

I know I was a little rude, but "Read problem statement" kinda pissed me off. Apologies to the setters but the statement was definitely ambiguous.

Div1 C "no adjacent cells with the same color as this cell", I interpreted initially as any two adjacent cells anywhere in matrix. It said nothing about "no adjacent cells to it".

wtf

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

    If you felt uncomfortable with that, we're sorry. But it is a quick option to answer a question, just like Yes, No, No comments and Question is unclear. So I think the usage of this is also reasonable.

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

    +1
    English is bad in this statement. Simply writing "A black cell changes if at least one of its adjacent cell is black and same for white." was sufficient.
    Even after understanding it, I had to read it whenever I need this condition while writing soln.

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

      That's so true. Although the meaning of the statement (condition) is clear for me, I messed up the condition multiple times while debugging. I have to reread the condition again and again just to make sure I did not think in the opposite way.

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

Alternatively for Div 2D/1B, you can try finding any subarray of length at least 2 which has median at least k. If you can find such a subarray, the answer is yes, otherwise it is no. FatalEagle describes how to find number of subarrays with median at least k over here.

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

I must say problems were very good and interesting.Thanks for the fast editorial.

→ Reply
»
3 weeks ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

I have a very short solution for Div1A which I think is pretty cool, and is not mentioned in the editorial. It uses dp:

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b){
  if (a == 0)
      return b;
  return gcd(b % a, a);
}

long long lcm(long long a, long long b)  {
  return (a*b)/gcd(a, b);
}

int main(){
  int n;
  cin >> n;
  vector<long long> a;
  long long ai;
  for(int i = 0; i < n; i++){
    cin >> ai;
    a.push_back(ai);
  }
  vector<vector<long long> > dp(2, vector<long long>(n, 1));
  dp[0][0] = a[0];
  dp[1][0] = a[0];
  dp[0][1] = gcd(a[0],a[1]);
  dp[1][1] = lcm(a[0],a[1]);
  for(int i = 2; i < n; i++){
    dp[0][i] = gcd(dp[0][i-1],a[i]);
    dp[1][i] = lcm(dp[0][i-1],gcd(dp[1][i-1],a[i]));
  }
  cout << dp[1][n-1] << "\n";
}

https://codeforces.com/contest/1350/submission/79884445

Basically the idea is we can keep track of what primes are divisors of all the numbers, and which primes are divisors of at least n — 1 of the numbers. The first row in dp is just the gcd of all the numbers, thus the primes which divide all numbers. The second row of dp is the factors which divide at least n — 1 of the numbers. The first row is easy to calculate, its just the gcd of the current number in the array and the previous column in dp. The second row is a little trickier, but it's just the lcm of the primes which divide all the previous numbers and the gcd of the previous column and the current number in the array. The code itself might explain it a bit clearer.

But basically to get the primes which divide at least n — 1 of the numbers, you can either just take all the primes which divide all of the first n — 1 numbers, or take the primes which divide at least n — 2 of the first n — 1 numbers, and also divide the current nth number, which is how you get the second equation. The final answer after iterating through dp is then just the cell in the second row and last column.

The code itself might make what I'm saying a bit clearer. If this is confusing I can try to explain it better, but I thought this was a pretty neat solution.

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

    Your explanation is pretty clear than editorial for me but it's a little confusing how you are getting factors that divide n-1 numbers. It would be highly appreciable if you explain it with an example :)

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

      Ok let me try:

      So for example let's use one of the pretests:

      10 24 40 80

      We start by assigning dp[0][1] = gcd(10,24) and dp[1][1] = lcm(10,24), as the gcd gives all the primes which divide both, and lcm gives all the primes which divide at least n-1 (so in the case of the first two numbers, we include any prime which divides either). So now we have dp[0][1] = 2 and dp[1][1] = 120.

      Now, calculating dp[0][2] is easy, it's just gcd(dp[0][1], 40) = 2. This is all the factors which divide all of the first three numbers. Now we calculate dp[1][2] by lcm(dp[0][1], gcd(dp[1][1], 40) = lcm(2, gcd(120,40)) = lcm(2, 40) = 40. So here we have that all the prime powers of 40 divide at least (3-1)=2 of the first 3 numbers (when I said factors in the previous post its actually slightly incorrect, as we in fact need any prime power factor to divide at least n-1 of the numbers, not any factor).

      The reason we did lcm(2, gcd(120,40)) is the following: 2 divides all of the first 2 numbers, so it trivially divides (3-1)=2 of the first 3 numbers. On the other hand, prime powers in 120 divide at least (2-1)=1 of the first 2, and so if we take gcd(120,40), the result will also divide 40, and so we get prime powers which divide 1+1=2 of the first 3 numbers. We then take the lcm of these two cases, as any prime power which satisfies either is good.

      Finally, for 80, we have dp[0][3] = gcd(2,80) = 2, and dp[1][3] = lcm(2, gcd(40,80)) = lcm(2,40) = 40, and that is in fact the desired answer.

      Let me know if this helped :).

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

        Wow, the thing in which I was confused is very well explained in the last second paragraph. Thanks to you. Hope you achieve high ratings in future :)

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

        please can you explain, i am a new coder, why we are seeing primes when the question is all about GCD and LCM

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

          GCD and LCM intrinsically have to do with primes, because they are comparing factors of numbers. GCD takes the minimum power of every prime from the two numbers, and LCM takes the maximum power of every prime.

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

A (maybe) more intuitive way for Div1 D:

Let $$$m=\sum a_i$$$. Like this problem, if we find a potential function $$$f$$$ such that $$$\mathbb{E} \left(\sum_{i} f(a_i) \right)$$$ decreased by $$$1$$$ in each step, the answer is simply $$$\sum f(a_i)-\left((n-1)f(0)+f(m)\right)$$$, which is the initial potential minus the final potential.

To satisfy the condition, we have equaltion

$$$\sum_i f(a_i)=\sum_{i} \frac{a_i}{m} \left((f(a_i-1)+1) + \left(\sum_{j\neq i} \frac{1}{n-1}f(a_j+1)+\frac{n-2}{n-1} f(a_j))\right)\right)$$$

, which is

$$$\sum_i \left(\frac{a_i}{m} (f(a_i-1)+1) + \frac{(m-a_i)}{m(n-1)} f(a_i+1)+\frac{(m-a_i)(n-2)}{n-1} f(a_i)\right)$$$

.

It is not hard to see if

$$$f(a)= \frac{a}{m} \left(f(a-1)+1\right)+\frac{m-a}{m(n-1)} f(a+1)+\frac{(m-a)(n-2)}{m(n-1)} f(a)$$$

for all $a (0\leq a \leq m-1)$, it satisfies the condition.

So simply solve these equations and find the answer.

We can use this method for all problems of this kind.

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

Div 2C/ Div 1A

observe --> lcm[a, gcd(b, c)] = gcd(lcm[a, b], lcm[a, c]) and gcd(a, lcm[b, c]) = lcm[gcd(a, b), gcd(a, c)]

using them the sought answer can be brought down to

gcd of { (a[i]*gcd(a[i+1], a[i+2], .. , a[n]))/gcd(a[i], a[i+1], .. , a[n] | i <= n }

so create an array (say, g) as: g[i] = gcd(a[i], a[i+1], .. , a[n])

check code here: 79893540

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

    Hi can you explain to me why did you divide the above numerator by gcd of all elements ??

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

      that is not gcd of all elements, that is the gcd from a[i] to a[n]

      that came only because i converted lcm to gcd, final answer in lcm form -->

      gcd of { lcm(a[i], gcd(a[i+1], a[i+2], .. a[n]) | i <= n }

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

    How did you prove for more than three numbers?

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

Anyway, problemset was nice — thx a lot

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

a good contest based on number theory. :)

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

Guys, could you please find the problem in my solution. By my mind it should work. Problem Div.2E-Div1.C .

My solution

I will be thankful.

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

    Don't waste time, sorry, I think I found the problem(

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

Here is my O( NlogN ) solution to Div2C/Div1C. Code.

I counted the number of instances of each number in a count array mp. Then for each i=2 to 2e5, I have counted the number of elements in the sequence which are divisible by i in cnt[i]. Now if we observe the final gcd will have contributions only from numbers i which have cnt[i] >= n-1. ( They appear in at least one of the numbers for each pair. ) Now since it may happen than cnt[2] = n and cnt[4] = n-1. In that case we may ignore 2's contribution by taking a lcm of the current answer with 4 and similarly for higher powers of a prime. I hope I didn't make it complex for anyone :P.

How is it NlogN ? the loop in which I update cnt runs for (N + N/2 + N/3 + ... 1) which gives NlogN. Thanks to ffao for correcting me and Everule for the explanation why it is NlogN. Also sequential addition of Nlog(N) for calculating the cumulative gcd.

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

    (N + N/2 + N/3 + ... 1) is O(N log N), not O(N log log N).

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

    I'm sorry, but that is not true. Sieve of Eratosthenes is $$$O(n\log{\log{n}})$$$ because it is $$$\sum N/p$$$ for all primes less than $$$\sqrt{n}$$$. $$$\sum_{i=1}^{N} N/i \approx n\log{n}$$$

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

The problems were very good. Thanks.

Reg the editorial, isn't the complexity of Div2A O(1) ?

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

    Wait, I don't think it can be done $$$O(1)$$$. You need to iterate up to sqrt(N) to find at least one divisor (if not, then the only valid divisor is N itself). You could go all the way up to N iterations too but sqrt(N) is okay (and if you don't find any divisors until then, N must be a prime). So, best complexity achievable is $$$O(\sqrt{N})$$$

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

      My Bad.

      I noticed the formula in editorial and thought it was O(1).

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

Div2 C/ Div1 A Can someone please check why my code is getting TLE. I think it should be within the bounds. My Code : 79910710

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

    Your f() loops n*10^4 which is like 10^9. See if you can optimize that part.

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

    It overflows, you wrote for(int j = i*i; j <= n; j += i), then $$$j$$$ will overflow.

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

      No, j <= N and N = 1e5. So, it shouldn't overflow

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

        Lets say $$$i = 10^5$$$, then it calculated $$$j = 10^5 \ctod 10^5$$$, which overflows and goes to negative numbers(for example $$$j = -10^9$$$), you see? it overflows AF. :)

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

can someone tell whats wrong in my approach for A 79887649

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

    For big prime numbers, your fact is equal to -1(should be equal to $$$n$$$ itself).

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

      thanks man !!,i was really stuck on this and got demotivated during contest:(

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

I cannot get my head around div2C / div1A. Can someone explain it using some examples? Pretty please.

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

    Since array t contains all possible lcm of pairs from input, We just need to find the product of all prime numbers that divide atleast n-1 numbers of the input. A simple example would be [5 7 5 5], You can notice that every element in the array t would have 5 as one of its divisors since 7 cannot exist alone.

    Now lets take an example from sample test to see how the algorithm works:

    input= [10 24 40 80] , n=4 ans=1; //initially

    • Since all numbers are divisible by 2, divide all by 2 => [5 12 20 40], ans=1*2=2;
    • Since n-1 numbers are divisible by 2, divide them by 2 => [5 6 10 20], ans=2*2=4;
    • Since n-1 numbers are divisible by 2, divide them by 2 => [5 3 5 10], ans=4*2=8;
    • Since n-1 numbers are divisible by 5, divide them by 5 => [1 3 1 2], ans=8*5=40;
    • Algorithms iterates through rest of the numbers and final answer is 40.

    Code

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

      By f=2 you're checking if there are any two numbers not divisible by i ,but i did reverse I checked if there are n-1 numbers or not which are divisible by i and I got TLE. You just ended up getting lucky with test cases in this contest :P

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

        Not really, It's pretty obvious that if you loop n-1 times inside a loop of 2e5 its gonna be TLE. Notice how i have a break statement if 2 numbers are not divisible by i, The one thing to be noticed is 2e5 can only have a max of 17 prime divisors(2^17=1.3*1e5) so the inner loops only gets traversed around 17*2 times in worst case but for your code it gets traversed every time. It's not a coincidence that my solution got accepted in 62ms :)

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

      Hey, thanks!

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

Thanks for the problems!

By the way, a formal petition to the setters to write cleaner model solutions than this:

I mean, I can probably understand it, but please, you've got plenty of time before the contest. You aren't racing to write the models as fast as possible, and you can spend some of your time making sure the code is readable.

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

For problem Div2 D once checkout my solution 79912071 I have not checked a case when n = 1, I simply wrote if(n==1) cout<<"yes", but my doubt is there should be if(n==1&&arr[0]==k)cout<<"yes";

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

    You first checked that the array has at least one $$$i$$$ such that $$$a_i = k$$$, so if $$$n == 1$$$ then you can be sure that the only element is $$$k$$$.

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

    If arr[0] was not k, ok would remain false and hence it will not even reach the case:

    if(n==1) ..

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

Why is this approach wrong for Div2B? I tried brute force and generated all sequences of divisors and then checked whether the sequence is beautiful or not. I am getting WA on pretest 2: link to submission

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

    Its $$$2^n - 1$$$ beautiful sequences in worst case(if array $$$s$$$ is increasing) so i guess your brute force should not work, try solving it with DP.

    Sorry, its not $$$2^n-1$$$ sequence, your brute force should work, sorry for that.

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

Editorial should be in little simple language. Can anyone please explain Div 2 Problem C?

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

    But there is complete editorial... What didnt you understand?

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

Having trouble wrapping my head around one line of this problem: 1349A — Orac and LCM. In the proof, the editorial says: "Proof. if there are at most n−2 integers in a that s.t. pk∣ ai, there exists x≠y s.t. pk∤ax and pk∤ay, so pk∤lcm({ax,ay}) and pk ∤ ans."

I can't seem to convince myself why if pk does not divide ax and ay, it must not divide lcm({ax,ay})? Would appreciate any insight, thanks!

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

    Let me proof it, if we have at most one $$$a_i$$$ such that $$$p$$$ doesn't divide $$$a_i$$$, then for any $$$1 \le i,j \le n$$$, $$$p$$$ divides $$$lcm(a_i, a_j)$$$(because at least one of them is dividable by $$$p$$$). So $$$p$$$ divides the answer as well.

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

      Thanks for the reply! That makes sense to me. Its more so the contrary that I don't really get. When they consider the case where you have two entries ax and ay that are not divisible by p, why can we say that p does not divide lcm({ax,ay})?

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

        Lets prove :

        Lets say the smallest number such that it doesn't divide $$$x$$$ and $$$y$$$, but divides $$$lcm(x, y)$$$ is $$$p$$$, with use of math you can see that $$${lcm(x, y)\over p}$$$ is dividable by both $$$x$$$ and $$$y$$$, but its smaller than $$$lcm(x, y)$$$ the contradiction prove that no such $$$p$$$ exist that doesn't divide $$$x$$$ and $$$y$$$ but divides $$$lcm(x, y)$$$.

        Another proof :

        Lets say such $$$p$$$ exist, we know that $$$lcm(x, y)\cdot gcd(x, y) = x\cdot y$$$, as $$$p$$$ divides $$$lcm(x, y)$$$ so the left part is dividable by $$$p$$$, but the right part is not, the contradiction proves no such $$$p$$$ exist that doesn't divide $$$x$$$ and $$$y$$$ but divides $$$lcm(x, y)$$$.

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

          Appreciate the proofs, thanks again. One final follow up. The example below is what it is tripping me up a bit. Do you know what is wrong about it? So lets say we have x = 3 and y = 10. Then lcm(3,10) = 30. Lets say p = 15. Then 15 does not divide x and does not divide y, but does in fact divide lcm(x,y). Is there something that does not work here?

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

            It doesn't work because 15 is not prime. The statement applies to primes. If there is a prime (or prime power) which doesn't divide x and doesn't divide y, it won't divide lcm(x,y). We only care about prime powers in the solutions to the problem, so this is sufficient.

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

            I considered $$$p$$$ to be prime(or a power of a prime) but forgot to add it in the proof. Sorry.

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

              All good, thanks for the explanation!

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

          i dont understand what does this mean "p^k | ans" why we are doing OR operation here??..

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

      hey thank you so much

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

    Solution explanation for Div 2. C. Orac and LCM -> Find Gcd of whole array say g -> Divide whole array by g -> Now array is suppose x1,x2....xn -> For some index k lets find the value for all its pair.. -> so, vk= gcd(lcm(x1,xk),lcm(x2,xk).....lcm(x(k-1),xk),lcm(x(k+1),xk),.....lcm(xn,xk)) -> xk val is included in all terms we can take it as common -> vk = xk*gcd(x1,x2,..x(k-1),x(k+1),......xn); -> no harm in taking xk as common as the second term is coprime to first one always... as we have already divided all the numbers by total arrays gcd. -> simply take gcd of all vi's for all 1<=i<=k Here is my solution for reference https://codeforces.com/contest/1350/submission/79831074

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

can anybody please tell me why my solution is wrong.Div2/prob b pretest2 failed. https://codeforces.com/contest/1350/submission/79864654

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

Can someone please check my solution. It's giving wrong ans I'm doing exactly as editorial it a O(n*sqrt(n)) solution https://codeforces.com/contest/1350/submission/79914083

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

    your find_divisors function is wrong. check for array of size 24 are you getting right divisors for the number 24. Probably you shouldn't divide the number(whose divisor you are finding) by the divisor.

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

      Thank you so much. I got the mistake i was finding prime divisors i need to find divisors.

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

My approach for Div1A/Div2C is similar to the Second approach discussed in the editorial, but I am unable to understand the first approach, can anyone help me telling how we arrive at the given observation mathematically?

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

div 2 problem c editorial not clear!! please help.

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

https://codeforces.com/contest/1350/submission/79817740 This solution got accepted for A. Orac and Factors though its Time Complexity is O(k) and k is 10^9 .... How is this possible ????

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

Can anyone please describe me the sample test cases of #div 2 B?

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

lol am I the only who thought in div 2 B they were talking about values stored at indexes to be divisible instead of indexes

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

can some one explain how bfs can be used to minimum distance of from good cell to black cell in problem DIV1 C

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

wow I like the editorial. I wasn't able to do div2/C during contest and it is well explained here. The mathematical proof is also very easy to follow.

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

div2C/ div1A solution 2 ,can anyone explain how the time complexity is O(v+nlog v). Thanks

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

    Shouldn't it be O(v+n*H*log v) where H is number of primes less than v , and as the number H is somewhere around 1000 for v=200000, so resulting in roughly O(100000*1000*10) = O(1,000,000,000) shouldn't it give TLE. In optimising steps it says we are stopping after we find that two numbers that aren't divisible by prime p, and move to next prime, so H isn't around 1000 but that's make computing it's complexity difficult for me. I would be very thankful if someone can explain.

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Can anyone help me out to find what is wrong with this code ? I don't find the mistake in my logic. Div2.B...

#include <bits/stdc++.h>

#define ll long long 

using namespace std;


void run_case(void)
{
	int n;
	cin >> n;
	vector <int> size (n+1);
	
	for(int i =0; i<n; i++) cin >> size[i+1];
	
	if (n==1) cout << 1 <<endl;
	else {
		int ans = 0;
		int mx = 0;
		
		for(int i=1; i<=n; i++){
			ans = ((size[i]>size[1])? 2 : 1 );
			for(int j=2; i*j <= n && (size[i*j] > size[i*(j-1)]); j++) ans ++;
			
			if(ans > mx) mx  = ans;
			
		}
		cout << mx <<endl;
	}

}

int main(void)
{
	ios_base :: sync_with_stdio (false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
	freopen ("Input.txt" , "r", stdin);
	#endif
	
	int t;
	cin >> t;
	while(t--) 
	run_case();
	
}
→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think your approach is wrong bro...acc to ur approach u can't have ans with index 2 3 6 because u r seeing just multiple of index eg. 2 4 6 but 4 is not divisor of 6. I hope u get it!!

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

    its dp problem next index answer depends on previous index...something like LIS

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

I have implemented the solution to Div2E/Div1C here https://codeforces.com/contest/1350/submission/79919196. Why am I getting runtime error and this weird verdict? I have been trying to debug my code but cannot find anything. If someone can please help it will be really great.

Edit: I've got it now, I was accessing q.front() by reference and then popped it. This was causing the RE.

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

Can anybody tell me how I optimize my code for PROBLEM (DIV 2 C), my approach seems correctbut getting TLE https://codeforces.com/contest/1350/submission/79920601

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

Hey guys,

I would like to give me some tips to improve. Specifically, on problem D, during the contest, I observed that if we somehow can form 2 numbers equal to k in row, then we can easily convert the entire sequence to k. In order to do that, we can go to each k and look left or right and see if we can have it as a median. If we can't do it (or no such k exist), the answer is no. Otherwise, obviously, there is a way! Please refer to my submission here for more details on my approach: https://codeforces.com/contest/1350/submission/79882933

Then, I was getting always WAs on test 10 and I was scrambling to find a case where it didn't work, but I couldn't find what's wrong and eventually I missed the problem. After that, I saw a solution and it hit me; if we have 2 consecutive numbers that are greater than k or 2 that have a smaller number in between, we can propagate it until it reaches a k and after that we can use my approach to finish it.

Unfortunately for me, I was unable to see this case and I did not solve the it. I would like your opinion on those 2 stuff:

  1. What is the easiest way to generate test cases that could help on finding the flaws on a speculation like the one I presented above? For me, it's quite difficult to find any (especially on this problem).

  2. On this case, was there any other way to disprove a speculation other than trying to find a counterexample?

Any help appreciated! Thanks!

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

    Use Python to generate many small cases and a brute force solver. Though it might be hard for graph problems. But for problem D, this can be made. I do this when I can't figure out what's wrong and it also helps reduce WA's. It's not that hard to do this because Python has many tools like itertools and easy syntax for many stuff. When you find a small case, you can easily trace what's wrong.

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

Can someone pls, explain the memoization approach for Div.2 B orac and models? Thanks In Advance.

→ Reply
»
3 weeks ago, # |
← Rev. 4   Vote: I like it +62 Vote: I do not like it

As for Div1F2:

0) I assume that

$$$ \displaystyle [z^i] \sum_{k=1}^{n-1} F^k = [z^i] \frac{F}{1-F} - [z^i] \frac{F^{n-i+1}}{1-F}? $$$

(The formula in the editorial misses $$$F$$$ in the numerator in the first term on the right hand side?)

1) What is "Lagrange Inversion"? I've never heard about this, and wikipedia suggests this or this; both of them are said to be called "inversion formulas", but I'd guess the former somehow applies? How to apply it, then? I can't see how to get the equation just below "And from the Lagrange Inversion: (...)" from the one above.

2) How to even think about this solution? To me, it looks like magic or a bunch of random complicated transformations of a power series which suddenly stops at a formula that we can compute using FFT fairly easily. I can even trace the steps (apart from this Lagrange inversion I mentioned before) and verify they're roughly okay. But... I can't picture myself ever finding out I needed to follow exactly these steps, even if I spent a month on the problem -- even after having read the editorial. What should I do if I want to get some understanding on what happens here?

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

    I am little confused about the formula in easy version is the code correct or does the editorial formula has some extra terms, because, if compared directly some factorials are missing in the code.please correct me if I am wrong. The d_ij version has y! But code doesn't.

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

      The meaning of $$$d_{i,j}$$$ in the code is different than in the editorial. This code follows the editorial exactly.

      (and extension to F2 is here)

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

    General Lagrange inversion formula is, for $$$F(x)$$$ and $$$G(x)$$$ satisfied $$$F(0)=G(0)=0,\,[x^1]F(x)\neq 0,\,[x^1]G(x)\neq 0,\,G(F(x))=x$$$:

    $$$[x^n]F(x)={1\over n}[x^{-1}]{1\over G(x)^n}$$$
    $$$[x^n]H(F(x))={1\over n}[x^{-1}]H'(x){1\over G(x)^n}$$$
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Do you know any good source to learn more about the general Lagrange Inversion Formula (even if it's Chinese explanation)?

      So in the editorial we substitute $$$F(x) = w(x)$$$, $$$G(x) = \frac{x}{\phi(x)}$$$ and $$$H(x) = \frac{1}{1 - \phi(x)} \cdot \frac{1}{1 - ux}$$$ I guess?

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

        It's mentioned in the books "Enumerative Combinatorics", "Analytic Combinatorics" and "Generatingfunctionology".

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

        Elegia

        We know that $$$\phi(x)=\frac{x}{\ln (1+x)}$$$. Then

        $$$\frac{1}{1-\phi(x)}=\frac{\ln (1+x)}{\ln(1+x)-x}=\frac{x-x^2/2+...}{-x^2/2+x^3/3-...}=-\frac{2}{x}+\sum_{i\ge 0}a_ix^i,$$$

        so $$$H(x)$$$ also contains a term of $$$\frac{1}{x}$$$, meaning that it is not analytic. Doesn't Lagrange Inversion require $$$H(x)$$$ to be analytic (according to Wikipedia)? Though I'm not familiar with this at all ...

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

          This theorem can be proved in formal Laurent series, it means that it's always correct when $$$n, k\in \mathbb Z$$$:

          $$$ n[x^n]F^{\langle -1 \rangle}(x)^k = k[x^{-k}]F(x)^{-n} $$$
          → Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    It seems that indeed a $$$F$$$ was missed. And, to be frank, I'm also not so good at these things. Elegia has an indepth study in combinatorics, generating functions and skills behind, and he has top level of skills in GF-oriented counting problems, even among those top OIers in China. This solution is his masterpiece, maybe.

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

    Same here, I'm trying to find the logic behind this. Maybe I'll write a survey after getting better understanding.

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

Can somebody help me figure out why my code for Div2C/Div1A fails test case 7?

Code

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

ProgSlacking In the editorial of D2E 2nd paragraph why is this the case when every grid is good then colour would never change please explain.

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

Unable to understand Div2-B problem someone please explain.

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

    you have to find the longest sequence where these conditions hold.

    1. every index should be divisible by the previous adjacent index. eg.

    5

    1 2 3 4 5

    you can choose 1 2 4 or 2 4 or 1 3 or 1 4 or 1 5 as well. Because index 4 is divisible by previous index 2 and index 2 is divisible by index 1.

    And The second condition is: every chosen element should be greater than the previous adjacent element. likely

    5

    2 1 3 1 1

    you should choose index 1,3 because a[3] is greater than a[1] and 3 is divisible by 1.

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

    Look at longest increasing subsequence here: https://cses.fi/book/book.pdf

    The idea is the same except you must change the inner loop to match what the problem asks.

    My code: https://codeforces.com/contest/1350/submission/79926910.

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

Can anyone please explain why my DFS solution for Div 2 B problem is giving WA?My submission- 79925444.Progslacking or DeadlyCritic Can u please help me debug this? I will be grateful. Thank you.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I checked this out, the bug was your DFS, you didn't run the DFS from all indices, and also you wrote :


    if(arr[temp]>arr[x])
     dfs(temp,ans+1);
else
     dfs(temp, ans);

    What is that else ??, i guess you wanted to say that we don't pop_back $$$x$$$, but what if $$$arr_{temp}$$$ was very small that you should pop_back more numbers.

    Here is your code getting AC, barely passing time limits.

    I recommend not to use long longs when they are unnecessary, see this, twice faster.

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

      Thank you very much DeadlyCritic for debugging it and providing an explanation. Regarding "else" part, Yes I thought of pop_back in recursion so that I wont need to loop DFS through all indices. Therefore I took only 1 index for DFS.

      Also thanks for the suggestion regarding long long. Will keep that in mind. :)

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

      The impact is greatly reduced in G++17 64-bit, see 80071943 and 80071981 (long long). The difference is just 250ms.

      Though, I do agree that use long longs only when required.

      → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

The solution for Div 2D(1B) fails for the following testcase:
n = 5, k = 1 and a=2,2,0,0,1
The answer should be no, but the given solution gives yes.
Am I missing something? @progslacking?
[Edit : My bad, the answer should be yes only]

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

    first convert the leftmost 0 to 2 by taking first 3 numbers, then convert the second 0 to 2 too. After 2 conversions you get:-

    22001->22201->22221

    Now start converting the 2's to 1 by taking one at a time:-

    22221->22211->22111->21111->11111

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

The contest is very interesting,thanks for questions setters.I thinks the ideas of solving B problem is very great,I should make more effort in it.

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

Thanks for Codeforces, and I hope Codeforces will be better and better. Come on! (Sorry, I'm Chinese. So my English isn't very good.)

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

can someone explain the time complexity of the seconds solution of DIV2 C ( Orac and LCM problem )

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

    you can find the min prime factor for each number and then divide everyone in O(logV)

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

I really like the problems <3

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

just an another way to store statuses for Div 2B problem , time complexity O(n * sqrt(n)) https://codeforces.com/contest/1350/submission/79929678

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

Anyone please explain div2.D. I didn't get the editorial explanation.

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

For Div1A/Div2C, why are we taking

ans=lcm(gcd(d1),gcd(d2)...gcd(dN))?

I am wondering why ans is not

ans=max(gcd(d1),gcd(d2)...gcd(dN))?

Since our requirement is that the ans should divide N-1 integers of a,

could someone please tell why the 2nd answer is wrong?

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

    Hey sanjay_thiru,

    I hope you understood the observation that is mentioned in the beginning of the editorial .

    Basically you are trying to find the lowest value to divide every distinct set of (n-1) numbers (distinct by index), So each of those values found will appear atleast once in every pair of numbers that we use LCM on.

    So in the LCM of all these pair of numbers , those calculated values will exist.

    And, since you have to find the GCD of all the pairs , it makes sense to take LCM of all the GCD(di), because we want the greatest value that divides all the LCM of pairs.

    Hence the conclusion.

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

Mathforces!!!!!

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Best problem of math

C was easy use this properties

gcd(lcm(a,b),lcm(a,c),lcm(a,d)) = lcm(a,gcd(b,c,d))

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

I am not able to figure out what's wrong with my solution of Div2D (https://codeforces.com/contest/1350/submission/79941143). Can anyone, please help me in coming up with a small test case where my solution will fail.

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

    n =10 ,k = 3,

    6 1 6 1 1 1 1 1 1 3

    for this test the answer is yes but your code output is no.

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

For Div2B, I tried simple DFS : 79945578.

Although my code successfully passed, I'm struggling to grasp why this approach is okay.

Anyone can calculate and explain time complexity of this solution?

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

whats the problem with my code in div2 B. It gave me tle although i used same approach as in editorial. Only difference is that i used memoization while applying dp link to my submission: https://codeforces.com/contest/1350/submission/79881782

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

Can anyone please check my Div2 C code: https://codeforces.com/contest/1350/submission/79873786

It gave me the memory limit exceeded error. Need help in figuring out the correct answer. Please share the relevant concepts that I didn't use here.

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

    O(N^2) will timeout.

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

      Yes, but it doesn't give time limit exceeded. rather it gives memory exceeded error.

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

        Lol so what? That's still gonna push N^2 in your array which will MLE. It's either gonna MLE or TLE whichever happens first. Maybe just stop forcing solutions to work when it's clearly bad.

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

In Div1C, why are grid cell's (i, j) termed as "grid"?

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

Can anyone can prove this : $$$gcd$$$ $$$of$$$ $$$sequence$$$ $$$lcm(x , ai)$$$ = $$$lcm(x$$$ , $$$gcd$$$ $$$of$$$ $$$sequence$$$ $$$ai$$$) , $$$i = 1, 2, .. n$$$ and $$$x$$$ $$$is$$$ $$$some$$$ $$$integer$$$

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

    Let $$$d=lcm(x,a_i)$$$ and $$$k=gcd(a_1,a_2,...,a_n)$$$， notice that $$$a_i|d$$$,and $$$k|a_i$$$, then $$$k|d$$$.

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

video editorial for B and C

https://codeforces.com/blog/entry/77306

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

can u please post another tutorial of Div 2 B problem as math tag is also present in it but editorial posted is of dp. it would be great if you do so!

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

Thanx, DeadlyCritic for reaching out to each possible comment. Just can't get why my solution is getting TLE which is similar to this one. Can you help?

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

    It overflows in the following line :


        for (int i = 2; i * i <= 200006; ++i){
        if(!prime[i]){
            for (int j = i * i; j <= 200006; j = j + i){
                prime[j] = 1;
            }
        }
  }

    because $$$i\cdot i$$$ can be as big as $$$10^{10}$$$.

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

      DeadlyCritic Sir, That's why in my recent submission, I took long long and not int. Still, it is giving TLE, why?

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

      Moreover, since i loops over till sqrt(200006) which is equal to 447 and hence i*i at max equals 200006. I don't see that as a reason. Perhaps something else, which I can't figure out.

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

        Sorry i missed that, for each $$$a_i$$$ you iterate over all primes yes? then it takes $$${n \over log_2n}$$$ time for each $$$a_i$$$(number of primes less than $$$n$$$ is at least $$${n \over log_2n}$$$), then the whole solution works in $$$O(n\cdot {n \over log_2n})$$$ time, which is too much, you don't have to iterate over all primes, just iterate over primes less than 500, then if $$$a_i > 1$$$ then its prime and insert it.

        Iv'e tried it and got AC

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

          ok thanx got that. Never thought that it would be a problem doing that !!

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

Hi, I've been trying to debug my code for Div2 C, I think my code follows the solution #2 described in the editorial, but somehow I keep getting wrong answer on test 4, can anyone please explain where the mistake is?? Thanks in advance My submission

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

    Does your code check big primes? for example the answer to the following test is 199967 :

    5
199967 199967 199967 199967 199967
    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In case anyone is still stuck detail explanation of C and B

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what does it mean by pk ∣ ans if and only if there are at least n−1 integers in a that s.t. pk∣ ai. ? specially the portion pk ∣ ans and pk∣ ai.

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

    a | b is a notation to indicate "a divides b".

    In this case, the baseline of the problem is that a certain number n divides the answer iff it is included in at least n-1 elements. :)

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

    I am also not being able to get it. I need some detailed explanation. Where can I find it?

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

In problem C, I got the second idea at the very beginning. Just because of a silly mistake it got WA on 36 in system test(debugged it later). However, I enjoyed the problem...

→ Reply
»
2 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

MikeMirzayanov Hi, I think offical submission 79869658 by lcjWA and submission 79869030 by Bazoka13 are almost the same.It may break the rules of contest, which helps them both become Candidate master.

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

    Hello, I'm very angry about what you said. It's a kind of stigma. My idea of question D is as follows: suppose a interval has a number other than k, then if there is a [i] > = K and a [i + 1] > = k|a [i + 2] > = k, we must be able to yes why? If a [i] a [i + 1] satisfies the condition, then it can make its left or right side expand to the number of > = k until it reaches the value of K. at this time, the number adjacent to K is > = K. according to the meaning of the question (2 + 1) / 2, the interval is assimilated to K no matter how

    It's the same way to assimilate a [i] a [i + 2] step by step. He can certainly make [I, I + 2] become a number > = k, because (3 + 1) / 2 = 2 even if a [i + 1] is the smallest in this range, it will not be changed by him. So there are 1.6W participants in this competition. Is there 1.6W talents in each problem solution that can not be judged as cheating? Funny. I believe that everyone who answers the D question correctly uses the same method as me

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

    To sum up, question D is just like the 1 + 1 = 2 you did in primary school. Is there any other solution to 1 + 1 = 2? Is the 1 + 1 = 2 written by primary school students in an examination room cheating? Fuck you

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

Can Somebody Explain Why this soln to Div -2 C is getting TLED 79963348 ??? The complexity is O(n*n/(log(n)))

Edit : The complexity is not enough to pass

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me whats wrong in this solution 79969659 This is for div 2 C.. giving wrong answer on test case 9.. but when I copy the testcase 9 and run it ..it gives correct answer..How?

Test case 9

2

199999 200000

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's make Div2D/Div1B a little interesting. If only those subsegments could be transformed whose median is k, how would you approach the problem?

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

Why is my recursive bruteforce for Div2B giving WA? Would be great if anyone could point out the mistake in recurrence Submission

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

79976653 Div2 B can anyone please tell me problem in this?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the difference between $$$\displaystyle E_x$$$ and $$$\displaystyle E_{x}^{'}$$$ in Div1D editorial ?

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

    $$$E_x$$$ is the expected time that the game ends on $$$x$$$, wheras $$$E_x'$$$ is the expected time in a "modified rules" game where we stop only when all biscuits are on $$$x$$$.

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem Div2C/Div1A — Orac and LCM

Can someone please explain why this is resulting in a runtime error on test 4 (Submission: 79984224)

import math

def multipleGCD(data, index):
    if len(data) - index == 1:
        return data[index]
    else:
        return math.gcd(data[index],  multipleGCD(data, index+1))
    
def solve(data, size):
    result = []
    for i in range(size-1):
        x = multipleGCD(data[i+1:], 0)
        y = math.gcd(data[i], x)
        result.append((x*data[i])//y)
    res = multipleGCD(result, 0)
    return res

size = int(input())
data = list(map(int, input().split()))
print(solve(data, size))

~~~~~ ~~~~~

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution for Div2.B, why is there a const MAXN = 500005 ? Where does 500005 come from?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, here is my submission of Div1-C https://codeforces.com/problemset/submission/1349/79994169 I used the same logic as in editorial but using DP. It gave WA on 6th testcase and I am not able to figure the error, can anyone help?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV-2 B My solution :

#include<bits/stdc++.h>
using namespace std;
 
vector<int> factors[100005];
int dp[100005] = {0};
int arr[100005];

//precompute all the factors of every integer
void pre(){
    for(int i=1;i<=100000;i++){
        for(int j=i;j<=100000;j+=i){
            factors[j].push_back(i);
        }
    }
}

int solve(int n){
	if(n==1) return 1;
	int ans = 1;
	if(dp[n]!=0) return dp[n];
	for(auto j : factors[n]){
		if(arr[j]<arr[n])
			ans = max(ans, 1 + solve(j));
	}
	return dp[n] = ans ;
}
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
    //pre-calculating the factors
    pre();
    int t ;
    cin>>t ;
    while(t--){
    	memset(dp,0,sizeof(dp));
	    int n ;
	    cin>>n ;
	    for(int i=1;i<=n;i++) arr[i]=0;
	    for(int i=1;i<=n;i++){
	    	cin>>arr[i];
	    }
	    int ans = 1;
	    for(int i=n;i>=1;i--){
	    	ans = max(ans,solve(i));
	    }
	    cout<<ans<<endl ;
    }
}
→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me out with the div1 C:- i cannot understand why all the cells in the example shown in the questions getting changed in the single iteration rather than the single cell being changed....(i think i am not able to get this particular line properly please help me out):- // For each iteration of the game (the initial iteration is 0), the color of each cell will change under the following rules:

If there are no adjacent cells with the same color as this cell on the current iteration, the color of it on the next iteration will be the same. Otherwise, the color of the cell on the next iteration will be different. //

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

How do i optimize the memory for Div 2E, I'm getting a MLE on test 8. 80013481 is my solution.

Thanks. UPD — I'm sorry, I changed the submission ID

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

    You sent a message on wrong thread, this is most recent div1,div2 round.

    Your problem is of a old div3.

    And you get TLE on TC12, is this the correct submission? [Reason for which BTW is because you don't break if flag = false so it becomes an infinite loop.]

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

      I'm sorry I made a mistake in the Submission ID

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

following one is the code I am talking about: for _ in range(int(input())): n, k = map(int, input().split()) a = list(map(int, input().split())) if k not in a: print("No") elif n == 1: print("Yes") elif any(u >= k <= v for u, v in zip(a, a[1:])): print("Yes") elif any(u >= k <= v for u, v in zip(a, a[2:])): print("Yes") else:
print("No")

The code is for problem D. first I used pypy to run this,but the time limit exceeded on test 5. then I used python 3,and it got accepted.Can anyone tell me the the reason?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i kept on MLEing for problem C, although I had the right idea the whole time (i think I did solution 2). What can you use to calculate the number of pairs besides stuff like maps and arraylists, which MLE? Is there a way to do it in o(1) space? I literally spent 1h30m trying to implement this goddamn problem and I don't think I've ever been more tilted at a codeforces problem than this onehttps://codeforces.com/contest/1350/submission/80029151

→ Reply
»