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

×

BLONDIE - Editorial

PROBLEM LINK:

Practice Link
Contest Link

Author: Ankush Khanna

DIFFICULTY:

Cakewalk

PREREQUISITES:

Prefix sum

PROBLEM:

Given an array with some elements missing, you have to find the missing elements. The missing elements can be found by taking the rounded down average of all the elements traversed before it. The first element is always known.

QUICK EXPLANATION:

Key to AC: Build a prefix sum of the elements traversed so far, whenever we encounter a missing element, take the rounded down average of the current prefix built (till the previous element), update the array element and also the prefix sum. That's it!

EXPLANATION:

There are two ways of solving this problem. The first one is to just follow what is written in the problem statement (the steps) and solve the sub-task 1 for 30 points. Because it will be a brute force solution working in $O(N^2)$ time, and would certainly fail to pass sub-task 2 within the given time constraint.

The other way is to simply keep a track of the accumulated sum by using prefix sum technique. As mentioned in the quick explanation part, the solution just needs to do the same.

Actually, the quick explanation is the real explanation for this problem. My solution for this problem works in $O(N)$ time per test case, and I have used $O(1)$ auxiliary space for my solution.

COMPLEXITY:

Being a regular cakewalk problem, this problem is also solved in $O(N)$ time per test case. The regular solutions that I have seen have taken $O(N)$ auxiliary space for building the prefix sum, but it can also be done using just constant $O(1)$ auxiliary space.

SOLUTION:

Setter's Solution

Feel free to share your approach. If you have any queries, they are always welcome.

This question is marked "community wiki".

asked 03 Feb, 18:17

ankushkhanna's gravatar image

4★ankushkhanna
53
accept rate: 33%

edited 03 Feb, 18:49

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,678
×1,652
×214
×14
×14

question asked: 03 Feb, 18:17

question was seen: 98 times

last updated: 03 Feb, 18:49