TASTYD - Editorial

general
, ,
1

Author: Roman Rubanenko
Tester: Vamsi Kavala
Editorialist: Bruno Oliveira

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Medium

PRE-REQUISITES

Divide-and-conquer

Problem:

Chef is at a restaurant serving dishes. There are N ingredients on the restaurant (which we can assume are numbered from 0 to N-1) , 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 data-set, a simple brute-force approach to evaluate all segments will suffice to pass the time limit.
For the larger data-set however, the approach we need to use is Divide-and-Conquer. 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 data-set, since constraints are so small. (N <= 1000 and K <= 100 on the sub-tasks being worth 21 and 39 points respectively.)
The sub-task 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 Divide-and-conquer 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,M-1] 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 SOLUTION

Can be found here.

TESTER’S SOLUTION

Tester’s solution will be uploaded soon.

Useful Links

Divide and Conquer

4 Likes
2

See here for quite simple O(N log^2 N) solution for arbitrary input data.

12 Likes
3

Could you please tell me where i went wrong?
Here is the link to my code : CodeChef: Practical coding for everyone

4

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.

5

can u give some more test cases!!
only one test cae was given!!

6

I am quite sure my approach is n(logn)^2 … could you please tell me why I still have TLE for last few tasks?

http://www.codechef.com/viewsolution/2687430

7

bad tutorial :confused:

5 Likes
8

#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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 VI;
typedef vector VVI;
typedef pair<int,int> PII;
typedef vector VPII;
typedef vector VD;
typedef pair<double,double> PDD;

const int inf=1000000000;
const LL INF=LL(inf)inf;
const double eps=1e-9;
const double PI=2acos(0.0);
#define bit(n) (1<<(n))
#define bit64(n) ((LL(1))<<(n))
#define pb push_back
#define sz size()
#define mp make_pair
#define 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 first
#define Y second

//clock_t start=clock();
//fprintf(stderr,“time=%.3lfsec\n”,0.001*(clock()-start));

#define N 201010
int 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[m-k]==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(n-m-1,a+m+1);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen(“tas.in”,“r”,stdin);
#endif
int 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;
}

9

@anton_lunyov - hats off for the solution - :d big upvote

10

for N = 10000 your program runs for 3 seconds…

11

@anton_lunyov…simply awesome!!