C,C++/JAVA/BASH/ASM ARENA

वह प्रदीप जो दीख रहा है झिलमिल दूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है चिन्गारी बन गयी लहू की बून्द गिरी जो पग से चमक रहे पीछे मुड देखो चरण-चिनह जगमग से बाकी होश तभी तक, जब तक जलता तूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है अपनी हड्डी की मशाल से हृदय चीरते तम का, सारी रात चले तुम दुख झेलते कुलिश का। एक खेय है शेष, किसी विध पार उसे कर जाओ; वह देखो, उस पार चमकता है मन्दिर प्रियतम का। आकर इतना पास फिरे, वह सच्चा शूर नहीं है; थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है। दिशा दीप्त हो उठी प्राप्त कर पुण्य-प्रकाश तुम्हारा, लिखा जा चुका अनल-अक्षरों में इतिहास तुम्हारा। जिस मिट्टी ने लहू पिया, वह फूल खिलाएगी ही, अम्बर पर घन बन छाएगा ही उच्छ्वास तुम्हारा। और अधिक ले जाँच, देवता इतन क्रूर नहीं है। थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है।

Facebook Hacker Cup 2013 Qualification round Problem 3 – Find the Min January 27, 2013

Filed under: Facebook Hacker Cup — whoami @ 13:28
Tags: ,

Find the Min

Though i got the output for the given input file, my below solution gave wrong results within 6 minutes time duration mainly because of not using “long long int” datatype for creating pseudonumbers.
It was because of the data overflow.

After changing the datatypes, got the positive answers(though it has not been tested as test results are not known).

I am just publishing my solution for my further reference( as i could not submit in the contest).

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;

long long int originals[1000009];
long long int generated_numbers[1000009];
long long int ans[1000009];

int main()
{
    //freopen("find_the_min.txt","r",stdin);
    freopen("find_the_min2.txt","r",stdin);
    //freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    int T,testcase=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);

        int a,b,c,r;
        scanf("%d%d%d%d",&a,&b,&c,&r);

        long long int m[k];

        m[0]=a;

        for(int i=1;i<k;i++)
        {
            long long int tmp1=b%r;
            long long int tmp2=m[i-1]%r;
            long long int ltmp=tmp1*tmp2;
            ltmp=ltmp%r;
            long long int tmp3=ltmp;
            long long int tmp4=c%r;
            long long int final=(tmp3+tmp4)%r;
            m[i]=final;
        }

        /*keep two sorted arrays, whose values can be used for each of
        the indexes <n
        */

        //originals
        for(int i=0;i<k;i++)
        {
            originals[i]=m[i];
        }
        sort(originals, originals+k);

        //generated
        int count=0;
        for(int i=0;i<k&&count<k;i++)
        {
            if(i==0)
            {
                if(originals[i]>0)
                {
                    for(long long int l=0;l<originals[i]&&count<k;l++)
                    {
                        generated_numbers[count++]=l;
                    }
                }
            }
            else
            {
                if(originals[i]-originals[i-1] > 1)
                {
                    int times=originals[i]-originals[i-1]-1;
                    long long int start=originals[i-1]+1;
                    for(int l=0;l<times&&count<k;l++,start++)
                    {
                        generated_numbers[count++] = start;
                    }
                }
            }

        }

        if(count < k )
        {
            long long int start=originals[k-1]+1;
            while(count < k)
            {
                generated_numbers[count++]=start;
                start++;
            }
        }

        deque<long long int>dq;
        for(int i=0;i<k;i++)
        {
            dq.push_back(m[i]);
            ans[i]=m[i];
        }
        set<long long int>st;st.clear();
        for(int i=0;i<count;i++)
        {
            st.insert(generated_numbers[i]);
        }

        int total_iterations=0;
        int total=k;
        while(total_iterations <2*k+2 )
        {
            ++total_iterations;
            long long int item=dq.front();
            dq.pop_front();

            std::set<long long int>::iterator it;
            if(st.size()>=1 )
            {
                long long int item_to_insert_in_dq = *(st.begin());
                dq.push_back(item_to_insert_in_dq);
                ans[total++] = item_to_insert_in_dq;
                st.erase (st.begin());
            }

            if(total_iterations <= k)
            {
                int flag=1;
                for(int i=total_iterations,j=0;j<k-1;i++,j++)
                {
                    if(item == ans[i])
                    {
                        flag=0;
                        break;
                    }
                }

                if(flag==1)
                {
                    st.insert(item);
                }
            }
            else
            {
                st.insert(item);
            }

            if(total_iterations == n) break;
        }
            printf("Case #%d: ",++testcase);

            if( (n-k) %(k+1) == 0)
            {
                printf("%lld\n",ans[k+k]);
            }
            else
            {
                printf("%lld\n",ans[k+((n-k)%(k+1))-1]);
            }

    }

    return 0;
}

🙂

Please donot use this code to submit in the running contest. It will not help in long run…

Advertisements
 

Check your pointer skills. January 4, 2013

Filed under: Uncategorized — whoami @ 11:47
Tags: , , , ,

Good Evening !!!

Explain the following :-

1. int (*(*foo)(void ))[3]

2.char *const argv[]

3. char * const *argv

4. void (*p[10]) (void (*)() )

Things that you might know well:-

1. const char*

2. char* const

3. const char* const

4. const *char ->tricky

5. char const * -> similar as one of the above(guess which one?)

🙂