it’s more like the test cases are distributed. like if N is 10^5, then there will be 1 test case, or if N is 1 in all test cases then there will be 10^5 test cases. when you add all N values in all test cases, it comes to 2 * 10^5.
So in general, all the different values of N in all test cases won’t exceed 2 * 10^5.
Thanks @taran_1407
Also if anyone has actually solved the first subtask and would like to kindly share their approach. I struggled coming up with a brute force solution.
For first subtask-
C++
//Author- Akshit Monga
//solving for subtask-1
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int main()
{
int T=readIntLn(1,1e5);
int sumN = 0;
while(T--){
int n=readIntLn(1,1e5);
sumN += n;
assert(sumN <= 2e5);
int arr[n];
for(int i=0;i<n;i++){
if(i<n-1) arr[i]=readIntSp(1,1e9);
else arr[i]=readIntLn(1,1e9);
}
int p[n];
vector<pair<int,int>> d;
for(int i=0;i<n;i++)
d.push_back(make_pair(arr[i],i));
sort(d.begin(),d.end());
int c=1;
for(auto i:d){
p[i.second]=c;
c++;
}
int mini=INT_MAX;
int maxi=INT_MIN;
int ans=0;
for(int i=0;i<n;i++){
mini=min(mini,p[i]);
maxi=max(maxi,p[i]);
set<int> vals;
for(int j=0;j<=i;j++){
vals.insert(j+1);
}
for(int j=0;j<=i;j++){
vals.erase(p[j]);
}
if((int)vals.size()==0){
ans+=d[maxi-1].first-d[mini-1].first;
mini=INT_MAX;
maxi=INT_MIN;
}
}
cout<<ans<<'\n';
}
assert(getchar()==-1);
cerr<<"SUCCESS\n";
}
Python
'''Author- Akshit Monga'''
# Subtask- 1 O(n*n)
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
n=int(input())
arr=[int(x) for x in input().split()]
vals=[(arr[i],i) for i in range(n)]
vals=sorted(vals)
p=[-1 for i in range(n)]
c=0
for i in vals:
p[i[1]]=c
c+=1
inds=[]
for i in range(n):
if sorted(p[:i+1])==[j for j in range(i+1)]:
inds.append(i)
ans=0
last=0
for i in inds:
ans+=max(arr[last:i+1])-min(arr[last:i+1])
last=i+1
print(ans)
Please provide link to your submission. The link you provided is of an accepted solution.
Please provide link to your submission.
Consider-
Your output- 4
Considering this submission of yours
Input
1
4
7 1 7 13
Expected Output
6
Your Output
12
Even your other submission fails for the above-given test case.
Input
1
6
9 1 6 1 13 17
Expected Output
8
Your Output
0
thank you for helping me out, i understood the problem
@taran_1407
Alternative Implementation :
In the above two multisets, we keep on adding respective elements from A and B. At any point, if both the multisets are same, then that is a good position.
Solution : CodeChef: Practical coding for everyone
This is actually O(n^2). Would fail if max is at first index and rest of the array is sorted.
1 Like
Hi, I could you all guys tell me how you got the approach/intuition for this problem or any problem generally. Do you, after seeing the problem get the intuition, or do you write some examples on your own and try to find patterns or some key observations. And finally, do guys solve based on intuition, or don’t solve it till you can come up with general proof?
How much time is taken in the comparison of two multisets using relational comparisons i.e A==B
where A and B are two multisets of int type.
Here’s my solution:
void solve(){
ll n;
cin>>n;
vl a(n);
take(a);
vl b = {all(a)};
sort(all(b));
multiset<ll> A,B;
ll ans=0;
fr(i,n){
A.ins(a[i]);
B.ins(b[i]);
if(A==B){
auto it1 = B.end();
auto it2 = B.begin();
it1--;
ans+= *it1-*it2;
A.clear();
B.clear();
}
}
cout<<ans;
}
Submission link: CodeChef: Practical coding for everyone
My concept is - (failed)
1.Take two arrays- original (arr), sorted (a2)
2.Now we put loop from 0 to n to create segment and calculate sum of this segment (max-min) simultaneously.
We take a boolean ‘dir’: tells we are looking for left or right end.
- 2.1 To get each ‘l’ we find the first index where a2[i] and arr[i] do not match and then change dir to find ‘r’.
- 2.2 To find each ‘r’ we search the first index where a2[i] and arr[i] match or it is last element and change dir and calculate sum.
sum= sum + sorted[r] - sorted[l] (max-min of current segment).
At the end of loop we get sum as answer.
Solution is here :: https://www.codechef.com/viewsolution/55490919
Now this works for cases that i can think of.
Can anyone suggest cases where it fails…?
Thank You.
Really a tricky question and hard to strike when someone has no knowledge of disjoint sets and multisets. In my approach I simply took two multisets and while traversing the whole array, I was checking whether the subset is the same subset (jumbled) which appeared in the sorted reference array or not. If yes, sort the jumbled subbarray and modify the answer.My Solution
I’m getting only 2 AC(s), remaining are WA…I’ve implemented the logic of editorial itself
Here’s the link to my code:
https://www.codechef.com/viewsolution/55506938
Can anyone point out the mistake?
Consider the input
1
6
1 3 2 3 1 5
Expected Output
2
Your Output
0
1 Like
Ok i got it. 5 4 3 2 1 fails
Thanks again mate!