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

×

NPLFLC - Editorial

PROBLEM LINK:

Practice
Contest

Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle

DIFFICULTY:

easy

PREREQUISITES:

binary indexed trees, binary search

PROBLEM:

You have an array of n numbers. You need to perform q queries of following type:

  • Change the value at xth index to Y
  • Find if there is a suffix with sum equal to some given value Y

EXPLANATION:

Brute-force : For every query of the first type just update the value in the array. For every second query iterate from the end of the array to see if the suffix sum is equal to some given value.

Now we can see that the suffix sums if ordered from right to left follow the non-decreasing order. So we can use binary search to speed up the calculations. Do a binary search on the length of the suffix and check the sum of the suffix corresponding to this length, if it is greater that the required sum then check on lower lengths else continue the search on higher lengths.

Now the only thing required is to find and update all the prefix sums. For this we can consider the reverse array and use Binary indexed trees or segment trees to update the array values and find the suffix sum faster.

Time Complexity : $O(N*log(N) + Q*log(N)*log(N))$
First creation of BIT takes $O(log(N))$ time for each element. For every query binary search takes $O(log(N))$ steps and every BIT query is $O(log(N))$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here

This question is marked "community wiki".

asked 09 Nov '16, 22:36

aniket20's gravatar image

6★aniket20
2962712
accept rate: 0%

edited 07 Jun '17, 17:26

admin's gravatar image

0★admin ♦♦
19.6k349497539

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,664
×978
×168
×105
×5
×1

question asked: 09 Nov '16, 22:36

question was seen: 434 times

last updated: 07 Jun '17, 17:26