I can’t see the difference between my solution (30 pts) and tester’s solution. They have the same complexity and mine seems better. Any ideas ?
My submission during contest : CodeChef: Practical coding for everyone
you are redeclaring a vast size array
its not necessary to declare a 2d visited array,u could use 1d visited array and using hash function => 1000*x+y , this trick i once used in tree question for storing edges in tree dp question.like x<<20+y, it will generate unique values, but greater than size range of array,so i used unordered map for that.
1 Like
@nvdrag123 I did this trick during contest with :
hash_set : CodeChef: Practical coding for everyone
unordered_map :CodeChef: Practical coding for everyone
Just a few minutes ago, i did a solution without redeclaring a vast array :CodeChef: Practical coding for everyone
still bitset reset complexity, why dont u just make the true value false,btw in this case hash set or unordered map, it will not work,its increasing complexity by factor of log.make const size array.
hash_set or unordered_set has average case O(1) in almost all operations (source) : http://www.cplusplus.com/reference/unordered_set/unordered_set/emplace/
my solution is quite different.
For each cell let’s count two numbers: the time when each of the heroes comes to this cell counting from zero(for example the (0, 0) cell will have numbers (0, 0) and (0, 1) will have (1, n))
Now it’s obvious that all the cells we visit with some of the heroes with fixed k has a view (k + 1) \cdot q for an integer q.
So all we have to do is for cell with numbers (x, y) find all numbers that divide x or y.
We can split out this problem into three easier: find all numbers that divide x and add 1 to answers for this k's, find all numbers that divide y and add 1 to answers for this k's, and find all numbers for gcd(x, y) and substract 1 from all the answers for this k's.
The only thing remains is to learn how to find all divisors of some x faster than in stupid \sqrt{n}. For this let’s calc for each x in range [2, 1e6] the least prime divisor(this can be done in O(n) or O(n loglogn) with Eratosphene sieve. After that let’s factorize each number in this diapason and save it like a pair <int, int> array, for example, we’ll save 5 as (5,1) and 100 as [(2, 2), (5, 2)], because 2^2 \cdot 5^2 = 100.
Now we can write a simple recursion function to brute force all divisors.
That is the main idea, I’m not sure if it’s that clear, but you can check my solution and ask some questions.
here it is: CodeChef: Practical coding for everyone
2 Likes
Nice Editorial. Thank You.
1 Like
Hello everyone,
The following is my 18 lines C++14 solution of the problem.
https://www.codechef.com/viewsolution/26191999
The solution is based on the idea of down-sampling the trajectory of each hero in the M \times N grid by factor K+1. For mathematical convenience, 0-indexed cell representation (r,c) is used, where r \in \{0,1,\ldots,M-1\} and c \in \{0,1,\ldots,N-1\}, respectively.
Let us assume that both heroes start to traverse the grid from the first cell (0,0) at time 0 with constant speed in the same row/column of one cell per time unit. Let us also assume that wrapping around from the last cell in each row/column to the first cell in the next row/cell column is done in one time unit.
\bf Observation~1
Both heroes destroy cells only at time instants z[i] = i \times (K+1), where i is the integer down-sampling index whose valid domain is i \in \{0,1,\ldots,\lfloor(M\times N -1)/(K+1)\rfloor\}, and both K and z[i] \in \{0,1,\ldots,M\times N-1\}. Therefore, each M\times N trajectory is down sampled by factor K+1. It follows that each hero destroys exactly 1+\lfloor(M\times N -1)/(K+1)\rfloor cells in the grid.
\bf Observation~2
The first hero reaches cell (r,c) at time instant g[r][c] = r \times N + c, while the second hero reaches the same cell at time instant h[r][c] = r + c \times M. The cell can be destroyed if and only if either g[r][c] or h[r][c] is divisible by K+1, or both.
\bf Observation~3
If both g[r][c] and h[r][c] are divisible by K+1, then cell (r,c) is destroyed by both heroes.
\bf Observation~4
The number of cells destroyed by at least one hero for a given K is equal to the summation of the number of cells destroyed by the first hero and the number of cells destroyed by the second hero only (i.e. not destroyed by both heroes).
\bf TIME-COMPLEXITY
O(p\log(p)) per test-case, where p = M \times N.
\bf UPDATE
The following is another code optimized C version of the proposed solution with less memory.
https://www.codechef.com/viewsolution/26227888
The expression for the number of cells destroyed by each hero is updated to
\lceil(M\times N)/(K+1)\rceil
15 Likes
Cool. It’s not even 18 lines. It’s 11 lines.
Hey guys! Can you pls check my code and pls tell why I am getting TLE.
`#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;
cin>>t;
for(int idx = 0; idx < t; idx++)
{
int n,m;
cin>>n>>m;
for(int i = 0; i < m*n; i++)
{
vector<int> v(n*m,0);
int count = 0;
for(int j = 0; j < m*n; j+=(i+1))
{
int k = j/m;
int l = j%m;
if(v[j] == 0)
{
v[j] = 1;
count++;
}
if(v[l*n+k] == 0)
{
v[l*n+k] = 1;
count++;
}
}
cout<<count<<" ";
}
cout<<"\n";
}
return 0;
}
`
I am getting TLE for original constraints. Pls, help me !!
Thanks !!
Editorials have not come yet for Equal Average…
for each i you create a n \cdot m sized vector. It works in O(n \cdot m) and so your overall asimptotic is O(nm \cdot (nm)).
Actually you don’t need to always create a new vector. You can simply create a static one and after each iteration make all positions you have changed on the previous iteration equal to zero.
https://www.codechef.com/viewsolution/26194092
That’s your solution, I just added a function clean garbage and remembered positions we have changed using stack
1 Like
Why I am getting TLE (Java)… Can anyone help me out ?? @taran_1407
https://www.codechef.com/viewsolution/26172035
Update:
I have improved my java code 
huge lol 
got 100 now only 2-3 line changes
https://www.codechef.com/viewsolution/26195050
Can you please explain line no. 22.?
I was actually thinking that this sieve based method will have {{(n*m)}^{2}*{log(n*m)}} complexity, should have submitted it during the contest 
You are declaring and initializing a large array (of size nm ) for every value of “k”, therefore your solution is working in n^2m^2log(nm), you can reduce this by factor of nm if you initialize the array once per test case, instead of initializing it nm times per test case.
1 Like
This question taught me the importance of global declaration and how maps can be very bad if number of elements >=10^5 
1 Like