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

×

QSET - Editorial

9
4

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Segment Trees, Number Theory

PROBLEM:

Given a string of digits of length N<(105), do two kind of operations(total of M<(105):

  • Type 1: 1 X Y: Replace AX by Y.
  • Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by AC, AC+1 ... AD.
    Formally, you have to print the number of pairs (i,j) such that the string Ai, Ai+1 ... Aj, (C ≤ i ≤ j ≤ D), when considered as a decimal number, is divisible by 3.

QUICK EXPLANATION:

Use segment trees. Store in node for each interval,
- the answer for that interval
- count1[], where count1[i] denotes number of prefixes of interval which modulo 3 give i.
- count2[], where count2[i] denotes number of suffixes of interval which modulo 3 give i.
- total, sum of interval modulo 3.

Perform merge operations in constant time.

EXPLANATION:

We basically need to find number of subarrays in range L to R who sum is divisible by 3.
Queries are for ranges, where we have to count subarrays, we can use segment tree because we can solve our problem if we can merge two intervals and find answer for the new interval in constant time.
We can use segment tree because we can take two different subarrays and merge them in constant time to find answer for the new large subarray.
In segment tree, each subarray's information is recursively calculated from two smaller subarrays.
While querying, we can merge different(and disjoint) subarrays to get answer for range L to R.
So, we need to design the node of our segment tree. We store in our node, the answer for current subarray. Also, we will store two arrays count1[] and count2[] as defined above.
While merging two intervals(say node1 and node2), our new answer will be node1.answer + node2.answer, plus count of valid subarrays which start in node1 and end in node2.

image

This pseudo code will clear the things.

//merges node1 and node2 and stores in node3
merge(node1, node2, node3)
    //non intersecting subarrays of node1 and node2
    node3.ans = node1.ans + node2.ans
    for i = 0 to 2:
        for j = 0 to 2:
            //if adding suffix of node1 with modulo i
            //to prefix of node2 with modulo j
            //gives us a subarray divisible by 3
            if (i + j) % 3 == 0:
                //all pairs of valid indexes are valid subarrays
                node3.ans += node1.count2[i] * node2.count1[j]

Note now, we also need to build both array count1 and count2 for the new interval.
Let's build count1 first:
Say there were count1[i] prefixes of node2 which when taken modulo with 3 gave i. Now, all such prefixes will give (i + node1.total) % 3, where node1.total denotes total sum of interval modulo 3. So, we can calculate new arrays. In similar way, we can calculate count2.

image

//building count1 and count2
for i=0 to 2:
    node3.count1[i] = node1.count1[i] + node2.count1[3-node1.total+i]
    node3.count2[i] = node2.count2[i] + node1.count2[3-node2.total+i]

So, complexity is: O(N log N) preprocessing and O(log N) per query.

ALTERNATIVE SOLUTION:

Suppose we keep in segment tree for each node, how many prefix sums in this interval are divisible by 0,1,2.
For a query [L,R], we just have to count number of prefix sums in interval [L,R] divisible by 0,1,2(let's call them s1,s2,s3).
Our answer will be choose(s1,2)+choose(s2,2)+choose(s3,2). Why? Because, suppose prefix_sum[i] % 3 = prefix_sum[j] % 3, then sum of substring [i+1, j] is divisible by 3.

For update query(mark A[x] = y), since we are keeping prefix sum modulo 3, for range [x, N], we increase/decrease each prefix sum by k(k<3). We can do this using lazy propagation.

SOLUTIONS:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 12 Jan '15, 15:06

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 14 Jan '15, 00:04

1

Someone please fix the "Access Denied" issue!

(18 Jan '15, 00:51) nisargshah953★

This is my favorite in this contest ;-)

My solution was in O(sqrt(N) * N) - simplified idea is to cut the array in sqrt(N) segments, segment can be updated in sqrt(N) time and query is in 3 * sqrt(N) (I handle first and last separately - 2 * sqrt(N) and then I use precalculated values in all segments in between - last sqrt(N) ).

Who is greedy can see my solution, I'll add detailed description a little later.

link

answered 12 Jan '15, 15:17

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 12 Jan '15, 15:42

why don't you use CHelper + IntelliJ IDEA?

(12 Jan '15, 15:35) code_overlord3★

I'm an Eclipse guy. I tried IntelliJ IDEA and also NetBeans several times but I do not like those (maybe there is not rational reason for that)...

What I do not like on IDEs (not sure now if it is the same in IntelliJ) the most is, that there have to be just one main project/class and especially for contests I'm using it different way (I have same experience with all C++ IDEs, also Eclipse for C/C++ one :-( ) that's my biggest problem in using other IDEs... In Eclipse I'm using run this class as Java/JUnit and I'm happy...

(12 Jan '15, 15:41) betlista ♦♦3★
1

Ok. But, just so you know ... you can achieve the same in IntelliJ IDEA.

(12 Jan '15, 15:59) code_overlord3★

Here is my code based on the above approach ..

http://ideone.com/NMQlRR

I also coded it during the contest itself .. :D

(14 Jan '15, 01:41) ma5termind3★

Can someone please explain alternative solution for this problem, we have count of prefixes with remainder 0, 1 and 2 when divided by 3. Now how do we get number of substrings divisible by 3 using this information? I got that given two prefixes with equal remainder, we will have a substring which is divisible by 3. Hence if,

  • s1 = no. of prefixes giving remainder 1,
  • s2 = no. of prefixes giving remainder 2,
  • s3 = no. of prefixes giving remainder 0,

our answer should be s1(s1-1)/2 + s2(s2-1)/2 + s3*(s3-1)/2 ? For ex- if the whole string is "133",

  • s1 = 3 (1, 13, 133)
  • s2 = 0,
  • s3 = 0,

Our answer is 3*(2)/2 = 3.

Not what editorial suggest, i.e., s1*s1 = 9.

Am I missing or misunderstood something?

link

answered 12 Jan '15, 23:23

akumar3's gravatar image

3★akumar3
1426
accept rate: 0%

edited 12 Jan '15, 23:28

yes, you are right, that was probably a typo. fixed that!

(14 Jan '15, 00:03) darkshadows ♦5★

@akumar3 : I saw your solution for this problem. https://www.codechef.com/viewsolution/5863202 Can you tell why have you incremented curr when i = 0 in processResult() ?

(25 Oct '15, 12:10) kay_kay4★
1

That is because the case with 0 remainder is special. For every two prefixes with equal remainder, we have 1 substring which is divisible by 3;

Now consider following string:

33

Prefixes:

3, 33 (both gives remainder 0 when divided by 3)

If you apply above formula, you will get '1' substring which is divisible by 3. But here both the original prefixes are also divisible by 3.

To account this fact, we have to update our formula for the case when remainder is 0, so if we have N prefixes which gives remainder 0; our answer will be:

= (N(N-1))/2 + N (original prefixes)

= (N*(N+1))/2

(25 Oct '15, 15:23) akumar33★

Thank you @akumar3.

(25 Oct '15, 20:14) kay_kay4★

please explain node3.count1[i] = node1.count1[i] + node2.count1[3-node1.total+i]

why this term:[3-node1.total+i] why not (i + node1.total) % 3

link

answered 15 Jan '15, 20:36

Mocshare's gravatar image

3★Mocshare
3115
accept rate: 0%

Hello! I am posting the link to my solution for QSET... I am getting TLE for the subtask 4.. Can anyone please help me in optimizing my update_segment_tree function to avoid TLE???? An explanation added will be of very much help.. Thank you! http://www.codechef.com/viewsolution/5857954

link

answered 12 Jan '15, 17:25

singh_abhinav's gravatar image

4★singh_abhinav
265615
accept rate: 0%

Although I used the same idea as given here, I got TLE on both subtask 3 and 4. Can anyone tell why? http://www.codechef.com/viewsolution/5790168

link

answered 12 Jan '15, 20:17

rishul_nsit's gravatar image

4★rishul_nsit
78351020
accept rate: 0%

This problem can be solved with TREAP , basicly whe storage the prefix sum mod 3 and we have 3 arrays that means T[ j ][ i ] = (AC[ i ] % 3 == j) where AC = prefix sum mod 3 and when we need to know the answer queries we need to know how many ones there has in T[ 0 ] , T[ 1 ] , T[ 2 ] in their respective intervals. Finally for update queries we only swap sufix of T .

Sorry for my bad english.

link

answered 13 Jan '15, 02:42

boxer2012's gravatar image

5★boxer2012
1
accept rate: 0%

Can anyone please explain the alternative solution in detail once more. I cannot understand why answer will be choose(s1,2)+choose(s2,2)+choose(s3,2).

link

answered 14 Jan '15, 17:13

raj1247's gravatar image

3★raj1247
131
accept rate: 0%

I don't know what choose(sx, 2) means, but you can read my comment above if it helps :)

(14 Jan '15, 23:56) akumar33★

the links of Setter solution give xml error ... please correct

link

answered 14 Jan '15, 22:25

shaky99's gravatar image

2★shaky99
1
accept rate: 0%

The links to setters and tester's solution is showing xml error! Please check the links!

link

answered 15 Jan '15, 00:27

div25's gravatar image

3★div25
1
accept rate: 0%

Editorial is pretty much clear.. and explanatory.. but can anyone plzz help me how to built a query function.. means how can query for the range like 4 to 7 in segment tree when array size,n=8 only summing of node.ans is not enough so i am not able to manipulate how count1 and count2 is added.. or it is to be added to find ans in the same way like in merge operation explained above.. @darkshadows please explain it..Would be very much thankful if anybody can help me to understand..

link
This answer is marked "community wiki".

answered 15 Jan '15, 21:27

lrn2code's gravatar image

2★lrn2code
11
accept rate: 0%

edited 15 Jan '15, 21:29

count1[], where count1[i] denotes number of prefixes of interval which modulo 3 give i. - count2[], where count2[i] denotes number of suffixes of interval which modulo 3 give i.

what does this mean?

link

answered 18 Jan '15, 18:50

aniruddha_paul's gravatar image

2★aniruddha_paul
35213
accept rate: 0%

why are we doing this

 for i = 0 to 2:
        for j = 0 to 2:
            //if adding suffix of node1 with modulo i
            //to prefix of node2 with modulo j
            //gives us a subarray divisible by 3
            if (i + j) % 3 == 0:

in the pseudo code ?

link

answered 23 Jan '15, 08:27

bicepjai's gravatar image

2★bicepjai
11
accept rate: 0%

what function choose(x,y) does?

link

answered 23 Jan '15, 21:50

parbays's gravatar image

1★parbays
1
accept rate: 0%

how could i modify this to check if the substring between C and D inclusive is divisible by 3 ?? Or am i trying to explore a wrong approach for doing this ?

link

answered 29 Jul '16, 22:26

coolcode's gravatar image

3★coolcode
1
accept rate: 0%

include <stdio.h>

int main() { int rows, cols, i, j;

/*
 * Reads number of rows, columns to be printed
 */
printf("Enter number of rows: ");
scanf("%d", &rows);
printf("Enter number of columns: ");
scanf("%d", &cols);

for(i=1; i<=rows; i++)
{
    for(j=1; j<=cols; j++)
    {
        //Print 1 if its first or last row
        //Print 1 if its first or last column
        if(i==1 || i==rows || j==1 || j==cols)
        {
            printf("*");
        }
        else
        {
            printf(" ");
        }
    }

    printf("\n");
}

return 0;

}

link

answered 30 Jul '16, 07:42

dhanush004's gravatar image

0★dhanush004
1
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:

×15,852
×2,655
×1,767
×639
×204
×28

question asked: 12 Jan '15, 15:06

question was seen: 11,795 times

last updated: 30 Jul '16, 07:42