You are not logged in. Please login at www.codechef.com to post your questions!

×

TASTYD - Editorial

3
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

This question is marked "community wiki".

asked 30 Jun '13, 14:26

kuruma's gravatar image

2★kuruma
17.4k72143208
accept rate: 8%

edited 16 Jun '15, 11:09

vicky002's gravatar image

1★vicky002 ♦♦
2461312


10

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

link

answered 30 Jun '13, 17:03

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138
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) ravifrmiem3★

Could you please tell me where i went wrong? Here is the link to my code : http://www.codechef.com/viewsolution/2305547

link

answered 01 Jul '13, 00:28

roshi's gravatar image

2★roshi
614919
accept rate: 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.

link

answered 01 Jul '13, 13:32

mbrc's gravatar image

6★mbrc
1252511
accept rate: 0%

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

link

answered 11 Aug '13, 19:08

sainath_b's gravatar image

3★sainath_b
3842612
accept rate: 11%

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

link

answered 18 Sep '13, 22:07

kirakira's gravatar image

3★kirakira
1
accept rate: 0%

for N = 10000 your program runs for 3 seconds...

(18 Sep '13, 22:51) betlista ♦♦3★

bad tutorial :/

link

answered 07 Jun '14, 05:36

vinitkp's gravatar image

4★vinitkp
45235
accept rate: 0%

-2

define _CRT_SECURE_NO_WARNINGS

include <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=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; }

link

answered 25 Mar '15, 14:47

nikhil0295's gravatar image

0★nikhil0295
-3
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,831
×102
×14

question asked: 30 Jun '13, 14:26

question was seen: 4,343 times

last updated: 16 Jun '15, 11:09