Tough Problem... - Codeforces

Блог пользователя wish_me

Tough Problem...

Автор wish_me, история, 7 лет назад, По-английски

Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.

eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]

ans=12 sum from [-2,5,4,5]

wish_me
7 лет назад
9

Комментарии (9)

Написать комментарий?

-JustSomeDude-

7 лет назад, # |

Uhm... What about restrictions? What is the maximum size of A, what is the maximum value of k? Maybe you have a link?

→ Ответить

wish_me

7 лет назад, # ^ |

maximum size of array 10**3 k<10**2..I got this problem in the interview

→ Ответить

-JustSomeDude-

7 лет назад, # ^ |

← Rev. 2 →

Well. If array size is not greater than 1e3 and the time restriction is >1 second(like in the most CF problems), than you can just go for a brute solution:

//pseudo-code
themaxsum = 0
for i...n
  thesumonseg = 0
  for j = i...n
    thesumonseg = thesumonseg + a[j]
  if thesumonseg % k == 0 && thesumonseg > themaxsum
    themaxsum = thesumonseg
print(themaxsum)

Assymptotics:O(n * (n + 1) / 2)

P.S. You can also use prefix solution.

→ Ответить

redocyz

7 лет назад, # ^ |

you can actually get O(n*k) if you use dp and store the maximum sub segment modulo k.

→ Ответить

wish_me

7 лет назад, # ^ |

can you tell your approach?

→ Ответить

redocyz

7 лет назад, # ^ |

just gonna write the main dp part


for(int i = 1; i <= n; i++) {
    for(int j = 0; j<k; j++) {
        if(dp[i-1][(j-a[i]+k)%k] !=0) {
            dp[i][j] = dp[i-1][((j-a[i])%k+k)%k] + a[i];
    }
    dp[i][a[i]%k] = max(dp[i][a[i]%k], a[i]);
    ans = max(ans, dp[i][0];
}

PS: u only actually need 2*k memory, though I am lazy.

→ Ответить

tfg

7 лет назад, # ^ |

← Rev. 3 →

You can actually get O(n) if you store minimum subsegment modulo k.

We want (sum[r] — sum[l — 1]) % k == 0. That also means that sum[r] % k == sum[l — 1] % k. You just need to remember the minimum sum[x < r] such that it has the same remainder when you divide by k to get the maximum answer. So just pass through the array and see if you have a new answer + update the position sum[x] % k if you need to.

Edit: this is the O(nlogn) code that works for any k (considering things don't overflow)

#include <iostream>
#include <map>

typedef long long ll;

int main()
{
	ll n, k, sum = 0;
	std::cin >> n >> k;
	std::map<ll, ll> pref;
	pref[0] = 0;
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{
		ll temp;
		std::cin >> temp;
		sum += temp;
		if(pref.count((sum % k + k) % k) == 1)
		{
			ans = std::max(ans, sum - pref[(sum % k + k) % k]);
			pref[(sum % k + k) % k] = std::min(pref[(sum % k + k) % k], sum);
		}
		else
		{
			pref[(sum % k + k) % k] = sum;
		}
	}
	std::cout << ans << '\n';
}

→ Ответить

redocyz

7 лет назад, # ^ |

← Rev. 2 →

you are right! The constraints on k made me look for complexity in terms of k..

though I think I see 2 errors:
1)it should be max right(for the ans part)? since he is looking for the maximum sum.
2) you should print ans instead of sum?

→ Ответить