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

×

Editorial for ENG5 - PELT2019

Problem setter: aditya10_

DIFFICULTY: Medium

PREREQUISITES: Dynamic Programming, Bit Masking

EXPLANATION: We will take a mask of the number of items M. 1 at ith index represent that item of type i is included. Mask at any time represents the type of items which are ordered continuously from the left. We will find the cost of adding every type of item which was not there in the mask ie the bits which were unset.
Cost of adding an item of type X means the number of items to select such that item of type X occurs in succession. The item of type X here is added after the type of items which have already been placed continuously i.e. the bits which were set in the mask.
Dp array stores the cost of each mask.
The above can be represented as:

code

Now How to find the cost of adding a type of item X?
Let the total number of items be tot which are set in the mask. And the number of items of type x be c. Now the cost will be the number of items which are not of type x in the range [tot+1,tot+x].

For this we will maintain an array which stores the frequency of each type of item. And a pref array pref[N+1][M+1]. pref[idx][x] represent the number of items of type x upto index idx.

code2

Author’s Solution: click here

Tester’s Solution: click here

asked 11 Jan, 18:16

panik's gravatar image

5★panik
1166
accept rate: 7%

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
×281
×126
×10
×4
×2

question asked: 11 Jan, 18:16

question was seen: 122 times

last updated: 11 Jan, 18:16