terminated's blog

By terminated, 5 years ago, In English,

Is it possible for a Div2 candidate to make a grup here where people can host contests apart from regular division contests? If yes then how? else if no,then can any one create it for me :)

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By terminated, 5 years ago, In English,

In Problem B of yesterdays contest I wrote this solution and got it wrong on pretest 8

int n;
        cin>>n;
        set<double> s;
        int c1=0;
        double a,b;
        cin>>a>>b;
        double result;int c=0;
        rep(i,n)
        {
            double x,y;
            cin>>x>>y;

            result = atan ((y-b)/(x-a)) * 180.0 / PI;
            if(*lower_bound(s.begin(), s.end(),result)!=result)
                   { c++;s.insert(result);}

            
        }   
        cout<<c<<"\n";

then I wrote this and got it accepted


int n; cin>>n; set<double> s; int c1=0; double a,b; cin>>a>>b; double result;int c=0; rep(i,n) { double x,y; cin>>x>>y; if(x-a!=0) result = (y-b)/(x-a); else result=INF; if(*lower_bound(s.begin(), s.end(),result)!=result) { c++;s.insert(result);} } cout<<c<<"\n";

The only difference between the accepted and unaccepted is the "atan" thing ,,In first case I calculated it using taninverse and In second using normal slope formula,,but I am not able to figure out why the atan fails,,any explanation will help.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By terminated, 6 years ago, In English,

I recently was doing this problem on spoj.It was about finding the number of distinct sub-string in a string.Suffix array was to be used but i didn't knew about suffix arrays.I searched on net and learned about suffix array but when I moved towards implemention all codes available online were a bit lengthy so I implemented my own and came out with this--

#include "bits/stdc++.h"
using namespace std;
 int main(int argc, char const *argsorted_suffixes[])
{
	
		set<string> set1;

		string s="aabaab";

		int n=s.length();
		/*inserting all possible suffixes of string in set1*/
		for (int i = 0; i < n ; ++i) 
		{
			set1.insert(s.substr(i,n-i));
		}

		vector<string> sorted_suffixes(set1.begin(),set1.end()); /*suffix vector(array)*/
		/*Building LCP table*/
		int LCP[set1.size()];

		LCP[0]=0;

		string s4,s5;

		for(int i=1;i<sorted_suffixes.size();i++)
		{
			s4=sorted_suffixes[i-1];
			s5=sorted_suffixes[i];
			int c=0;
			for(int j=0;j<s4.length();j++)
			{
				if(s4[j]==s5[j])
					c++;
				else
					break;
			}
			LCP[i]=c;


		}
		/*LCP TABLE CONSTRUCTED*/
		for (int i = 0; i < sorted_suffixes.size(); ++i)
		{
			cout<<sorted_suffixes[i]<<" "<<LCP[i]<<endl;
		}
}

Here I have not constructed a suffix array rather I have a vector of strings which has the suffixes in sorted order and I think it doesn't make a difference to either have a container of indexes or to have a container of sorted suffixes. This is easy to code and understand.I have tested it for many cases and it works fine, If there is any bug in my code please point out!

Read more »

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it

By terminated, 6 years ago, In English,

Should we really care about Branch Prediction while writing and submitting code on any online judge, as branch prediction drastically can increase or decrease a programs runtime?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it