div24ever's blog

By div24ever, 18 months ago, In English,

Given 3 types of queries

  1. Insert element 'x' into multiset
  2. Delete element 'x' from multiset
  3. Find xor of all elements present in multiset which are less than 'k' (k is not fixed)

I required above solution in this problem. But I was unable to solve it this way. How to solve this?

Read more »

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

By div24ever, history, 19 months ago, In English,

I am trying to solve Spy Syndrome 2 for a long long time. This is my submission. I am unable to figure out why my code prints weird characters.

Read more »

 
 
 
 

By div24ever, history, 3 years ago, In English,

Hi everyone!

I have made a simple program which will give best order of solving problems during codeforces contest according to the user's speed. It will tell you whether it is better to solve problem in order C -> B -> A or B -> A -> C ( with many other permutations ) according to user's speed.

GitHub link

Read more »

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

By div24ever, history, 3 years ago, In English,

Time according to UTC +5.5

Codeforces Educational Round 9 --> Mar/01/2016 20:30 to Mar/01/2016 22:30

HackerEarth March Easy '16 --------> 01 Mar 2016, 21:30 to 02 Mar 2016, 00:30

HackerRank HourRank 6 ------------> Mar 1 2016, 22:00 to Mar 1 2016, 23:00

HourRank is unrated this time, maybe because of this clash. From past 2-3 months, I wanted to participate in HackerEarth Monthly Easy contests but i couldn't because there was always a clash.

Such type of clashes are complete turn off for many participants. So please try avoid such clashes in future and try to change the timing of contests(if possible) happening on 1st March 2016.

EDIT 1 — Both HourRank and March Easy are rated. This is for the first time HackerEarth contest will be rated!

Read more »

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

By div24ever, history, 3 years ago, In English,

I solved TopBiologist by recursion. I want to know if there is any iterative approach? We will need to run loop 6 times to generate sequence of length 6. Is there any shorter way to do this?

My code

Read more »

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

By div24ever, history, 3 years ago, In English,

Problem statement

I am unable understand the first testcase of this problem.

10 2 3

When L = 1, 5 and 7 then both will into abyss.

When L = 6 both will complete race at the same time.

So we should consider four cases when there will be tie. Why are we taking only 1, 6 and 7?

Read more »

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

By div24ever, history, 3 years ago, In English,

I am trying to solve this using dynamic programming with complexity of O ( N ^ 2 ) which will give TLE because N <= 10 ^ 5.

Problem Link

Read more »

 
 
 
 

By div24ever, history, 3 years ago, In English,

I am trying to solve Niceness of the string but i am getting WA because i think i am unable to process blank lines. For blank lines output will be zero. I am using scanf(" %[^\n]s",a) which will ignore blank lines.

My code

Read more »

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

By div24ever, history, 3 years ago, In English,

Problem link

I have done this problem with time complexity O( nlogn + n * m ) and space complexity O( 2 * m ). How can i improve this?

Read more »

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

By div24ever, history, 3 years ago, In English,

Problem link

Why is the answer 2 ^ ( n — 1 ) ?

Read more »

 
 
 
 

By div24ever, history, 3 years ago, In English,

I have encountered weird behaviour with character arrays/strings on various websites. For example take these two submissions — First submission Second submission. I have just removed fflush(stdin) from my first submission and got AC. I faced similar issue with this problem. This submission has scanf without fflush(stdin) and it got runtime error but according to previous logic it should have got AC. Now this submission with fflush(stdin) and scanf also got runtime error. But this submission with cin got AC.

So my question is what should i do to prevent such nasty errors during contest? cin is slower than scanf so i prefer scanf.

EDIT — For first problem, i saw that i have used different versions of C++. In C++ 11 it gave WA but in C++ it gave AC.

Read more »

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

By div24ever, history, 3 years ago, In English,

Many people might want to participate in both contests so please look into this issue. 101 Hack Nov and Codeforces Round #332 (Div. 2)

EDIT — Codeforces has shifted the Round #322 to 20th November. Thank you Codeforces. :)

Read more »

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

By div24ever, history, 3 years ago, In English,

How to take fast I/O in C++? I am solving a problem where number of test cases can be 10^6 so i guess fast I/O will help to speed up my solution.

Read more »

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

By div24ever, history, 3 years ago, In English,

I want to know how can i compare two different outputs so that i can check whether an algorithm works fine for corner cases also. I want to compare output generated by naive algorithm and an another algorithm saved in two .txt files. I use Code Blocks.

Read more »

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

By div24ever, history, 3 years ago, In English,

I tried to solve FACTMUL and got AC with 4.82 time. There are many submissions with less than 1.0 time. How to do it in less than 1.0 time?

My code

#include<bits/stdc++.h>
unsigned long long mod=109546051211,fact[587117]={0,1,2,6},a[587117]={0,1,2,12},i,j;
unsigned long long mulmod(unsigned long long a,unsigned long long b)
{
    if((a==0)||(b<mod/a)) return (a*b)%mod;
    unsigned long long x=0,y=a%mod;
    while(b>0)
    {
        if(b%2==1) x=(x+y)%mod;
        y=(y*2)%mod;
        b/=2;
    }
    return x%mod;
}
int main()
{
    for(j=2;j<587117;j++)  //Computes and stores factorial
    {                      //of all number till 587116
        if(fact[j]) continue;
        fact[j]=mulmod(j,fact[j-1]);
    }
    unsigned long long n;
    scanf("%llu",&n);
    if(n>=587117) printf("0\n");
    else
    {
        if(a[n]!=0) printf("%llu\n",a[n]); //It will make no difference
        else                               //because test case is 1
        {
            for(i=2;i<=n;i++) a[i]=mulmod(fact[i],a[i-1]);
            printf("%llu\n",a[n]);
        }
    }
    return 0;
}

Read more »

 
 
 
 

By div24ever, 3 years ago, In English,
Let a = ( 2 ^ 9 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 11 ^ 1 )
and b = ( 2 ^ 2 ) * ( 3 ^ 4 ) * ( 7 ^ 1 ) * ( 13 ^ 2 )

then our answer will be ( 2 ^ 9 ) * ( 11 ^ 1 )

I can easily which factors will be present in the answer by calculating a / gcd(a,b) but i am having difficulty in finding the power of those factors. Is it possible to solve the problem using gcd and lcm? Or we will have to factorize both a and b then find the answer?

EDIT — Or is it possible to just find the factors having the exact same power? For above example it is ( 7 ^ 1 ).

For a = ( 2 ^ 3 ) * ( 3 ^ 2 ) * ( 5 ^ 3 ) * ( 7 ^ 1 )
and b = ( 2 ^ 4 ) * ( 3 ^ 2 ) * ( 7 ^ 1 ) * ( 17 ^ 2 )
it is ( 3 ^ 2 ) * ( 7 ^ 1 )

Read more »

 
 
 
 

By div24ever, history, 3 years ago, In English,

Hi i am trying to solve above problem and getting WA. Help.

#include<stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char a[1000];
        int i,b=0,c=0,d=0;
        fflush(stdin);
        gets(a);
        fflush(stdin);
        gets(a);
        for(i=0;a[i]!=' ';i++)
        {
            if(a[i]=='m')
            {
                b=-1;
                break;
            }
            b=b*10+(a[i]-'0');
        }
        for(;a[i]!=' ';i++);
        i+=3;
        for(;a[i]!=' ';i++)
        {
            if(a[i]=='m')
            {
                c=-1;
                break;
            }
            c=c*10+(a[i]-'0');
        }
        for(;a[i]!=' ';i++);
        i+=3;
        for(;a[i]!='\0';i++)
        {
            if(a[i]=='m')
            {
                d=-1;
                break;
            }
            d=d*10+(a[i]-'0');
        }
        if(b==-1) printf("%d + %d = %d\n",d-c,c,d);
        else if(c==-1) printf("%d + %d = %d\n",b,d-b,d);
        else printf("%d + %d = %d\n",b,c,b+c);
    }
    return 0;
}

PS — I got AC. I was getting WA because there were many blank lines in input.

Read more »