Full Solution:

• At first get the shortest path tree rooted at S using Dijkstra.Now what we observe is if those edges which are not there in the shortest path tree are deleted ,then it wont affect our result.Also if any edge in the shortest path tree which don't lie on the path from S to T are deleted,then also our answer wont change.
• Now what happens when we delete one of the edge of the shortest path tree is that the tree gets decomposed into two components.

Now imagine how our shortest path from S to T will look like.Let's denote the component in which S lies by A and the component in which T lies by B.Its not possible to reach T without entering the component B(as T lies in component B and S in component A).Consider the earliest moment when we reach component B from A,let that edge ...

Looking for hints,here we go

• if we cut the ith slice into r pieces,then all of them should be of equal length.
• why?
• try yourself !
• this is because if we don't cut them into equal pieces ,then the minimum among them will be <= K(K denotes the length if all the r pieces are of equal length) and max among them >=K ,so they will lead to greater difference.

IOITC syllabus is almost similar to that of IOI. U can also see the problems at IOITC judge to get some idea.

i would rather suggest you to concentrate on jee,otherwise u will regret ur whole life !

It is a classical problem.Number of swaps needed is nothing but the number of inversions in the array.

I have solved it using BIT,below is my code.

#include <bits/stdc++.h>
using namespace std;
const int MAX=5e5;
long long int N,X,ans,arr[MAX];
map<long long int,long long int> mp;
int BITS[MAX];
void update(int X,int delta)
{
while(X<=N)
{
		BITS[X]+=delta;
		X+=(X&-X);
}
}
int query(int X)
{
int res=0;
while(X>0)

can u share ur code ?

that's some solution :D

almost similar problem was asked in a recent codeforces contest

here's my code(very similar to what i coded in that contest :P)

#include <stdio.h>
 
long long int M,T,S,N;
 
int bekar;
int next[300][300],token[300][300],mark[300][300];
 
void final(int M,int T,int ind)
{
	if(ind==0)
 
	{
		printf("%d",M);
		return ;
	}
	final(next[M][T],token[M][T],ind-1);
}
 
void cal(int M,int T,int ind)
{

IARC Judge is giving fatal error for c++ code,so below is my code in C

#include <stdio.h>
#include <string.h>
 
int ind,len,arr[12],mark[12];
 
int main()
{
	char X[12];
	scanf("%s",X);
	len=strlen(X);
	for(int A=0;A<len;A++)
	{
		mark[X[A]-'0']++;
		for(int B=(X[A]-'0')+1;B<=9;B++)
		if(mark[B]==0)
		{
		     arr[ind]=A;
		     ind++;
			 break;		
		}
		if(mark[X[A]-'0']==2||X[A]=='0')
		break;

in case anyone need help,he can go through this code

//C++ code
//Mohammad Zaid
#include "bits/stdc++.h"
using namespace std;
const int MAX=1e6;
long long int N,arr[MAX],dp[MAX][2];
int main()
{
	cin>>N;
	for(int A=1;A<=N;A++)
	cin>>arr[A],arr[A]+=A;
	for(int A=1;A<=N;A++)
	dp[A][0]=max(dp[A-1][0],arr[A]);
       for(int A=N;A>=1;A--)
	dp[A][1]=max(dp[A+1][1],arr[A]);
	for(int A=N;A>=1;A--)
	cout<<max(dp[A][0]+N-A,dp[A+1][1]-A);
	return 0;   
}