×

# TASTYD - Editorial

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

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.

Divide and Conquer

This question is marked "community wiki".

2★kuruma
17.5k72143208
accept rate: 8%

2561312

 10 See here for quite simple O(N log^2 N) solution for arbitrary input data. answered 30 Jun '13, 17:03 6.6k●62●119●138 accept rate: 12% @anton_lunyov - hats off for the solution - :d big upvote (01 Jul '13, 18:35) inseder5★ @anton_lunyov...simply awesome!! (16 Jul '14, 05:15)
 0 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 2★roshi 61●4●9●19 accept rate: 0%
 0 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 6★mbrc 125●2●5●11 accept rate: 0%
 0 can u give some more test cases!! only one test cae was given!! answered 11 Aug '13, 19:08 384●2●6●12 accept rate: 11%
 0 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 answered 18 Sep '13, 22:07 3★kirakira 1 accept rate: 0% for N = 10000 your program runs for 3 seconds... (18 Sep '13, 22:51)
 0 bad tutorial :/ answered 07 Jun '14, 05:36 4★vinitkp 45●2●3●5 accept rate: 0%

# include <queue>

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=1e-9; const double PI=2acos(0.0);

# 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; }

-3
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,933
×102
×14

question asked: 30 Jun '13, 14:26

question was seen: 4,409 times

last updated: 16 Jun '15, 11:09