Hello, ACM ICPC Dhaka Regional 2021 : Online Replay will be hosted on LightOJ.

Link: https://lightoj.com/contest/acm-icpc-dhaka-2021

Contest date time: Sat Jan 21 2023 15:00:00 GMT+0000

You need to have LightOJ account and need to register for the contest.

Note that, the datasets and limits are adjusted for LightOJ platform.

Enjoy the contest.

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 ?

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 ?

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

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

I have found that this solution is skipped 8255696.

why is that? what is the reason behind?

though this solution gets accepted after resubmitting!

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?

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

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 !

Hello, Today we have TOPCODER SRM 585. Check the time here: http://www.timeanddate.com/worldclock/fixedtime.html?&day=19&month=07&year=2013&hour=11&min=00&sec=0&p1=179

HF & GL !!

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 ?

for this problem UVA 12501

How to solve this problem with segment tree ?

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

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

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?

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.

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 ?

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  :(