faiyaz26's blog

By faiyaz26, history, 4 years ago, In English,

Is it possible to have update query on mo's algorithm ?

In exact I want to know that whether it is possible to solve this problem by using mo's algorithm ?

I am the setter of the problem, but I have used 2d Interval tree to solve the problem. The code is big and quite messy.

Looking for simpler solution. Can anyone help with some clear explanation ?

Read more »

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

By faiyaz26, history, 4 years ago, In English,

Can anyone help me with this problem ?

12939 — Keep Fit!

I have followed the idea of this problem to solve the problem.

But the complexity becomes Q * NlogN , which gives TLE.

Any optimized idea ?

Read more »

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

By faiyaz26, 5 years ago, In English,

I am stuck with this problem for more than 2 years. :(

Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3871

Lightoj categorized this problem under DP and Segment tree. But I have no idea how to plug this two topic in the solution. Can anyone provide me the solution in descriptive way? :)

Read more »

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

By faiyaz26, 5 years ago, In English,

How to solve this problem (http://uva.onlinejudge.org/contests/337-93cec436/12829.pdf) ? How to get result from 2D grid ? I have some idea about the offline solution, but what about online solution (which is required by this problem) ?

Read more »

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

By faiyaz26, 5 years ago, In English,

I have found that this solution is skipped 8255696.

why is that? what is the reason behind?

though this solution gets accepted after resubmitting!

Read more »

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

By faiyaz26, 5 years ago, In English,

Hello, I tried to solve this problem with Suffix Array : 452E - Three strings . I have seen some solution but unable to understand the idea. Can anyone give me the idea to solve the problem using Suffix Array?

Read more »

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

By faiyaz26, 6 years ago, In English,

I am learning link cut tree. I have seen the research paper and other slides.

But i have a question about this DS. Can LC Tree answer the number of childs under a root's subtree efficienty ? I mean, if I link root of a tree under a node, then if i ask the number of child under the great root, which is root of all the nodes. Can LC answer the question efficiently ? If yes, then how ? How can I propagate the value to all the ancestors ? I have seen one implementation here: 860934

How to modify it ?

Thanks in advance. :)

Read more »

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

By faiyaz26, 6 years ago, In English,

Hello, Today (6th December 2013) from 8AM BDT ACM ICPC Dhaka Regional 2013 will take place at North South University. And there will be a semi-live contest on http://www.codemarshal.com/ , a new cloud based platform to handle the contest. You need to create new account to attend the contest.

Semi-live Contest will start from 3:00 PM BDT, 7 December 2013. You can find your timezone here: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20131207T0900

Link: http://www.codemarshal.com/contests

Good Luck & Have Fun !

Read more »

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

By faiyaz26, 6 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

By faiyaz26, 6 years ago, In English,
 
 
 
 
  • Vote: I like it
  • -36
  • Vote: I do not like it

By faiyaz26, 7 years ago, In English,

I am having problem to see the codes of the participants of this contest :

Codeforces Round #110 (Div. 1)

here is one submission : 1244730

you will see the the text "Program source is not available.".

What is wrong ?

Read more »

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

By faiyaz26, 7 years ago, In English,

for this problem UVA 12501

How to solve this problem with segment tree ?

Read more »

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

By faiyaz26, 7 years ago, In English,

for this problem: 89C - Chip Play My try is: 2462423

I am getting TLE for test 31.

MY solution is N^2. I am trying to solve the problem with dfs type recursion. before recursion i am removing that chip. than after traversing i am putting back that chip like backtracking. I am getting TLE.. How to optimize it ? anybody help!!

Read more »

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

By faiyaz26, 7 years ago, In English,

Is there any online problem classifier or notes on classified problems for UVA Live Archive ? please share the link...

Read more »

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

By faiyaz26, 7 years ago, In English,

for this problem: http://www.spoj.pl/problems/PATULJCI/

i have got some idea from this analysis by COCI. http://hsin.hr/coci/archive/2009_2010/contest3_solutions.zip

so far my implementation is with segment tree, then binary search.

here is my implementation which is getting WA:

/* Bismillahir Rahmanir Rahim */
/*Coder: Ahmad Faiyaz*/

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))

# define VI vector<int>
# define VS vector<string>
# define VC vector<char>

#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()
#define FORIT(i,m) for(__typeof((m).begin()) i=(m).begin();i!=(m).end();i++)
#define pii pair<int,int>
using namespace std;
#define MAX 300005
struct node{
    int number,count;
};

int arr [MAX];
node tree [4*MAX];

vector <int> e [100005];

node combine(node l,node r){
    node ret;
    if(l.number == r.number){
        ret.number=l.number;
        ret.count= l.count+r.count;
    }
    else{
        if(l.count > r.count){
            ret.number= l.number;
            ret.count= l.count-r.count;
        }
        else{
            ret.number= r.number;
            ret.count= r.count-l.count;
        }
    }
    return ret;
}

node make (int val,int c){
    node ret;
    ret.count=c;
    ret.number=val;
    return ret;
}

void build(int node,int left,int right){
    if(left==right){
        tree[node]= make(arr[left],1);
        return;
    }

    int mid= (left+right)>>1;
    build(2*node,left,mid);
    build(2*node+1,mid+1,right);

    tree[node]= combine(tree[2*node],tree[2*node+1]);
    return;
}


node query(int node,int left,int right,int i,int j){
    if(left > j || right <i) return make(-1,-10000);
    if(left>= i && right<=j){
        return tree[node];
    }
    int mid= (left+right)/2;
    return combine(query(2*node,left,mid,i,j), query(2*node+1,mid+1,right,i,j));
}

int main(){
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,q,i,j;

    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        e[arr[i]].pb(i);
    }
    build(1,0,n-1);
    scanf("%d",&q);
    while(q--){
        scanf("%d %d",&i,&j);
        node ret= query(1,0,n-1,i-1,j-1);
      //  cout<<ret.number<<" ";
        int cnt= upper_bound(all(e[ret.number]),j-1)-lower_bound(all(e[ret.number]),i-1);
        int elem= (j-i+1);

        if(2*cnt > elem){
            printf("yes %d\n",ret.number);
        }
        else{
            printf("no\n");
        }
    }

    return 0;
}

as far as i can see, i am doing same thing as told in the problem analysis!! but getting WA!! i have done checking with the official judge data, it seems that query function is not giving correct number for some range!! what to do?

Read more »

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

By faiyaz26, 7 years ago, In English,

I am trying to solve this problem UVA 12477 ( PDF ).

I am thinking about the solution with SQRTN Segment which is described here — http://e-maxx.ru/algo/sqrt_decomposition

I know how to add elements in SQRTN Segment Data Structure. But how to use this data structure when we need to change all the elements for a certain segment to a value X ? Example: Update called 0 in the problem UVA 12477.

Can anyone help me with some good explanations for this array [1 index based ] ?

1 2 3 4 5 6 7

updates: 1. change the values of 3 to 6 to 10. 2. change the value of 1 to 7 to 100. 3. give the sum for 4 to 7.

Read more »

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

By faiyaz26, 7 years ago, In English,

For this problem i have to do 3 kinds of update in Segment Tree. http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3867

To make it in time , i need to use Lazy Propagation. But how to handle all 3 update in lazy propagation ?

I have an idea to make 3 update function with 3 update lazy propagation array.

But when i am going to use query how i am supposed to know which update should be done first due to lazy propagation ?

Can anyone help me ?

Read more »

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

By faiyaz26, 8 years ago, In English,

Can anyone help me on learning Segment tree  by giving some tutorials and nice implementation in c++ ? I have seen the topcoder tutorial , but have not understand it well  :( 

if you give me an implementation in c++ with some comment . it will be great.. :) Thanx in Advance.. :)

Read more »

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