As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

magieNoire's blog

By magieNoire, 3 years ago, In English,

Hello everyone, I tried recently this problem, but unfortunately I got TLE. I am using an O(nlogn) algorithm as supposed( a segment tree for updating the list and a map to keep track of frequency of each number and it's position ). I think there is some overhead with the update function -- can I rewrite it iteratively ? Any suggestion is welcomed.

Here is my code: link

Note: if someone can redirect me to a non recursive implementation of segment trees that will be great.

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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I solved it with the same (recursive) approach, but I did not use a map. I compressed the input values by using an auxiliary array (and by sorting it). It passes in 0.171 seconds and 3965 KB.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain more. A tiny example will be perfect :)

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 5   Vote: I like it +9 Vote: I do not like it

      For the sample input:

      5
      + 8 (i=0)
      + 6 (i=1)
      + 8 (i=2)
      - 8 (i=3)
      - 8 (i=4)
      

      I keep a copy of the input, I sort the "copy" thus getting this:

      5
      + 6 (i=1)
      + 8 (i=0)
      + 8 (i=2)
      - 8 (i=3)
      - 8 (i=4)
      

      I assign increasing numbers k to "mark" distinct values (in this case there are 2 distinct values):

      5
      + 6 (i=1) (k=1)
      + 8 (i=0) (k=2)
      + 8 (i=2) (k=2)
      - 8 (i=3) (k=2)
      - 8 (i=4) (k=2)
      

      (while computing this, I store for each i the corresponding k).

      Then, for each i (from 0 to q - 1), I add/remove the number (which I get from the "original" input) in/from the k-th position.

      Code here

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks dude! Good explanation and good solution too ;)

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I've used the segment tree realization, which I know as "Implicit segment tree". The main idea is to build segment tree on whole range of numbers (from 1 to 1000000000 in this problem), but nodes we create only when they are need.

My solution passes in 0.187s with VC++ compiler and 0.343s with G++.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The link that you gave me doesn't work ( empty page ). I am the only one ?

    You know what I got it accepted with VC++ compiler too. But, I am highly interested in your solution, please fix the problem.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      My solution using an implicit segment tree. There are at most 100000 numbers to store; a root-to-leaf path requires lg(1000000000) ~ 31 nodes in the segment tree. Pre-allocate a pool of nodes of size 100000 * 31, whenever you want to create a new node, fetch it from the pool (faster than malloc-ing at runtime). Update is similar to ordinary segment tree (I use left/right pointers).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've suffered a few days to pass this problem. Even with the right ideia, TLE was the veredict. Then I substitued an iterative approach for the recursive one. Anyway, my iterative update(remove, insert) function is here. Thanks to wil93 for the great solution.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I used the indexing notation of Segment tree (v is the parent of 2*v and 2*v+1) and iterated through the dependent nodes during update; In my solution, On a node I stored gcd due to elements in its left-subtree and gcd due to the elements in its right-subtree. [http://ideone.com/uMRGOV] The space can be reduced also. [http://ideone.com/wqH4Tz]

On a side note, I guess, any balanced Tree representation would work. (Fenwick Trees/ Segment Trees/ Online Treaps etc.,). Hope it helps :)

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I am getting WA on the Test-Case #4 .

I have stored all the factors of the number with its occurance in an UNORDERED MAP. I have used set to store the minimum element as HCF will be its factor.

Here is my code .... It would be a great help if someone could tell me whats wrong.

#include <bits/stdc++.h>
using namespace std;
#define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++)
#define rep(i,x,n) for(long i=long(x);i<long(n);i++)
long HCF(long a,long b)
{
    if(a==0) return b;
    return HCF(b%a,a);
}
int main() 
{
    ifstream cin("input.in");
    ofstream cout("output.out");
    ios::sync_with_stdio(0);cin.tie(0);
    long n,x,h=-1,l=0;
    unordered_map<long,long> m;
    set<long> s;
    char c;
    cin>>n;
    rep(j,1,n+1)
    {
        cin>>c>>x;
        if(c=='+')
        {
            l++;
            s.insert(x);
            if(h==-1)
            {
                h=x;
                cout<<x<<"\n";
            }
            else
            {
                h=HCF(h,x);
                cout<<h<<"\n";
            }
            long p=sqrt(x);
            rep(i,1,p+1)
            {
                if(x%i==0)
                {
                    m[i]++;
                    m[x/i]++;
                }
            }
            if(p*p==x)
                m[p]--;
            //for(auto i:m)
            //    cout<<i.first<<" "<<i.second<<"\n";
            //cout<<"\n";
        }
        else
        {
            s.erase(x);
            l--;
            long q;
            if(!s.empty())
                q=*s.begin();
            else
            {
                cout<<1<<"\n";
                continue;
            }
            //cout<<q<<"-----\n";
            long p=sqrt(x);
            rep(i,1,p+1)
            {
                if(x%i==0)
                {
                    m[i]--;
                    m[x/i]--;
                }
            }
            if(p*p==x)
                m[p]++;
            long w=0;
            rep(i,1,sqrt(q)+1)
                if(q%i==0)
                {
                    if(m[i]==l)
                        w=max(w,i);
                    if(m[q/i]==l)
                        w=max(w,q/i);
                    //cout<<w<<"--n---n--n\n";
                }
            cout<<w<<"\n";
            //for(auto i:m)
            //    cout<<i.first<<" "<<i.second<<"\n";
            //cout<<"\n";
        }
    }
    return 0;
}