heap sort

// array  is 1 based
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int arr[1000000];
int n;
// heapify function works as .
// compare cur node with both of its child
// if  it is greater than both of  its child than leav
// else swap with the greatest , and call heapify for the node with which we have
// replaced it
void heapify(int n,int cur)// cur is curren node and n is passed so that  it will note access any node out of the  array as a child.
 {
    int lid=2*cur;
    int rid=2*cur+1;
    int maxi=arr[cur];
    int mid=cur;
      if(lid<=n && arr[lid]>maxi)
         {
           maxi=arr[lid];
           mid=lid;
   }
 
   if(rid<=n && arr[rid]>maxi)
         {
           maxi=arr[rid];
           mid=rid;
   }
   if(cur!=mid)
    {
     swap(arr[mid],arr[cur]);
      heapify(n,mid);
}
 
 }

 int heapsort()                                  
  {
   //  a max heap is a heap in which any node contains valeus >= its both child
    // ie  arr[i]>=arr[2*i] and arr[i]>=arr[2*i+1];
    // we are taking  1 based array
    // start building heap from index n/2 since all the nodes from index n/2+1 to n are the leaf nodes
    // also heap is a complete binary tree means nodes will be filled form left to rigsht ..
   
    for(int i=n/2;i>=1;i--)// start building heap from bottom up or from a node at a level 1 above than the leaf.
       {
          heapify(n,i);
}

for(int i=n;i>=1;i--)//  in heach iterqation extract 1 element from the  top of the heap
                     // and decrease size of the array by 1 from end and again build heap to get max of remaining element
                     // at top
 {
      swap(arr[i],arr[1]);
      heapify(i-1,1);
 }
 // printing sorted array ..
 for(int i=n;i>=1;i--)
 {
   cout<<arr[i]<<" ";
 }
  }
 
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
  {
    cin>>arr[i];
  }
  heapsort();
}

to do dp

to do

1>

D. Red-Green Towers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are r red and g green blocks for construction of the red-green tower. Red-green tower can be built following next rules:

• Red-green tower is consisting of some number of levels;
• Let the red-green tower consist of n levels, then the first level of this tower should consist of n blocks, second level — of n - 1 blocks, the third one — of n - 2 blocks, and so on — the last level of such tower should consist of the one block. In other words, each successive level should contain one block less than the previous one;
• Each level of the red-green tower should contain blocks of the same color.

Let h be the maximum possible number of levels of red-green tower, that can be built out of r red and g green blocks meeting the rules above. The task is to determine how many different red-green towers having h levels can be built out of the available blocks.

Two red-green towers are considered different if there exists some level, that consists of red blocks in the one tower and consists of green blocks in the other tower.

You are to write a program that will find the number of different red-green towers of height h modulo 109 + 7.

Input

The only line of input contains two integers r and g, separated by a single space — the number of available red and green blocks respectively (0 ≤ r, g ≤ 2·105, r + g ≥ 1).

Output

Output the only integer — the number of different possible red-green towers of height h modulo 109 + 7.

Sample test(s)

input

4 6

output

2

input

9 7

output

6

input

1 1

output

2

Note

The image in the problem statement shows all possible red-green towers for the first sample.

cbzcbzx


2-->>>

1900. Brainwashing Device

Time limit: 1.0 second
Memory limit: 64 MB

While some people travel in space from planet to planet and discover new worlds, the others who live on Earth still have to get up in the morning, go to work, return back home and try to have a rest. They don't like this situation anymore and envy people who can afford space travel.

That doesn't suit the government of the Earth. Their goal is to make everyone happy, but that is difficult. That is why the government decided to do some tests in the small town of Lux, and then, if everything goes well, to apply the experience to other cities.

Lux's distinctive feature is that it is situated in a long underground tunnel and there is only one train inside it. Almost everyone in the town uses the train. The government has bought a brainwashing device and installed it in the train. The device is new and its effects aren't well understood yet, so the government decided to limit the number of the spans where the device would be turned on. Statistics on number of passengers travelling between each pair of stations every morning have already been collected. Now the government should pick the spans where the device could be used to make most of the people happy.

Input

The first line contains integers n and k that are the total number of the stations and the number of spans between adjacent stations where the device could be turned on (2 ≤ n ≤ 500; 1 ≤ k ≤ n − 1). The i'th of the next n − 1 lines contains n − iintegers. The j'th integer is the number of passengers traveling from i'th to (i + j)'th station. These numbers are non-negative and don't exceed 100. You can assume that every passenger uses the train only once a day.

Output

In the first line output the total number of people who will become happy because of the device. In the second line output kintegers in the ascending order that are the indexes of the spans where the device should be turned on. The span between the station i and i + 1 has the index i. If the problem has multiple solutions you can output any of them.

Sample

input	output
4 1 5 0 6 5 3 5	14 3

Problem Author: Alex Samsonov (prepared by Alexander Fetisov)

3->>>

Parade

Attempted by: 36

/

Accuracy: 90%

/

Tag(s):

 Algorithms, Hard  Edit

PROBLEM

EDITORIAL

MY SUBMISSIONS

ANALYTICS

 Brasil National Progra...

A school has N students, numbered from 1 to N. Each student wears a T shirt of some color. The T shirt of the i^thstudent is of color C_i.
The teachers of the school want to organize a parade. In the parade, there will be some students standing in a straight line in increasing order of height.
The number of students in the line should be atmost M and atleast 1. Your job is to calculate the number of distinct parades that can be organised.

Two parades are said to be distinct if the sequence made by colors of T-shirts worn by students are different.

For each student i, you are given one student L_i such that height(L_i) < height (i).
L_i for the shortest student will be 0. The height of all students are distinct.

Input:

The first line contains the number of test cases, T.
The first line of each test case contains two space separated integers, N and M.
N lines follow. The i^th line contains two space separated integers, L_i and C_i.

Output:

For each test case, output a single line containing the answer of that test case.
Output the answer modulo (10^9+7)

Constraints:

1<=T<=50

1<=M<=N<=10^3

0<=L_i<=N
All L_i are distinct

1<=C_i<=1000

Problem Statement in native language: http://hck.re/HRCC50

---

Sample Input

(Plaintext Link)

3
2 1
0 1
1 1
2 1
0 1
1 2
2 2
0 1
1 2

Sample Output

(Plaintext Link)

1
2
3

Explanation

In the first test case, there are two students. The student 1 is shorter than student 2. As M=1, we want only parades with 1<=number of students<=1. As both students have T shirt of same color, it doesn't matter which student we choose because both of them have the same T shirt color. So only one parade is possible i.e. [1]

In the second test case, two parades are possible { [1] ,[2] }.
In the third test case, three parades are possible { [1] , [2] and [1,2] }.

NOTE: The sequence of numbers inside [ ] is the sequence of T shirt colors.

---

Time Limit: 1 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded if any testcase passes.

Allowed languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Problem Author: Abhinav Sharma

Problem Tester: Bidhan Roy

4>>>>>>>>