codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

340D.md (2086B)


      1 Source: https://codeforces.com/problemset/problem/340/D
      2 
      3 D. Bubble Sort Graph
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with *n* elements *a*1, *a*2, ..., *a**n* in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it *G*) initially has *n* vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode).
     22 
     23 ```
     24 procedure bubbleSortGraph()  
     25     build a graph G with n vertices and 0 edges  
     26     repeat  
     27         swapped = false  
     28         for i = 1 to n - 1 inclusive do:  
     29             if a[i] > a[i + 1] then  
     30                 add an undirected edge in G between a[i] and a[i + 1]  
     31                 swap( a[i], a[i + 1] )  
     32                 swapped = true  
     33             end if  
     34         end for  
     35     until not swapped   
     36     /* repeat the algorithm as long as swapped value is true. */   
     37 end procedure
     38 ```
     39 
     40 For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph *G*, if we use such permutation as the premutation *a* in procedure bubbleSortGraph.
     41 
     42 Input
     43 
     44 The first line of the input contains an integer *n* (2 ≤ *n* ≤ 105). The next line contains *n* distinct integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ *n*).
     45 
     46 Output
     47 
     48 Output a single integer — the answer to the problem.
     49 
     50 Examples
     51 
     52 Input
     53 
     54 ```
     55 3  
     56 3 1 2
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 2
     63 ```
     64 
     65 Note
     66 
     67 Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].