It was the first round in which I managed to solve 6 problems out of 7, submitting the last one in last 3 seconds. Following are some thoughts I had while solving those problems and some mistakes I made. I make it a point to refer the notebook I use for writing observations and calculations during contest for writing these blogs. So that even if I delay the post by a day or two I don’t miss much on the content. So let’s start with the first problem.
Solved during contest
A. Favorite sequence
- At first glance, it looked like simple use of a deque.
deque<int> q;
for(int i=0;i<n;i++){
cin>>x;
q.push_back(x);
}
for(int i=1;i<=n;i++){
if(i&1){cout<<q.front()<<" ";q.pop_front();}
else{cout<<q.back()<<" ";q.pop_back();}
}
- It would have saved me 3 minutes but ended up implementing a more contrived solution with two pointers managing start and end of an array.
B. Last Year’s Substring
- You have to tell if it is possible to take a prefix and a suffix of the given string and merge them to form “2020”.
- So iterate on the length of the prefix which from 0 to 4 and take the remaining from suffix, if you hit “2020” then the string is good.
for(len=0;len<=4;len++){
string prefix=s.substr(0,len);
string suffix=s.substr(n-len);
if((prefix+suffix)=="2020"){puts("YES");return;}
}
puts("NO");
C. Unique Number
- Simple complete search problem.
- One observation is that you don’t need 0 because requirement is off smallest integer with a given sum, so 0 doesn’t help in any way.
void dfs(string s){
int sum=0;
for(auto i:s)sum+=(i-'0');
if(sum>50)return;
if(dp[sum]!=-1)dp[sum]=min(dp[sum],stoll(s));
else{
if(!s.empty())dp[sum]=stoll(s);
}
int mx='0';if(!s.empty())mx=s.back();
for(char i=mx+1;i<='9';i++){
dfs(s+i);
}
}
D. Add to Neighbour and Remove
- Thought it would be solvable using dynamic programming by looking at the constraints and the answer it needed, used up about 20 minutes to find a recurrence then jumped over to E1 struggled with that for 10 minutes then came back to D.
- Problem is to find the maximum number of partitions the given array can be divided into such that all partitions have equal sum.
- First observation is that total sum should be divisble by the sum of the partition.
- It is feasible to iterate on the sum of the first partition i.e. prefix sum and find out if we can make it till the end with the given sum.
int ans=n-1;
set<int> s;
vector<int> p(n+1);
for(int i=1;i<=n;i++){
p[i]=p[i-1]+a[i-1];
s.insert(p[i]);
}
for(int i=1;i<=n;i++){
int x=p[i];
if(p[n]%x!=0)continue; //first observation
bool ok=1;
int parts=0;
for(int cur=x;cur<=p[n];cur+=x){
parts++;
ok&=(s.find(cur)!=s.end());
}
int moves=n-parts;
if(ok)ans=min(ans,moves);
}
E1. Close Tuples (easy version)
- How many tuples of 3 elements exist in given array such that difference between maximum and minimum element in the tuple is less than or equal to two?
- I try to solve such problems by looking at the contribution of each element in the answer, and then adjust for overcounting.
- So for every element, if it is the minimum element in the tuple other two elements can be chosen from all +1 and +2’s. Similarly if it is the maximum element in the tuple than other two elements can be chosen from all -1’s and -2’s. How to count the tuples in which it is neither maximum nor minimum?
- Trying all possible scenarios for the current element, this is what I submitted in contest to get AC.
reverse(all(a));
for(int i=0;i<n;i++){
ans+=f[a[i]+1]*f[a[i]];
ans+=f[a[i]-1]*f[a[i]];
ans+=f[a[i]+2]*f[a[i]];
ans+=f[a[i]+1]*f[a[i]+2];
ans+=f[a[i]+1]*f[a[i]-1];
if(a[i]>=2)ans+=f[a[i]-2]*(f[a[i]]+f[a[i]-1]);
if(a[i]>=2)ans+=(f[a[i]-2]*(f[a[i]-2]-1))/2;
for(int k=-1;k<=2;k++)ans+=(f[a[i]+k]*(f[a[i]+k]-1))/2;
f[a[i]]++;
}
- It is a pretty hacky way to go about this problem, as I missed the crucial observation that order doesn’t matter, which is very helpful to solve its harder version.
F. The Treasure of The Segments
-
In last 15 minutes I decided to solve this one over E2 because I wasn’t making any headway in solving the latter.
-
In a good set of segments there will exist a segment such that it intersects all other segments. Goal is to find the largest set of segments that is good.
-
So, if we count for every segment, the number of segment it intersects then the answer would be the maximum number among them. Add 1 to it if you don’t consider a segment’s intersection with itself.
-
Now all elements not in the largest set need to be removed.
-
How to count for every segment the number of segment it intersects? I don’t know.
-
Can we count the complement instead? Can we count the segments that don’t intersect with given segment fast enough such that the calculation can be done for all the segments?
-
Counting the complement is easier. Let’s say there are two segments [l1, r1] and [l2, r2].
-
These two segments don’t intersect if l1>r2 or l2>r1. These conditions can’t be followed simultaneously, so no overcounting.
-
Subproblem is to count all l’s greater than current r and count all r’s less than current l.
-
This can be accomplished by simple binary search, if you sort the input obviously and need to make two arrays one sorted on l and other sorted on r.
Solved after contest
E2. Close Tuples (hard version)
- Why order doesn’t matter?
- Consider that instead of an array you are given buckets of numbers where each bucket can hold only one type of number and frequency of the number is equal to the frequency of that number in the array. It is a fancy way to say that you are given frequency array of the given array.
- Now you’re asked to create those tuples, you will end up creating as many tuples as in the original problem. The reason is even if a number comes earlier than some number in the array, what really matters is how it compares to the other number because that comparison decides its position in the array.
- Contribution of every number in the array can be counted by counting only the tuples in which the number is minimum. For that we need frequency of the numbers in [number, number+k] which can be done using binary search (order doesn’t matter, so we can sort the array to do that).