saketag007's blog

Difficult problem
By saketag007, history, 13 days ago, In English

Given a chocolate shop with chocolates priced from 1 to 10^9 consecutively. A student visits the shop for K consecutive days and buys chocolates indexed at (A1,A2,A3...An) on each day. You are given an array 'A' representing the chocolate indexes the student buys each day. Determine the minimum priced chocolate remaining in your shop after the kth day.

Constraints

1 <= N <= 500

1 <= A[i] < 10^9

1<=K<=10^5

Sample Test cases -

A = [1,3,5,7,9]

k = 3

O/P — 8

Explanation -

on 1st day 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (1,2,3,4,5,6,7,8,9.....10^9) ---> (2,4,6,8,10,11,12....10^9)

on 2nd day — again 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (2,4,6,8,10,11,12....10^9) ---> (4,8,11,13,15,16,17....10^9)

on 3rd day — again 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (4,8,11,13,15,16,17....10^9) ---> (8,13,16,18,20,21,22....10^9)

Minimum priced chocolate after 3rd day is 8.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saketag007 (previous revision, new revision, compare).

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saketag007 (previous revision, new revision, compare).

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saketag007 (previous revision, new revision, compare).

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This is an old codeforces contest problem, but I don't remember the number.

→ Reply
»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.com/problemset/problem/1852/A

This is a harder version of what you stated.

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Isn't this actually easier? Because in this case you don't have to worry about elements running out, since the set is of size $$$10^{100}$$$

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's a valid concern, but I think we can avoid it. Imagine that the chocolates from $$$10^9+1$$$ to $$$10^{100}$$$ were present in the chocolate set in the beginning. Note that whenever you remove chocolates above $$$10^9$$$, that does not affect any positions of chocolates below or equal to $$$10^9$$$. That is because in this version we remove large numbered chocolates, rather than simply not removing them in the original version of the problem, and therefore this is the only difference.

      So as long as there exists a chocolate below or equal to $$$10^9$$$ at the end of the operations, the answer for both problems is the same. And this is always true because we remove at most $$$N$$$ chocolates on each of $$$k$$$ operations, and $$$Nk < 10^9$$$.

      → Reply