Subset Maxima - Repovive Premier Round 6 | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/c

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Subset Maxima - Repovive Premier Round 6 | Repovive | Repovive

Think of assigning the values $n,n-1,\ldots,1$ . When we decide where value $c$ is placed, every condition with maximum $c$ must use that same position, because $c$ appears only once in a permutation.

So, all subsets $S_i$ with $c_i=c$ must have a common position. Moreover, that position cannot appear in a condition with a smaller maximum, because then placing $c$ there would make that smaller maximum too large.

For each position $v$ , let $mn[v]$ be the minimum $c_i$ over all conditions whose subset contains $v$ . If $v$ is in no subset, set $mn[v]=\infty$ .

Then value $c$ can be placed only at positions that belong to every subset with maximum $c$ and also satisfy $mn[v]=c$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Process values from large to small