Блог пользователя DR.MANHATTAN

Автор DR.MANHATTAN, 7 лет назад, По-английски

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! :-|

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор DR.MANHATTAN, 7 лет назад, По-английски

Highlight: Successfully did Problem — B, but failed to do Problem — A( Awkward !! )

I remember the first time I'd been to an onsite contest ( almost 1 year ago ), the drive to solve the questions the fastest was so high that my brain and my hands literally got paralyzed and I was unable to do anything after attempting the First Question. Thanks to my team mate, we still managed to get the 3rd place and a Cash prize with it ( sweet !! ). What's sad, is that I did not lack in knowledge or skill to solve all the problems in time ( It was not a hard contest ) and could have easily managed to get the first prize and some SERIOUS BOUNTY !!

However, winning the 3rd prize too got me enough bounty to buy this beauty for myself !!

Since then, thanks to Petr and his YouTube contest Video's Petr's competitive programming video with commentary , I've learned the art of staying calm during a contest and got rid of a HUGE limitation.

Contest Talk :

Problem A The question seemed pretty clear, but it seemed confusing as to how to go about it. (_Fun Fact_: this was the first contest I'd seen in which more people got the Problem B right than the number of people that got Problem A right.) So I was not alone in this conundrum. The limits (b<=10^7 and a<=10^7) ensured that a brute force solution was not gonna work. My initial solution did pass the pre-tests, but was hacked in an instant. I understood how to go about the problem only after reading the official editorial.

Problem B Yay!! A geometry problem (barely though!!). After my initial solution for Problem A got hacked, I moved on the problem B and couldn't contain my happiness when I found out that it was a geometry problem and one that I could perhaps SOLVE !! There is something magical about geometry problems!! Perhaps it's because of the images that you form in your mind while solving the problem, the thought process or the imagination that goes into it that if feels kinda STAR-TRECKY !!

When you finally solve a geometry problem ( or at least when I solve one ) It almost feels like I've solved one of the problems that the Star Trek spacecraft encountered along one of its many fantastical voyages :D

However, this question had a pizza (Yum!!) in context, but it was still enjoyable to solve. The picture used for explanation was spot on (though I only saw it after I'd already solved and submitted the solution )

All one had to do was to ensure that the toppings were right within the boundary of the crust. The handy Pythagoras theorem helped to determine the distance of the center of the topping from the origin, subtracting and adding the x coordinate value of the topping to the resulting hypotenuse and checking that the line was within the given boundary ( crust ) ensured that only the right toppings were counted!

int  length(double x,double y,double r_s,double r,double d){
     	double hyp=sqrt(x*x+y*y);
     	return (hyp-r_s>=(r-d) && hyp+r_s<=r);
     }

     int main(){fastio

     	int r,d;
     	cin>>r>>d;
     	int ct=0;
     	test(t){

     		double x,y,r_s;
     		cin>>x>>y>>r_s;

     		if(length(x,y,r_s,r,d))ct++;
     	}


     	cout<<ct;
     }

Got AC in first go !!

My rating too went up thanks to this problem !! ---------- Rest of the problems were beyond the reach of my knowledge as they were topics from Trees and Tries .. etc ... Will get there one day... !!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор DR.MANHATTAN, 7 лет назад, По-английски

Codeforces Round #417 (Div. 2)

  • Could not solve even a single problem ( got stuck on the 1st problem A. Sagheer and Crossroads, as I could not figure out the pattern, and hence brute forced the solution by writing verbose code, which eventually led to a wrong answer as I did not account for all the conditions )

  • Found the description of the problem confusing. Had to read it about 5-6 times, to really understand the question.

  • Later after the contest ended, I took my time and figured out the pattern in the question and coded up the solution quickly( without looking at the editorial ) and got it accepted.

I mean, it was this simple once you see the pattern... ~~~~~

re(i,4){ if(v2[i][3] ) {

       if((v2[i][0]||v2[i][1]||v2[i][2]) ||v2[(i+1)%4][0] || v2[(i+2)%4][1] ||v2[(i+3)%4][2] ){

         cout<<"YES\n";
         return 0;
       }
    }

}
cout<<"NO\n";

~~~~~

The rest of the questions were above my skill level.Even the 2nd question B. Sagheer, the Hausmeister had a DP solution with n*2^n complexity .. My My :-|

Reflection

  • Not all B problems are easy ( i.e just implementation ). Some can have involved concepts like DP. Problems C,D,E remain unsolvable due to lack of algorithm / D.S skill.

  • Think twice code once !!

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор DR.MANHATTAN, 7 лет назад, По-английски

contest — 811

Highlights

_ Questions attempted_ : 2

### ** 1st got accepted A. Vladik and Courtesy ### ** 2nd got hacked B. Vladik and Complicated Book

Question Discussion:

A. Vladik and Courtesy

  • A fairly easy implementation based question.

    -The one who finished the question first , took about 1 minute to do this question, however, I took about half an hour.Moreover, I got my first submission wrong, as I did not totally understand the question clearly enough. I got it right on the second attempt though.

    B. Vladik and Complicated Book
  • I instinctively knew that the solution I provided was suboptimal, but I knew no other way to attempt this question, other than to use sort again and again for each query.

  • Initially, it did pass the pretests ( I didn't know that there were more test-cases that would be run on it later ), and I couldn't believe my luck. Unfortunately, it got hacked in a few minutes :-/.
  • After the contest ended, I went through the editorial ( quickly understood how I could fix the time complexity bottleneck ) and quickly coded up the solution, got AC !!

RESULT : SPECIALIST__ (1404) ( seems like codeforces rating system rewards newbies generously )

Reflection : :

  • Try to read and understand questions quick, keeping in mind the corner cases, and touch the keyboard only after you're convinced that you've thought of all possible corner cases

  • If the solution that you've thought of would get a TLE , due to the constraints of the problem, then don't push your luck. Producing a solution not keeping in mind the constraints is as good as not submitting a solution ( it's even worse, as you lose points as penalty )

  • The first 2 problems are doable by me (considering my present skill level ), as they do not require any algorithmic/ data structure knowledge. Just implementation skill and the skill to spot a pattern / reduce time complexity.

  • The other problems C ,D ,E , do requre algorithmic knowledge... I'll get there once I study up those Algo's and have enough practice to be able to attempt them in competitions.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -28
  • Проголосовать: не нравится

Автор DR.MANHATTAN, 7 лет назад, По-английски

This page will focus on all the coding contests I participate in , on various online judges__

I intended to keep track of the progress I make through participating in these online contests.

I will reflect on the questions that were asked in each contest, to gauge my progress and understanding.

The following is the rating system followed by Codeforces. Sadly, right now I'm in the bottom rung of the rating ladder ( Newbie :-| ).

However, I do intend to get to the top ( Legendary Grandmaster ;) ) . Don't know how long that would take, but it's sure going to be an interesting journey.

Let's begin.....

Полный текст и комментарии »

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится