Contest Talk ------------------ Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017)
Highlights : Did the 1st (A) question and Got AC in the first go, struggled till the end to get the 2nd question (B) right.
Analysis :
A. Arpa and the Mexican Wave The first question seemed difficult at first , so I took a lot of time thinking about all the scenarios that could be possible, and finally typed in the solution ( all in all taking 42 minutes , in contrast, the person who submitted it the first who took less than a minute :O )
And my code follows :
int main(){
ll n,k,t; // Unnecessarily taken long long ( int would have done )
cin>>n>>k>>t;
if(t>(n+k))t=(t%(n+k)); // check out this UNNECESSARY STEP !! :-/
if(t<=k){
cout<<t;
}
else {
if(t<=n)cout<<k;
else cout<<k-(t-n);
}
return 0;
}
Should have really given attention to this constraint :
1 ≤ t < n + k
All one had to do keeping the constraints in mind was this :
int main(){
int n,k,t;
cin>>n>>k>>t;
cout<<min(t,min(k,n+k-t));
return 0;
}
In retrospect, this could very well have been done in under a minute if one understood the problem statement fast enough, as the implementation is easy and short !
B. Arpa and an exam about geometry
If you've read my previous blog post , you know about my love for geometry problems and the deep rooted connection they have with Star Trek . This question is a perfect example of how I link those 2 things together .
The question talks about a rotation of the triangle about an axis, so as to find out if the previous points once rotated would move to the subsequent points or not. The first thing that I imagined was an equilateral triangle ( As I would later find out this to be a case of not reading the question thoroughly enough ). I submitted the solution right away and failed the pretest :-| . Then I went on to again read the question slowly and carefully this time. So, we only had to ensure that 2 sides were of the same length ( that the only way you could the point from one point to the next ( of 2 points ) ), and not just any 2 sided needed to be same ( the side B and C were the ones that needed to have equal length ).
This is the image that came to my mind right away :
I finally got it !! ( or so I thought ) I used the distance formula and took all the values as doubles to compare the 2 sides that mattered, got it Wrong on the pretests. (NOTE TO SELF: Avoid floating points like the PLAGUE! )
As I would later find out , almost every one who eventually got this problem right , got it wrong the first time ( because they too used floating points, but later realised that it was not needed and the length could be compared directly (in integer form ) as the square-roots of the integers could be cancelled on both sides ( and that would lead to integer numbers for comparison ) ).
I was still unable to get the problem accepted ( as I did not check for collinearity of all points ). Later I did it by using the point slope method ( which does not require floating points and gets an integer result ).
Code follow :
#define sqr(x) (x)*(x)
typedef long long ll;
ll length(ll ax,ll ay,ll bx,ll by){
return (sqr(bx-ax)+sqr(by-ay));
}
int main(){
ll ax,ay,bx,by,cx,cy;
cin>>ax>>ay>>bx>>by>>cx>>cy;
ll l1=length(ax,ay,bx,by);
ll l3=length(bx,by,cx,cy);
if( (by-cy)*(bx-ax)==(bx-cx)*(by-ay) ){
cout<<"No";
}
else if(l1==l3){
cout<<"Yes";
}
else cout<<"No";
return 0;
}
....................
All questions after this remain unsolvable by me because of my lack of enough algo-ds knowledge ...
Effect on my progress graph: My graph dipped lower! :-|
