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

×

ENTRY - Editorial

PROBLEM LINK:

Contest
Mirror
Practice

Author: Rupesh Maity
Tester: Asim Krishna Prasad
Editorialist: Rupesh Maity

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment Tree, Lazy Propagation

PROBLEM:

Given an array whose elements are set to 0 initially, apply two operations:
Update: given (L, R), update arr[i] = (arr[i] + 1) % 10, for all L <= i <= R.
Sum: given (L, R), find the sum of all the elements of the array in the range L to R (both inclusive).

QUICK EXPLANATION:

Maintain a segment tree where each node contains the count of the number of occurances of each number from 0 to 9 and maintain a lazy component for each of these nodes. An update would require the circular shifting of the count of occurances of these numbers and updating the parent nodes accordingly.

EXPLANATION:

You need to first learn about Lazy Propagation to understand the most standard way to solve this problem. Since we only have integers ranging from 0 to 9, it is possible to maintain the count of occurances of each of these integers in every node of the segment tree. An update to any node requires us to circular shift the occurance count towards the right. That is, if you're supposed to update for a node representing the range (l, r), such that(L <= l <= r <= R), where (L, R) is the update range in the question, the count of occurances of 0 is shited to 1, 1 to 2 and so on till 9 to 0. This is a circular shift. We're doing this because all the 0s in this range are converted to 1s and so on for every element. Remember, we are also maintaining a lazy component to be updated later for all the children. The count of all the parent nodes are updated accordingly in each step. Now to find the sum of this range, we can simply use this count of occurances. Remember to take care of those lazy updates ;)

This editorial was written assuming that you know about lazy propagation. If you don't, I recommend you solve a few basic lazy propagation related questions and come back to this question later.

Author's Solution:

Author's solution can be found here.

This question is marked "community wiki".

asked 06 Oct '16, 18:27

deathsurgeon's gravatar image

4★deathsurgeon
112
accept rate: 0%

edited 06 Oct '16, 20:21


include<stdio.h>

main () { int a [5],i,sum=0,ar [5]; printf ("enter the elements of an array\n"); for (i=0;i <5;i++) scanf ("%d",&a [i]); for (i=0;i <5;i++) { ar [i]=a [i]; sum=sum+ar [i]; printf ("%d",ar [i]); } printf ("%d",sum); }

link

answered 06 Oct '16, 20:13

nidhibt1212's gravatar image

0★nidhibt1212
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:

×2,556
×1,726
×164
×13
×4

question asked: 06 Oct '16, 18:27

question was seen: 763 times

last updated: 06 Oct '16, 20:21