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

×

CAPPLE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Agarwal
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Adhoc

PROBLEM:

You are given a multiset S of N numbers. Your task is to erase all elements from S. If all elements in S have the same value, you can erase all of them in one move. In the other case, you are allowed to make one specific action: pick any subset A of S such that all elements in A have the same value x, and change values of all elements in A to some y, such that y < x and there is at least one element in S with a value y. Your task is to return the minimum possible number of moves after which S is empty.

QUICK EXPLANATION:

The answer for this question is the number of distinct values in S.

EXPLANATION:

The first observation is that in order to erase all elements of S you have to reduce S to another multiset in which all elements have the same value.

Let d be the number of distinct elements in S.

The second observation is that you have to make at least d moves, because if you made k < d moves, then there exists a move and a value x in S such that you didn't pick x in that move, so you cannot erase it.

The third observation is that you can erase all elements of S in exactly d moves. For example, we can do the following:

Let x_1 < x_2 < ... < x_{d-1} < x_d be the values of elements in S.

In first move we pick all elements with value x_d and we reduce their values to x_{d-1}. In the second move, we pick all elements with value x_{d-1} and we reduce their values to x_{d-2} and so on. After d-1 steps all elements in S have value x_1 and in one move we can erase them.

Based on the second and the third observation we conclude that the minimum number of moves to do the task is d.

Time Complexity:

O(N) time complexity per one testcase. Since all values are small (up to 10^5) you can count the number of distinct elements using a simple look-up array.

AUTHOR'S AND TESTER'S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

This question is marked "community wiki".

asked 15 Dec '14, 19:43

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

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,631
×1,643
×934
×228

question asked: 15 Dec '14, 19:43

question was seen: 3,125 times

last updated: 15 Dec '14, 19:43