selfcompiler's blog

By selfcompiler, history, 3 months ago, In English,

Hi Everyone I am trying to solve Problem
I gone through editorial but not able to get it . Below is the function where i got stuck .Could someone please tell me how to calculate below function efficiently for each n .

Editorial Link

Read more »

 
 
 
 

By selfcompiler, history, 3 months ago, In English,

Hi Everone , I tried problem https://community.topcoder.com/stat?c=problem_statement&pm=9728 , not able to comeup with any proper logic . I checked the editorial also, solution is not clear could someone help to understand how to approach this problem .

Read more »

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

By selfcompiler, history, 9 months ago, In English,
N red and M blue points on the plane in such a way that no three points lie on the same line.what is the number of distinct triangles with vertices in red points which do not contain any blue point inside.I am not able to understand and visualize from editorial .
Editorial Link

Read more »

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

By selfcompiler, history, 9 months ago, In English,

We have set of intervals [theta,-theta] . I want to find out the optimal value of theta [-180,180] which lies in the maximum no of intervals . Value of theta can be float . Can you please help me find the way to find out the optimal theta.

Read more »

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

By selfcompiler, history, 9 months ago, In English,

Every Friday night, Alice, Clara and Mary go to Koerner’s pub to relax after a long week. At the pub, lots of guys ask them for their phone numbers. In fact, the three ladies are so popular that they have started counting the number of times each one is asked for her phone number during one evening. On day i, Alice, Clara and Mary were asked Ai , Ci and Mi times, respectively. 100 Fridays have passed, and the records were lost, but there are 3 things Alice still remembers. 1. X of the 100 days, Ai was equal to Ci . 2. Y of the 100 days, Ci was equal to Mi . 3. Z of the 100 days, Ai was equal to Mi

I want to find out the how many maximum and minimum no of day Ai,Bi,Ci will be equal ?

I tried to use inclusion exclusion principle not able to get it exactly how to apply here ?

Read more »

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

By selfcompiler, history, 9 months ago, In English,

A king wishes to go for a walk of a square chessboard with the following conditions: • Each two consequent cells of the path must be adjacent, i.e., share an edge or a corner (thus, a cell may have up to eight adjacent cells). • Each cell must be visited exactly once; the first and the last cells of the path must coincide (thus, the first cell of the path will be actually visited twice). • The path must have no self intersections (we may think of a path as a closed polyline with vertices at cells’ centers). Your task is to find the maximal possible length of a king’s path (here we mean the length of the polyline, not the number of king’s moves).

Sample Input

N=1 ans=0 N=2 ans=4 N=3 ans=9.414

I am not able to get it , would you please help me understand to this ? Thank you .

Read more »

 
 
 
 

By selfcompiler, history, 10 months ago, In English,

Hi All, DEC Long challenge is over , can anyone please give some hint how to approach this problem Sereja and Increasing subsequence. (sorry for bad english)

Edit :editorials are not published yet :(

Read more »

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

By selfcompiler, history, 2 years ago, In English,
 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By selfcompiler, history, 2 years ago, In English,

I try to find out some sources to Learn Nim and grundy theorem . But I did not find any explanation , why the logic works .

  1. like xor(n1,n2,n3....nk)=0
  2. How to find grundy number with some explanation . why does this approach work ?

Please refer some problems .

Read more »

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

By selfcompiler, 3 years ago, In English,

I tried this Problem then i am able to get the dp relation dp[i][k]=(1/(i+1))*dp[i-1][k]+(i/(i+1))*dp[i-1][k-1] where dp[i][k] represent the probability of collection of k candies in first i bags . But here the value of N is very high so i am unable to solve it,that will be great help,Thanks in advance

Read more »

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

By selfcompiler, 3 years ago, In English,

I tried this Problem but getting WA ,I don't know why i am keep getting WA .If some one find out the fault in my code that would be great help!!

Your code here...
#include<iostream>
#include<cstdio>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std;

#define si(x) scanf("%d",&x);
#define s2i(a,b) si(a)si(b)
#define sl(x) scanf("%I64",&x);
#define s2l(a,b) sl(a)sl(b)
#define ss(x) scanf("%s",x);

#define pi(x) printf("%d",x);
#define pl(x) printf("%I64",x);
#define ps(x) printf("%s",x);
#define line printf("\n");
#define space printf(" ");
#define p2i(a,b) pi(a) space pi(b)
#define p2l(a,b) pl(a) space pl(b)

#define vinit(_size_,_value_) resize(_size_,_value_)
#define _mem(value,_array_) memset(_array_,0,sizeof(_array_))
#define ULL long long int
//#define ULL unsigned long long int
#define _pi pair<int,int> 
#define _pl pair<LL,LL>
#define _vi vector<int> 
#define _vl vector<LL>
#define _vpi vector< _pi >
#define _vpl vector< _pl >

#define _f first
#define _s second
#define _pb push_back
#define _mp make_pair
ULL mygcd(ULL a,ULL b)
{
        ULL c;
        while(a!=0)
        {
           c=a;a=b%a;b=c;
        }
        return b;
}
ULL mylcm(ULL a,ULL b)
{
    ULL ans=a;
    ans=ans/mygcd(a,b);
    ans=ans*b;
    return ans;
}
ULL N,M,g,x,y,gx,gy,go,k;
int main()
{
    int tc;
    cin>>tc;
    while(tc--)
    {
       scanf("%lld%lld",&M,&N);
       g=mygcd(M,N);
       if(g==1)
       {
               cout<<M*N<<endl;
               continue;  
       }
       x=M/g;
       y=N/g;
       k=x*y;
       gx=mygcd(g,x);
       gy=mygcd(g,y);
       k=k*gx*gy;
      printf("%lld\n",k);
   
    }
    return 0;
}

`

Read more »

 
 
 
 

By selfcompiler, 3 years ago, In English,

I tried this problem VPALIN ,I know it can be solvable using Trie ,but i am unable to frame the idea would anyone like to help to frame the idea :) ?

Read more »

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

By selfcompiler, 3 years ago, In English,

Hii I am trying to solve this problem http://www.spoj.com/problems/ZQUERY/ after thinking so many days i am not able to come up with efficient solution ,would any one like to suggest some idea, how to solve this ?

Read more »

 
 
 
 

By selfcompiler, 3 years ago, In English,

I read the editorial of the this Problem but i am not able to get the idea, would anyone like to help me to understand the solution of problem .

Read more »

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

By selfcompiler, 3 years ago, In English,

Actually This is a piece of question ,i am struggling in that part so i want help . 1. so the problem is you have two equations — v=x*v1+y*v2
x*s1+y*s2<=s

you have the values of v1,v2,s1,s2,s all are fit in 32 bit integer .you have to maximize the value of v ?? Constraints : s1>=1,s2>=1,v1>=1,v2>=1,v>=1,s>=1,x>=0,y>=0 and s1,s2,v1,v2,x,y,v,s all are positive integer.

Read more »

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

By selfcompiler, 3 years ago, In English,

Here is Problem Link i read its editorial but unable to understand it would anyone like to make me understand this problem ?

Read more »

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

By selfcompiler, 3 years ago, In English,

Here is the Link of the topcoder problem Link i read its editorial but not able to get it would anyone like to help me to understand this ??

Read more »

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

By selfcompiler, 3 years ago, In English,

I want to know how to create suffix link in suffix automaton ? I tried a lot, I read suffix automaton from this site site but unable to get the idea . I tried some papers from that to hard to understand for me.If someone want to explain ,it will be great help for me and another naive coders .Hope if you use figures(pictures) that will be awesome.

Read more »

 
 
 
 

By selfcompiler, 3 years ago, In English,

Can anyone Guide me how to optimize this relation  where b[j]>=b[j+1] and a[i]<=a[i+1] .I know for optimization use convex hull trick and i read convex hull trick ,but i don't know how to use this trick to optimize this Dp relation.

Read more »

 
 
 
 

By selfcompiler, 3 years ago, In English,

I am trying to solve the problem MATSUM on spoj.I try it using 2D Binary Indexed Tree.But keep getting Time Limit Exceeded.If my approach to solve this problem is not good enough then please suggest another methods.If my approach is correct then please guide me how to get rid-off from TLE.

My code is below

Your code here...
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<map>
#include<stdlib.h>
#include<string.h>
using namespace std;

#define g getchar_unlocked()

int scan()//fast input output
{
    int t=0;
    char c;
    c=g;
    while(c<'0' || c>'9')
    c=g;
    while(c>='0' && c<='9')
    {
    t=(t<<3)+(t<<1)+c-'0';
    c=g;
    }//end fast input output
    return(t);
}

vector<int> Matrix[1026];
int N;  // MAXVAL for Binary indexed tree tree(1 based indexing)
void initialize()
{
     scanf("%d",&N);
     for(int i=0;i<N;i++)
      Matrix[i].resize(N+2);
     return ; 
}
int Freq_at_idx(int idx,int vec_idx)
{
    int sum=Matrix[vec_idx][idx];
    if(idx>0)
    {
     int z=idx-(idx&-idx);
     idx--;
     while(idx!=z)
     {
                  sum-=Matrix[vec_idx][idx];
                  idx-=(idx&-idx);
     }
             
    }
    return sum;
}
void update(int vec_idx,int idx,int v)
{
     while(idx<=N)
     {
                  Matrix[vec_idx][idx]+=v;
                  idx+=(idx&-idx);
     }
     return ;
}

// it gives the sum of all the elements from 1 to idx of vector Matrix[vec_idx]

int Cumilative_Freq(int vec_idx,int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=Matrix[vec_idx][idx];
        idx-=(idx&-idx);
    }
    return sum;
}
void set_value(int x,int y,int v)
{
     int v1;
     v1=Freq_at_idx(y+1,x);
     v=v-v1;
     if(v==0)
      return ;
     update(x,y+1,v);
}
void get_sum(int x1,int y1,int x2,int y2)
{
     int sum=0;
     for(int i=x1;i<=x2;i++)
     {
             sum+=Cumilative_Freq(i,y2+1)-Cumilative_Freq(i,y1);
     }
     printf("%d\n",sum);
     return ;
}
int main()
{
    int x,y,v,x1,x2,y1,y2;
    char str[5];
    int tc;
    //scanf("%d",&tc);
    tc=scan();
    while(tc--)
    {
    initialize();
    scanf("%s",str);
    while(str[0]!='E')
    {
             if(str[1]=='E')
               {
                   //scanf("%d%d%d",&x,&y,&v);
                   x=scan();
                   y=scan();
                   v=scan();
                   set_value(x,y,v);
               } 
              else
              {
                   //scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                   x1=scan();
                   y1=scan();
                   x2=scan();
                   y2=scan();
                   get_sum(x1,y1,x2,y2);
              }
              scanf("%s",str);    
     }
     for(int i=0;i<N;i++)
      Matrix[i].clear();
    }
    return 0;
}


Read more »

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

By selfcompiler, 3 years ago, In English,

I read the editorial of this Problem But i did't understand it's bruteforce solution (the one ,that is given in the editorial) how it work, it will be great help if you make me understand how it work.If anyone provide Dp solution,please provide it and the reference code.

Read more »

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

By selfcompiler, 5 years ago, In English,

[problem:http://codeforces.com/contest/268/problem/C] HELP me in this problem can any one explain the logic behind this ?

Read more »

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

By selfcompiler, 5 years ago, In English,

[problem:http://codeforces.com/contest/268/problem/C] HELP me in this problem can any one explain the logic behind this ?

Read more »

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

By selfcompiler, 5 years ago, In English,

HERE IS THE CODE can any one t

include <stdio.h>

include <stdlib.h>

const int MAX = 86044176; const int LMT = 9267; const int LEN = 5000000;

int flag[MAX>>6], primes[LEN+5];

define ifc(x) (flag[x>>6]&(1<<((x>>1)&31)))

define isc(x) (flag[x>>6]|=(1<<((x>>1)&31)))

void sieve() { register int i, j, k; for(i = 3; i < LMT; i+=2) { (i<100) && printf("%d\n",ifc(i)); if(!ifc(i)) for(j=i*i, k=i<<1; j < MAX; j+=k) isc(j); } primes[1] = 2; for(i=3, j=2; i < MAX && j <= LEN; i+=2) if(!ifc(i)) primes[j++] = i; }

void print() { for(int i=0;i<(MAX>>6)&&i<300;i++) printf("%d\t",flag[i]); printf("\n"); /*for(int i=0;i;i++) printf("%d\t",primes[i]); printf("\n"); */

}

int main() { char buff[11]; //register int q = atoi(fgets(buff, 11, stdin));

sieve(); //print(); //while(q--) printf("%d\n", primes[atoi(fgets(buff, 11, stdin))]); return 0; }

Read more »

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

By selfcompiler, 5 years ago, In English,

http://codeforces.com/problemset/problem/31/E can any one explain how to solve this problem i am very weak in dp ? how to think plz explain it fully (sorry for my poor english )

Read more »

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