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>>>>>>>>

Sliding Window Minimum Implementations

Sliding window minimum is an interesting algorithm, so I thought I would implement it in a bunch of different languages. This repository contains (or will contain) implementations of the algorithm in different programming languages. What follows is an explanation of the problem and the algorithm.

The repository is stored at https://bitbucket.org/keegan_csmith/sliding-window-minimum

A copy of this article is stored athttp://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

Problem Introduction

The algorithm is sometimes also referred to as the Ascending Minima algorithm. I learnt the algorithm from a South African Computer Olympiad camp some years ago. I couldn't find any references to it in any journal, however there are some explanations on the Internet.
Given an array ARR and an integer K, the problem boils down to computing for each index i: min(ARR[i], ARR[i-1], ..., ARR[i-K+1]). The algorithm for this "slides" a "window" of size K over ARR computing at each step the current minimum. In other words the algorithm roughly follows this psuedocode:

for (i = 0; i < ARR.size(); i++) {
  remove ARR[i-K] from the sliding window
  insert ARR[i] into the sliding window
  output the smallest value in the window
}

The sliding window algorithm does the remove, insert and output step in amortized constant time. Or rather the time it takes to run the algorithm is O(ARR.size()).

Naive Algorithms

Before I explain the O(1) solution for sliding window minimum, let me explain some alternative solutions which are suboptimal. The most straight-forward solution is for each index i in ARR, simply loop over the values from ARR[i-K+1] to ARR[i] and keep track of the minimum:

void brute_force_time(std::vector<int> & ARR, int K) {
  for (int i = 0; i < ARR.size(); i++) {
     int min_value = ARR[i];
     for (int j = i - 1; j >= min(i - K + 1, 0); j--)
        min_value = min(min_value, ARR[j]);
     std::cout << min_value << ' ';
  }
}

The above C++ code runs in O(NK) where N = ARR.size(). We can improve on this by using a sorted set to speed up the minimum value queries to logarithmic time:

void logarithmic_time(std::vector<int> & ARR, int K) {
  std::multiset<int> window;
  for (int i = 0; i < ARR.size(); i++) {
     window.insert(ARR[i]);
     if (i - K >= 0)
       window.erase(window.find(ARR[i - K]));
     std::cout << *window.begin() << ' ';
  }
}

The window can have at most K elements, so the multiset insert, find and begin operations all take time O(logK). This gives us an overall time of O(NlogK).
We can improve the run-time by a constant factor by using a heap instead. All the heap operations (except finding the minima) have the same run-time complexity as the multiset versions, however heaps empirically perform better. We need to be able to remove arbitrary items in the heap, but the implementation of heaps in C++ (std::priority_queue) does not support this operation. Luckily a technique I have mastered in real life helps us get around this: we delete lazily. For each element in the priority queue we also store what index it was inserted from. Then when we query what the smallest element is, we discard it if its index falls out of range of our current window.:

void logarithmic_time2(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (-ARR[i], i). We use -ARR[i] since
  // priority_queue is by default a max-heap, but we want a min-heap. By
  // negating the value on insertion and removal we get a min-heap. One can
  // also use the rather ugly
  // std::priority_queue< std::pair<int, int>,
  //                      std::vector< std::pair<int, int> >,
  //                      std::greater< std::pair<int, int> > >

  std::priority_queue< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     window.push(std::make_pair(-ARR[i], i));
     while(window.top().second <= i - K)
       window.pop();
     std::cout << (-window.top().first) << ' ';
  }
}

Note that deleting lazily can actually make this algorithm perform rather badly. If the input is N values from N to 1, then a value is never deleted from the priority queue leading to O(logN) insertions. However, on average this is empirically faster than the multiset version.

Sliding Window Minimum Algorithm

The idea of lazily deleting elements is a salient one, but by putting in a bit more effort when inserting an element into the window we can get amortized O(1) run-time. Say our window contains the elements {1, 6, 7, 2, 4, 2}. We want to add the element 5 to our window. Notice that all elements in the window greater than 5 will now never be the minimum in the window for future i values, so we might as well get rid of them. The trick to this is to store the numbers in a deque [1] and whenever inserting a number x we remove all numbers at the back of the deque which are greater than equal to x. Notice that if the deque was sorted before inserting, it will still be sorted after inserting x. Since the deque starts off sorted, it remains sorted throughout the sliding window algorithm. So the front of the deque will always be the smallest value.
The front of the queue might have a value which shouldn't be in the window anymore, but we can use the lazy delete idea with the deques as well. Now each element of ARR is inserted into the deque and deleted from the deque at most once. This gives as a total run-time of O(N) for the algorithm (amortized O(1) per insertion/deletion). Pretty sweet:

void sliding_window_minimum(std::vector<int> & ARR, int K) {
  // pair<int, int> represents the pair (ARR[i], i)
  std::deque< std::pair<int, int> > window;
  for (int i = 0; i < ARR.size(); i++) {
     while (!window.empty() && window.back().first >= ARR[i])
       window.pop_back();
     window.push_back(std::make_pair(ARR[i], i));

     while(window.front().second <= i - K)
       window.pop_front();

     std::cout << (window.front().first) << ' ';
  }
}

----------------------------------------implementation----------------------------

#include<iostream>
using namespace std;
  int arr[1000000];
  #include<bits/stdc++.h>
int main()
{
 int t;
     cin>>t;
     while(t--)
      {
       int n,k;
       cin>>n>>k;
       for(int i=1;i<=n;i++)
        {
         cin>>arr[i];
}
queue<pair<int,int> > q;


// note that queue will contains only nos in the increasing order  if any smaller
// no try to insert pop() , all biger number till rear

for(int i=1;i<=n;i++)
 {

  q.push(make_pair(arr[i],i));
 
  while(!q.empty())
    {
     if(q.front().first>arr[i] || q.front().second<i-k+1) q.pop();
     else break;
   }
   if(i>=k)// means than atleast k numbers are covered from array
  cout<<"till  "<<i<<" min "<<q.front().first<<endl;
 }
  }
}

optimal game stratgy

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a)  scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod  1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a);
#define pl(a) printf("%lld\n",a);
#define pi(a) printf("%d\n",a);
#define pd(a) printf("%lf\n",a);
#define pf(a) printf("%f\n",a);
lli  dp[3000][3000];
int solve(lli  arr[],int start,int end)
 {
   if(start>end)return 0;
  if(dp[start][end]!=-1)
 {

  return dp[start][end];
  }
  else if(start==end)
   {
 
    return dp[start][start];
   
  }
  else if(start+1==end)
   {

 
    return max(arr[start],arr[start+1]);
   
   }
 //  else if(dp[start][end]!=-1) return dp[start][end];
   else
   {
   
    lli val1=arr[start]+min(solve(arr,start+2,end),solve(arr,start+1,end-1));
     lli  val2=arr[end]+min(solve(arr,start,end-2),solve(arr,start+1,end-1));
   
     dp[start][end]=max(val1,val2);
   }
return dp[start][end];
 }
int main()
{

int n;
lli arr[10000];
int t=1;
while(1)
 {
    cin>>n;
   lli  tot_sum=0;
     if(n==0) return 0;
    
    
     else
     {
      for(int i=0;i<n;i++)
{
cin>>arr[i];
      tot_sum+=arr[i];
}
}
for(int i=0;i<n;i++)
 {
   for(int j=0;j<n;j++)
   dp[i][j]=-1;
 }
for(int i=0;i<n;i++) dp[i][i]=arr[i];

solve(arr,0,n-1);
 cout<<dp[0][n-1]<<endl;
 }
}

ncr using inverse modulo

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define ll long long int
#define mod 1000000007

ll powmod(ll a,ll b)
    {
    b=mod-2;
    ll result=1;
    while(b)
        {
        if(b&1)
            result=(result*a)%mod;
        b=b>>1;
        a=(a*a)%mod;
    }
    return result;
}
int main() {

    int t,n,m,i;
    ll fact[201];
    fact[0]=fact[1]=1;
    for(i=2;i<201;i++)
        fact[i]=(fact[i-1]*i)%mod;
    scanf("%i",&t);
    while(t--)
        {
        scanf("%i%i",&n,&m);
        ll ans=fact[n]*powmod((fact[m],mod);
        printf("%lli\n",ans%mod);
    }
    return 0;
}

all destination shortest path using dijkestra and priority queue

#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long int lli;
int visited[10010];
lli dist[10010];
#define pp pair<int,int>
// comparator for min heap
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};

int main()
{
    int t;
     cin>>t;
      while(t--)
       {
        list<pair<lli,lli> >li[10010];
        lli n,m;
 
       cin>>n>>m;
       
          for(int i=0;i<m;i++)
           {
            lli a,b,c;
             cin>>a>>b>>c;
            li[a].push_back(make_pair(b,c));
            li[b].push_back(make_pair(a,c));
           
           }
         
             

            for(int i=1;i<=n;i++)
             {
              visited[i]=0;
              dist[i]=INT_MAX;
}


//  declaring pq;
            priority_queue<pp, vector<pp > , Prioritize > q;
           dist[1]=0;
       
           lli ans=0;
           int f=0;
           // need to find distance of all node from 1
           lli start=1;
           q.push(make_pair(1,0));
           while(!q.empty())
            {
           
   
            list<pair<lli,lli> > :: iterator it;
            lli start=q.top().first;
         
           
             q.pop();
            if(visited[start]==1) continue;
            visited[start]=1;
         
            for(it=li[start].begin();it!=li[start].end();it++)
             {
       
              if(!visited[it->first]  && dist[it->first]>dist[start]+it->second)
              {
             
               q.push(make_pair(it->first,dist[start]+it->second));
             
                dist[it->first]=dist[start]+it->second;
              }
             
             }
             
}
               

           
           for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
         }
         return 0;
       }
     
     

INVERSION_COUNT

#include<iostream>
using namespace std;
 typedef long long int lli;
    lli temp[10000000];
      lli arr[1000000+10];
 #include<bits/stdc++.h>
 lli ic=0;
lli merge (lli arr[],lli start,lli mid,lli end)
   {
 
     lli i=start, j=mid+1;
     lli p=start;
   
      lli lc=0;
       while(i<=mid && j<=end)
        {
       
        if(arr[i]>arr[j])
        {
        lc+=mid-i+1;
        temp[p++]=arr[j];
        j++;
}
else
{
temp[p++]=arr[i++];
}
       
}
while(i<=mid) temp[p++]=arr[i++];
while(j<=end) temp[p++]=arr[j++];
for(int i=start;i<p;i++) arr[i]=temp[i];
return lc;
   }
 
 void  divide(lli arr[],lli start,lli end)
  {
 
  if(start<end)
  {
 
  lli mid=(start+end)/2;
 
  divide(arr,start,mid);
  divide(arr,mid+1,end);
  ic+=merge(arr,start,mid,end);
  }
 

  }
 
 int  main()
  {
  int t;
  cin>>t;
  while(t--)
   {
    ic=0;
    lli n;
    cin>>n;
 
    for(int i=0;i<n;i++)
     {
       cin>>arr[i];
       
 }
 divide(arr,0,n-1);
  cout<<ic<<endl;
}
return 0;
  }