### faiyaz26's blog

By faiyaz26, history, 4 years ago, ,

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 ?

• +19

By faiyaz26, history, 4 years ago, ,

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 ?

• +7

By faiyaz26, 5 years ago, ,

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

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? :)

• +19

By faiyaz26, 5 years ago, ,

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) ?

• 0

By faiyaz26, 5 years ago, ,

I have found that this solution is skipped 8255696.

why is that? what is the reason behind?

though this solution gets accepted after resubmitting!

• -7

By faiyaz26, 5 years ago, ,

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?

• +5

By faiyaz26, 6 years ago, ,

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. :)

• +2

By faiyaz26, 6 years ago, ,

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

Good Luck & Have Fun !

• +4

By faiyaz26, 6 years ago, ,

• +73

By faiyaz26, 6 years ago, ,

• -36

By faiyaz26, 7 years ago, ,

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 ?

• +9

By faiyaz26, 7 years ago, ,

for this problem UVA 12501

How to solve this problem with segment tree ?

• +1

By faiyaz26, 7 years ago, ,

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

• -2

By faiyaz26, 7 years ago, ,

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

• +1

By faiyaz26, 7 years ago, ,

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 */

#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?

• 0

By faiyaz26, 7 years ago, ,

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.

• +5

By faiyaz26, 7 years ago, ,

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 ?

• +5

By faiyaz26, 8 years ago, ,

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.. :)