You are not logged in. Please login at www.codechef.com to post your questions!

×

Solution for Chewing Problem of ZCO 2013

Problem link - https://www.codechef.com/ZCOPRAC/problems/ZCO13003

Code submission and test result - https://www.codechef.com/viewsolution/12135910

I have written my solution to this problem in JAVA and I am getting a TLE error in the second sub-task. I know my code is not the most efficient nor the most optimised way to do so. I have tried understanding the concept by looking at other people's code but couldn't decipher it. Can someone explain to me how it is done. I am new in competitive coding and not very well versed with binary search.

Code in Java -

//written by Lord_of_Codes
import java.util.*;
class ZCO13003
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int a[]=new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
        }
        long sum =0;
        for(int i=0; i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                long d=a[i]+a[j];
                if(d<k)
                {
                    sum++;
                }
            }
        }
        System.out.println(sum);
    }
}

asked 29 Nov '16, 00:56

lord_of_codes's gravatar image

1★lord_of_codes
355
accept rate: 0%


What you have done is called a brute force approach -
To solve this problem you need to know binary search which you said are not well versed with.
I recommend you to watch some videos of it on youtube and also I am providing some links -
https://www.commonlounge.com/discussion/601e95ee310545a78a429b676def547f/main
https://www.commonlounge.com/discussion/9efbe64b3fb04690abc1622b461185fd/main
http://www.iarcs.org.in/inoi/online-study-material/topics/binarysearch.php

Btw, I recommend you to join this community of IOI at commonlounge. It's pretty helpful.

And here's the solution - https://www.commonlounge.com/discussion/2afcb31fbcaa4c71b8d6bed6e6a5b77e/main

And here's my code - https://www.codechef.com/viewsolution/12151274

link

answered 29 Nov '16, 02:05

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%

I tried to solve it using Fenwick Tree. for every element in the hardness array i am counting how many are less than the current element. but i am getting WA for few TC. can someone pls tell me the flaw in the logic?

    ll int n,k;
    long long int bit[1000000+7];

    long long bit_q(ll int bt[], ll int j)
    {
        long long sum=0ll; //its 0LL
        while(j>0){
            sum+=bt[j];
            j -= (j & (j*-1)); //parent finding
        }
        return sum;
    }

    void bit_up(ll int bt[], ll int n, int i,ll int  diff) // bit update
    {
        while(i<=n){
            bt[i] += diff;
            i += (i & (i*-1)); //next index in BITree
        }
    }

    int main() {
        int t=1;  //    readint(t);
        while(t--){
            cin>>n>>k;
            vector<ll int> q;
            for(int i=0;i<n;i++){
                ll int a;
                cin>>a;
                if(a<k)  q.push_back(a);
            }
            sort(q.begin(),q.end());
            n=q.size();
            ll int c = 0;
            for(ll int i=0; i<n; i++){
                c+= bit_q(bit, k-(q[i])  );
                bit_up(bit, n, q[i]+1 ,1);
            }
            cout<<c;
        }
        return 0;
     }
link

answered 02 Feb '17, 13:07

aminuteman's gravatar image

1★aminuteman
1745
accept rate: 13%

edited 02 Feb '17, 13:08

(02 Feb '17, 13:16) aminuteman1★

consider the case 0 1 4 9 10 15 3 1 0 and K =3, i think the program will not give output when quering -ve ie (k-q[i]), as BIT cannot have -ve index.

(02 Sep '18, 19:56) jvjplus2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,314
×427
×399
×247

question asked: 29 Nov '16, 00:56

question was seen: 1,147 times

last updated: 02 Feb '17, 13:16