ajs97's blog

By ajs97, history, 6 years ago, In English

Recently I was solving a gym contest and came across this problem:http://codeforces.com/gym/100739/problem/D. I have absolutely no idea as to how to solve it? Could someone give some ideas regarding the solution?

Tags gym, ktu
 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

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

Why can't we view submission in gym? Does someone know the reason? If we can, then this problem will be solved, too.

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

You can write MxN equations R[i] + C[j] = K — A[i][j] (mod K), where R[i] — number of operation "increment i-th row", C[j] — number of operations "increment i-th column".

Now let's R[i] = 0. With that you can calculate all C[j] and R[i]. And total number of operations is sum of all R[i] and C[j].

It is one of the possible answers, but can be not minimal. It's because R[0] from optimal answer can be not 0.

We can't brute all values of R[0]. But we can do next observation: if we increment any of R[i] — we need to increment all R[i] and decrement all C[j]. When we do this, total number of operation will be changed for M — N.

It can be easy proven, that optimal answer would contain some R[i] or C[j] equals to 0 (if not — we can decrement our answer for M — N or N — M at most once).

So we can simply iterate over all R[i] and C[j], set it to 0 and find answer for that setting. From all answers we need to choose answer with minimal sum of operations.

P.S. Can you modify this from O((N+M)^2) to O((N+M)log(N+M))? ;)

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

    i dont know why i am getting wrong answer in test case 21 in this code..please help me probelm link http://codeforces.com/gym/100687/problem/C

    include<bits/stdc++.h>

    using namespace std; int main() { int n,m,x,y,z,k; cin>>n>>m>>x>>y>>z; int temp=n/3; if(temp<=z) { n=n%3; z-=temp; } else if(z!=0 && n!=0) { k=z*3; z=z*3-n; z=z/3; n=n-k; } temp=n/2; if(temp<=y) { n=n%2; y-=temp; } else if(y!=0 && n!=0 &&n>0) { k=y*2; y=y*2-n; y=y/2; n=n-k; } if(n<0)n=0; m=m+n; if(m<=(x+y+z)) { cout<<"Yes"<<endl; } else cout<<"No"<<endl; return 0;

    }