Author: Roman Rubanenko PROBLEM LINKSDIFFICULTYMedium PREREQUISITESDivideandconquer Problem:Chef is at a restaurant serving dishes. There are N ingredients on the restaurant (which we can assume are numbered from 0 to N1) , and each ingredient is characterized by its beauty which is a positive integer. To order a specific dish, a costumer chooses a segment of ingredients, starting from ingredient whose index is L and ending on the ingredient whose index is R. However, Chef decides not to use the least beautiful ingredient that is on this subset. Given an integer K, we want to count how many segments (L,R) are there such that the sum of their beauty values will be divisible by K after excluding the least beautiful ingredient. Quick Explanation:For the small dataset, a simple bruteforce approach to evaluate all segments will suffice to pass the time limit. For the larger dataset however, the approach we need to use is DivideandConquer. We will see in detail how can this be done. Detailed Explanation:As mentioned above in quick explanation, iterating over all sets and doing the appropriate counting should suffice to solve the small dataset, since constraints are so small. (N <= 1000 and K <= 100 on the subtasks being worth 21 and 39 points respectively.) The subtask with the remaining 40 points allocated to it, is not so simple, since N and K can both be very large. The idea is to use Divideandconquer to speed things up. Let F[L,R] be the answer for the original problem if we are given the array=A[L..R], that is, the array formed only by the given ingredients chosen by a costumer. Let M be the index of the minimal element on this segment. Let's count the number of segments that contain point M. We can count it using partial sums and any data structure that allows us to find a key and the number of times it appears in that same structure (map, for example). Then we need to calculate the segments that does not contain M, so we can have either L1<R1<M or M<L1<R1 so we should add F[L,M1] and F[M+1,R] to F[L,R]. Due to the randomness of the test data, it can be showed that this approach doesn't take a long time. Some tricks and tweaks necessary to get higher points can be seen on both Setter's / Testers solutions. Refer to setter's and tester's solution for implementation details. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONTester's solution will be uploaded soon. Useful Links
This question is marked "community wiki".
asked 30 Jun '13, 14:26

See here for quite simple answered 30 Jun '13, 17:03
@anton_lunyov  hats off for the solution  :d big upvote
(01 Jul '13, 18:35)
@anton_lunyov...simply awesome!!
(16 Jul '14, 05:15)

Could you please tell me where i went wrong? Here is the link to my code : http://www.codechef.com/viewsolution/2305547 answered 01 Jul '13, 00:28

I did not understand one thing, why is K<=100 an advantage? I mean we only divide by K , it does not contribute to complexity, i suppose. answered 01 Jul '13, 13:32

can u give some more test cases!! only one test cae was given!! answered 11 Aug '13, 19:08

I am quite sure my approach is n(logn)^2 ... could you please tell me why I still have TLE for last few tasks? answered 18 Sep '13, 22:07

define _CRT_SECURE_NO_WARNINGSinclude <cstdio>include <cmath>include <cstring>include <cstdlib>include <ctime>include <iostream>include <fstream>include <sstream>include <algorithm>include <string>include <vector>include <set>include <map>include <list>include <complex>include <queue>pragma comment(linker, "/STACK:266777216")using namespace std; define assert(f) { if(!(f)) { fprintf(stderr,"Assertion failed: "); fprintf(stderr,#f); fprintf(stderr,"\n"); exit(1); } }typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<vi> VVI; typedef pair<int,int> PII; typedef vector<pii> VPII; typedef vector<double> VD; typedef pair<double,double> PDD; const int inf=1000000000; const LL INF=LL(inf)inf; const double eps=1e9; const double PI=2acos(0.0); define bit(n) (1<<(n))define bit64(n) ((LL(1))<<(n))define pb push_backdefine sz size()define mp make_pairdefine cl clear()define all(a) (a).begin(),(a).end()define fill(ar,val) memset((ar),(val),sizeof (ar))define MIN(a,b) {if((a)>(b)) (a)=(b);}define MAX(a,b) {if((a)<(b)) (a)=(b);}define sqr(x) ((x)*(x))define X firstdefine Y second//clock_t start=clock(); //fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()start)); define N 201010int mod; int a[N]; LL ans; void rec(int n, int* a) { if(n<=1) return; int ma=inf; for(int i=0;i<n;i++) MIN(ma,a[i]); int m=n/2; for(int k=0;;k++) { if(a[mk]==ma) {m=k; break;} if(a[m+k]==ma) {m+=k; break;} } VI s(m+1,0); int sum=0; for(int i=0;i<m;i++) { sum=(sum+a[i])%mod; s[i+1]=sum; } sort(all(s)); for(int r=m+1;r<=n;r++) { ans += upper_bound(all(s),sum)  lower_bound(all(s),sum)  (r==m+1); if(r==n) break; sum=(sum+a[r])%mod; } rec(m,a); rec(nm1,a+m+1); } int main() { ifndef ONLINE_JUDGEfreopen("tas.in","r",stdin); endifint n; scanf("%d%d",&n,&mod); { for(int i=0;i<n;i++) scanf("%d",a+i); ans=0; rec(n,a); printf("%lld\n",ans); } return 0; } answered 25 Mar '15, 14:47
