Pretext
Not a post for almost an year and suddenly a wild post appears out of nowhere. I know. I'm just gonna act as if everything was normal and some dumbass hacker hacked my account and removed the few posts in between. Let me continue in this post about my team experience in the ACM ICPC Kharagpur Online Qualifiers that took place today. (Technically Yesterday. But who cares!)
What Comes after Pretext? Text??
I had just finished eating home cooked Chappatis and a lip-smacking Aloo-Bhindi fry when the contest started. Today was the qualifiers to the Kharagpur On-site regionals for the prestigious ICPC contest. One would think having participated in a ton of contests and a regionals or two before the stress and tension levels to be normal if not cool. It was definitely not the case.
Observing from how Codechef conducted Amritapuri Online my spidey senses told me the contest would start 30 secs before and it did. There it was at 13:59:30 IST sharp. The tingling sensation, the rush of adrenaline and 5 unsolved problems which could be our ticket to the Kharagpur on-site. My team consisted of Sai Kiran who was in his 4th year of B.Tech and Sandeep my class mates. Well-rested and the team spirits high, tabs were rushing on my computer screen to the right of my current tab. All 5 problems were open and each of us attacked a separate problem each.
Sandeep started of with the first problem in the set. The geometry. Little did he know he'd be stuck with it through out the contest. I was reading the second problem which seemed do-able. Not wasting another second I quickly checked out the other problems. With a small constrain and no complications I quickly recognized that the 5th problem was the easiest and was off coding it. The first submission mattered. 2 minutes to code and test the solution and another to add the word 'Case', we clocked our first submission at 00:04:22. Pretty decent.
With sandeep still hacking at the Geometry problem alone, Sai Kiran and me quicky decided that the graph problem was one among the hardest and settled for solving Inversions which indeed turned out to be the second easiest problem. First with an initial idea to simulate the k-swaps with a modification of Bubble sort, the Idea was thorough. A quick insertion of the BIT for counting the Inversion count, our code was set. Hoping to clock a 20 minute submission for the second one, we submitted it, but was awarded with a wrong answer instead. The next submission involved removing the Bubble sort modification upon realising that it doesn't matter which numbers were swapped. This resulted in a wrong answer as well. We both took a brake to help with Sandeep with his idea. He was stuck. 'Modify the closest pair problem?', 'Here's where it fails'. Things didn't look good. We were off. Each working on our own. Thinking where we could have gone wrong. That's when Kiran realised the corner case that we missed. Oh it was stupid. We repeated the same mistake in the practice contest too. We realised we need to buck up. Clocking in at 01:03:00 with 2 penalties we were decently ranked near the 50s.
But with 2 hours to go we knew we had to solve the third to maintain our rank. Since the other two problems lacked any successful submission, we were sure our conclusions were right. Coming back to the geometry problem 4 dis-proved ideas later, we were dead beat. A crazy idea strikes me. To select points at random and keep updating the minimum. Will it work? Don't know. Is there a chance? Yes. A TLE and a resubmission later we were dead beat. Ranking in at 114 we were happy. Not content. Just happy that we put up a decent performance. Awaiting the official results.
After the contest it was depressing to hear that the 70+ submission were not all authentic. I understand finding an idea or an algorithm online. But the same exact problem being previously used in another contest with code available? Heart-breaking. Not that we didn't Google it. But that it wasn't a fair contest. But I'm sure the mistake could be corrected. Copied code be eliminated. But the contest wasn't glitch-free. Just like last time. (Oh yeah! The DP fiasco) Looking forward for a good regionals this year. Adios. Wish all the teams good luck. And as Modi at Madison Square puts it, 'May the force be with you!
Problem E
Cakewalk - Sorting - Print the sum of 3 maximum numbers. n>=3
Problem B
Easy Medium - BIT/Merge Sort - Given an array and a number K, perform exactly k 'adjacent' swaps so that the number of inversions in the array is minimized.
Given that only adjacent swaps may be performed, it can be proved that each swap will decrease (or increase) the number of inversions by at most 1. Calculate the number of inversions I. If K is lesser then the final answer was I - K. If K was greater there were two options. If K - I was odd and even. If K - I was odd, repeated swaps of the same element would end up with one inversion never zero. If it was even then the number of inversions can be maintained at zero. The corner case that we missed was if there were repeated elements. Then the extra swaps can be made on them and the answer is always zero.
Problem A
Medium - Geometry - The intended solution seems to be a modification of the existing closest pair problem. For n value less than 5 we brute force. Refering to ACRush's AC code in the GCJ, it is just an extension of the closest pair. Each recursion keeps track of the minimum sum distance in a global variable. If points lie on (R/2) of the midpoint (where we divide them into two planes) then we select the points. Then for each point on the left side we select all points on the right which lies at most (R/2) distance from it. And for each pair of points in the right we check if it forms a better answer with the current point. We repeat the same by selecting one point on the right and two on the left. The time complexity analysis of this fails me.
AC Rush's code
void solve(int H,int T)
{
if (T-H+1<=5)
{
for (int i=H;i<=T;i++)
for (int j=i+1;j<=T;j++)
for (int k=j+1;k<=T;k++)
checkIt(i,j,k);
return;
}
int M=(H+T)/2;
solve(H,M);
solve(M+1,T);
double sp=(P[M].first+P[M+1].first)/2.0;
vector<pair<double,int> > QL,QR;
for (int i=H;i<=T;i++) if (fabs(P[i].first-sp)<=R/2.0)
if (i<=M)
QL.push_back(MP(P[i].second,i));
else
QR.push_back(MP(P[i].second,i));
sort(QL.begin(),QL.end());
sort(QR.begin(),QR.end());
for (int step=0;step<2;step++)
{
for (int i=0,k=0;i<SIZE(QL);i++)
{
for (;k<SIZE(QR) && QR[k].first<QL[i].first-R/2.0;k++);
int d=k;
for (;d<SIZE(QR) && QR[d].first<=QL[i].first+R/2.0;d++);
for (int a=k;a<d;a++)
for (int b=a+1;b<d;b++)
checkIt(QL[i].second,QR[a].second,QR[b].second);
}
if (step==0)
{
vector<pair<double,int> > T=QL;
QL=QR;
QR=T;
}
}
}
Will solve Problem C and D and update the blog later.
All my solutions to today's problem is available here: https://github.com/ash1794/Share-Code/tree/master/ACMKGP14
Happy Coding!
Update 1: Upon discussion with Sandeep, it became more clear why this would run in time. Not definite. But approximate. Approximate enough for Competitive purposes. (:P) Since this is a direct modification of the closest pair the rough Time Complexity was O(n log n). The part which eluded me was
for (int a=k;a<d;a++)
for (int b=a+1;b<d;b++)
which could contain infinite many points, because this being real numbers. What we do is fix a point on the left hand side, draw a circle of R/2 and pick points on the other side which is within the circle. But this could contain many points. R here is current found minimum of sum of distances. So if there were a lot of points within the circle, the R value would have been much smaller. Since it's not, we don't have as much values as we hoped. Therefore the number of points would be close to ten which is good enough to pass within the time-limits. Pretty Smart.
Not a post for almost an year and suddenly a wild post appears out of nowhere. I know. I'm just gonna act as if everything was normal and some dumbass hacker hacked my account and removed the few posts in between. Let me continue in this post about my team experience in the ACM ICPC Kharagpur Online Qualifiers that took place today. (Technically Yesterday. But who cares!)
What Comes after Pretext? Text??
I had just finished eating home cooked Chappatis and a lip-smacking Aloo-Bhindi fry when the contest started. Today was the qualifiers to the Kharagpur On-site regionals for the prestigious ICPC contest. One would think having participated in a ton of contests and a regionals or two before the stress and tension levels to be normal if not cool. It was definitely not the case.
Observing from how Codechef conducted Amritapuri Online my spidey senses told me the contest would start 30 secs before and it did. There it was at 13:59:30 IST sharp. The tingling sensation, the rush of adrenaline and 5 unsolved problems which could be our ticket to the Kharagpur on-site. My team consisted of Sai Kiran who was in his 4th year of B.Tech and Sandeep my class mates. Well-rested and the team spirits high, tabs were rushing on my computer screen to the right of my current tab. All 5 problems were open and each of us attacked a separate problem each.
Sandeep started of with the first problem in the set. The geometry. Little did he know he'd be stuck with it through out the contest. I was reading the second problem which seemed do-able. Not wasting another second I quickly checked out the other problems. With a small constrain and no complications I quickly recognized that the 5th problem was the easiest and was off coding it. The first submission mattered. 2 minutes to code and test the solution and another to add the word 'Case', we clocked our first submission at 00:04:22. Pretty decent.
With sandeep still hacking at the Geometry problem alone, Sai Kiran and me quicky decided that the graph problem was one among the hardest and settled for solving Inversions which indeed turned out to be the second easiest problem. First with an initial idea to simulate the k-swaps with a modification of Bubble sort, the Idea was thorough. A quick insertion of the BIT for counting the Inversion count, our code was set. Hoping to clock a 20 minute submission for the second one, we submitted it, but was awarded with a wrong answer instead. The next submission involved removing the Bubble sort modification upon realising that it doesn't matter which numbers were swapped. This resulted in a wrong answer as well. We both took a brake to help with Sandeep with his idea. He was stuck. 'Modify the closest pair problem?', 'Here's where it fails'. Things didn't look good. We were off. Each working on our own. Thinking where we could have gone wrong. That's when Kiran realised the corner case that we missed. Oh it was stupid. We repeated the same mistake in the practice contest too. We realised we need to buck up. Clocking in at 01:03:00 with 2 penalties we were decently ranked near the 50s.
But with 2 hours to go we knew we had to solve the third to maintain our rank. Since the other two problems lacked any successful submission, we were sure our conclusions were right. Coming back to the geometry problem 4 dis-proved ideas later, we were dead beat. A crazy idea strikes me. To select points at random and keep updating the minimum. Will it work? Don't know. Is there a chance? Yes. A TLE and a resubmission later we were dead beat. Ranking in at 114 we were happy. Not content. Just happy that we put up a decent performance. Awaiting the official results.
After the contest it was depressing to hear that the 70+ submission were not all authentic. I understand finding an idea or an algorithm online. But the same exact problem being previously used in another contest with code available? Heart-breaking. Not that we didn't Google it. But that it wasn't a fair contest. But I'm sure the mistake could be corrected. Copied code be eliminated. But the contest wasn't glitch-free. Just like last time. (Oh yeah! The DP fiasco) Looking forward for a good regionals this year. Adios. Wish all the teams good luck. And as Modi at Madison Square puts it, 'May the force be with you!
Problem E
Cakewalk - Sorting - Print the sum of 3 maximum numbers. n>=3
Problem B
Easy Medium - BIT/Merge Sort - Given an array and a number K, perform exactly k 'adjacent' swaps so that the number of inversions in the array is minimized.
Given that only adjacent swaps may be performed, it can be proved that each swap will decrease (or increase) the number of inversions by at most 1. Calculate the number of inversions I. If K is lesser then the final answer was I - K. If K was greater there were two options. If K - I was odd and even. If K - I was odd, repeated swaps of the same element would end up with one inversion never zero. If it was even then the number of inversions can be maintained at zero. The corner case that we missed was if there were repeated elements. Then the extra swaps can be made on them and the answer is always zero.
Problem A
Medium - Geometry - The intended solution seems to be a modification of the existing closest pair problem. For n value less than 5 we brute force. Refering to ACRush's AC code in the GCJ, it is just an extension of the closest pair. Each recursion keeps track of the minimum sum distance in a global variable. If points lie on (R/2) of the midpoint (where we divide them into two planes) then we select the points. Then for each point on the left side we select all points on the right which lies at most (R/2) distance from it. And for each pair of points in the right we check if it forms a better answer with the current point. We repeat the same by selecting one point on the right and two on the left. The time complexity analysis of this fails me.
AC Rush's code
void solve(int H,int T)
{
if (T-H+1<=5)
{
for (int i=H;i<=T;i++)
for (int j=i+1;j<=T;j++)
for (int k=j+1;k<=T;k++)
checkIt(i,j,k);
return;
}
int M=(H+T)/2;
solve(H,M);
solve(M+1,T);
double sp=(P[M].first+P[M+1].first)/2.0;
vector<pair<double,int> > QL,QR;
for (int i=H;i<=T;i++) if (fabs(P[i].first-sp)<=R/2.0)
if (i<=M)
QL.push_back(MP(P[i].second,i));
else
QR.push_back(MP(P[i].second,i));
sort(QL.begin(),QL.end());
sort(QR.begin(),QR.end());
for (int step=0;step<2;step++)
{
for (int i=0,k=0;i<SIZE(QL);i++)
{
for (;k<SIZE(QR) && QR[k].first<QL[i].first-R/2.0;k++);
int d=k;
for (;d<SIZE(QR) && QR[d].first<=QL[i].first+R/2.0;d++);
for (int a=k;a<d;a++)
for (int b=a+1;b<d;b++)
checkIt(QL[i].second,QR[a].second,QR[b].second);
}
if (step==0)
{
vector<pair<double,int> > T=QL;
QL=QR;
QR=T;
}
}
}
Will solve Problem C and D and update the blog later.
All my solutions to today's problem is available here: https://github.com/ash1794/Share-Code/tree/master/ACMKGP14
Happy Coding!
Update 1: Upon discussion with Sandeep, it became more clear why this would run in time. Not definite. But approximate. Approximate enough for Competitive purposes. (:P) Since this is a direct modification of the closest pair the rough Time Complexity was O(n log n). The part which eluded me was
for (int a=k;a<d;a++)
for (int b=a+1;b<d;b++)
which could contain infinite many points, because this being real numbers. What we do is fix a point on the left hand side, draw a circle of R/2 and pick points on the other side which is within the circle. But this could contain many points. R here is current found minimum of sum of distances. So if there were a lot of points within the circle, the R value would have been much smaller. Since it's not, we don't have as much values as we hoped. Therefore the number of points would be close to ten which is good enough to pass within the time-limits. Pretty Smart.
Best of luck for the regionals. This contest again reiterates the standard mantra I guess - "Trust intuition more than correctness.":P
ReplyDelete