PROBLEM LINK:
Setter: Alei Reyes
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are N dinosaurs under the training of Chef Ada, who are playing football, i-th dinosaur having height i units.
Currently, they are being trained in the following manner.
- Initially, the leftmost dinosaur has football.
- The dinosaur that has the ball, passes it to the nearest dinosaur on the right which is taller than him.
- The previous step continues until the ball reaches the tallest dinosaur and he throws the ball to score a goal!
Chef Ada wants to reorder them in such a manner so that the ball is passed from dinosaur to dinosaur exactly K times.
QUICK EXPLANATION
- If K = 0, we can simply place the tallest dinosaur as the leftmost dinosaur, hence making sure there is no dinosaur to dinosaur pass. We can place remaining dinosaurs after tallest dinosaur in any order.
- Now, in order to have K passes, let’s place K+1 largest dinosaurs in increasing order at the front and remaining dinosaurs in any order at the end. This shall always guarantee K passes.
EXPLANATION
First of all, let us handle a base case where K = 0 that is, we want an ordering where the very first dinosaur is the tallest dinosaur.
Since the tallest dinosaur never passes the football to any other dinosaur, the ordering of dinosaur after tallest dinosaur is irrelevant.
There are multiple possible orderings that may guarantee exactly K passes. I’m describing building one of them.
We can simply place the largest K+1 dinosaurs at the start ensuring exactly K passes and placing remaining dinosaurs after the tallest dinosaur.
Another solution is to place the smallest K dinosaurs in increasing order of height and then placing the tallest dinosaur and then placing the remaining dinosaurs.
General idea is, we keep the first K dinosaurs in sorted order and place the tallest dinosaur at K+1 position to ensure no more than K passes.
Hence, 1 3 5 2 4, 1 2 5 3 4, ```2 4 5 1 3`` are all valid orderings for K = 2
TIME COMPLEXITY
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int t=rint('\n');
assert(1<=t&&t<=256);
while(t--){
int n=rint(' ');
int k=rint('\n');
assert(2<=n&&n<=20);
assert(0<=k&&k<=n-1);
for(int x=0;x<=k;x++){
printf("%d ",n-k+x);
}
for(int i=0;i<n-k-1;i++){
printf("%d ",i+1);
}
puts("");
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int i;
rep(i,k){
cout<<i+1<<" ";
}
int gg=n;
f(i,k,n){
cout<<gg<<" ";
gg--;
}
cout<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
//SOLUTION BEGIN
//Into the Hardware Mode
long mod = (long)1e9+7;
void pre() throws Exception{}
void solve(int TC)throws Exception{
int n = ni(), k = ni()+1;
for(int i = n-k+1; i<= n; i++)p(i+" ");
for(int i = 1; i<= n-k; i++)p(i+" ");pn("");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
void exit(boolean b){if(!b)System.exit(0);}
long IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e6+5;
DecimalFormat df = new DecimalFormat("0.00");
double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
static boolean multipleTC = true, memory = false, fileIO = false;
FastReader in;PrintWriter out;
void run() throws Exception{
if(fileIO){
in = new FastReader("C:/users/user/desktop/inp.in");
out = new PrintWriter("C:/users/user/desktop/out.out");
}else {
in = new FastReader();
out = new PrintWriter(System.out);
}
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();
for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 