pistone's blog

By pistone, 12 years ago, In English

here is a challenging problem in its own : link is below http://codeforces.net/blog/entry/4611

i have tried different approaches for this one , but none produces answers for 10 testcases within 1 minute time .

hope somebody is able to crack it .

Full text and comments »

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

By pistone, 12 years ago, In English

hello ,

i am a newbie in the world of algorithmic competition , and hope if anybody can mentor me in this arena.

Full text and comments »

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

By pistone, 12 years ago, In English

since the min cost flow algorithms operate on integers , if the cost matrix containes double numbers , how can we adapt it to min cost flow algorithms

Full text and comments »

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

By pistone, 12 years ago, In English

can anybody share code snippet for min cost max flow algorithm , specially for the transportation problem types.

Full text and comments »

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

By pistone, 12 years ago, In English

there are 10000 stations numbered from 0 to 9999. from each station , some load has to be transferred to another station by train . the fuel consumption of train between 2 successive station is 1 litre .

Find the minimum amount of fuel , in which loads can be transferred to all the destination stations.

constraints: the load for each station is between 1 and 100 inclusive. a train cannot carry more than 50 kgs of load at one time. a train cannot carry loads of several stations at the same time even if it can take more load . several stations can send their load to a station at the same time.

the first train leaves station 0.

Input : the destination station and load to be transferred for each of the 10000 stations.

need help in solving this problem

Full text and comments »

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

By pistone, 12 years ago, In English

hi all, it would be helpful if somebody can give links to problems related to dfs and bfs.

Full text and comments »

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

By pistone, 12 years ago, In English

given , there are 3 points in 2d space . also there are 10000 points in 2d space . each of the 3 points in the first set can be related to at max 3500 points from the 2nd set. how to assign all the 10000 points in the 2nd set , to the 3 points in 1st set , so that the sum of distances of points in 2nd set from points in 1st set is minimised ?

Full text and comments »

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

By pistone, 13 years ago, In English

There are 10000 stations numbered from 0 to 9999. from each station , some load has to be transferred to another station by train . the fuel consumption of train between 2 successive station is 1 litre .

Find the minimum amount of fuel , in which loads can be transferred to all the destination stations.

constraints: the load for each station is between 1 and 100 inclusive. a train cannot carry more than 50 kgs of load at one time. a train cannot carry loads of several stations at the same time even if it can take more load . several stations can send their load to a station at the same time.

the first train leaves station 0.

Input : the destination station and load to be transferred for each of the 10000 stations.

Full text and comments »

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

By pistone, 13 years ago, In English

there are 10000 stations numbered from 0 to 9999. from each station , some load has to be transferred to another station by train . the fuel consumption of train between 2 successive station is 1 litre .

Find the minimum amount of fuel , in which loads can be transferred to all the destination stations.

constraints: the load for each station is between 1 and 100 inclusive. a train cannot carry more than 50 kgs of load at one time. a train cannot carry loads of several stations at the same time even if it can take more load . several stations can send their load to a station at the same time.

the first train leaves station 0.

Input : the destination station and load to be transferred for each of the 10000 stations.

need help in solving this problem

Full text and comments »

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

By pistone, 13 years ago, In English
is it possible to have codeforces t-shirts , i am ready to buy many

Full text and comments »

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

By pistone, 13 years ago, In English

hi everyone,
Is there any indicative list of datastructure related problems in SGU problem set,
specially  "TREES" .

Full text and comments »

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

By pistone, 13 years ago, In English

my approach is to create 3 rotations for each box  and sort the boxes according to increasing base area.

Then run LIS on the sorted data.

it gives correct results for test samples in the problem , still getting WA.

Need help !!!!

Full text and comments »

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

By pistone, 13 years ago, In English

here is my solution for thi problem from EL JUDGE ,
but the time limit is exceeds by 1 second , 


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct{
 int m;
 int s;
}rec;

bool compare(const rec& r1,const rec& r2)
{
 return(r1.m + r1.s <= r2.m + r2.s);

}

int main()
{
 int n,i,j;
 int best[100000] ;

 cin>>n;
 i = 0;
 vector<rec> v;
 rec r;
 while(i < n)
 {
  //cin>>r.m;
  //cin>>r.s;
  scanf("%d",&r.m);
  scanf("%d",&r.s);
  v.push_back(r);
  i++;
 }
 for(i = 0;i<=n;i++)
  best[i] = 4000000;
 best[0] = 0;

 sort(v.begin(),v.end(),compare);
 int maxcount = 0;
 for(i= 0; i < n;i++)
 {
  for(j = maxcount + 1; j > 0;j--)
  {

   if(v[i].s >= best[j -1] && (v[i].m + best[j -1] < best[j]))
   {
    best[j] = v[i].m + best[j -1];
    if(j > maxcount) maxcount = j;
   }

  }

 }
 cout<<maxcount<<endl;
 return 0;
}



need  help to optimise this ,  the input length can be upto 100000

Full text and comments »

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

By pistone, 13 years ago, In English

hi all ,
i have read few english versions of some russian  programming books .
And my love for them has increased .
But i have one book by  author "Menshikov" . Its is russian language (djvu format).
I want to convert it into english .
Help please !!!!!!!! :)

Full text and comments »

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

By pistone, 13 years ago, In English

for me it wa quite a problem , since i strictly used C++ to solve it.

Full text and comments »

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