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

×

how can these solutions pass time limit and codechef do u really check how much plagarism is there in long challenge ..

asked 12 Mar, 17:39

square_root_pi's gravatar image

0★square_root_pi
756
accept rate: 0%


time complexity is actually $O(N\log{MAX})$, where MAX is maximum number in the array. Refer to this explanation TIME COMPLEXITY EXPLANATION.

Upvote it if you find it helpful I need karma points to contribute to the community (I don't have any now)

link

answered 13 Mar, 13:24

pshishod2645's gravatar image

5★pshishod2645
47410
accept rate: 16%

edited 13 Mar, 13:26

The complexity may seem O(n^2) but is actually around O(nlogn) since whatever input you try, the maximum number of total votes would be around nlogn. Try to come up with a test case that would give TLE on these codes and you'll realize why it's true.

The reason why you're getting runtime error on ideone is because you're printing 10^5 integers which is more than the allowed output size on ideone. Try it on an offline compiler or just comment out the final print statements and it would work.

link

answered 13 Mar, 01:17

abdullah768's gravatar image

6★abdullah768
1.9k217
accept rate: 17%

if u remove the if statement

there are 2 simple for loops with with each one running and the difference bw i and j is just two everytime

why isn't this loop is simple

for(ll i=0;i<n;++i){

    for(ll j=i+2;j<n;++j){

        cout<<"hello ";

    }

    cout<<endl;
}
(13 Mar, 01:45) square_root_pi0★

Whats your point all the solution that u have linked above seems right and the time limit is generally 1 sec you assume u can do 10^8 operation per sec so 10^6 is fine. And about the plagiarism issue all the solutions are checked for plagiarism after contest.

link

answered 12 Mar, 17:50

phantomhive's gravatar image

3★phantomhive
844
accept rate: 0%

n can be as large as 100000 in the loop

  for( i=0; i<(n); i++)
  {
        if(i+1 < n)
        {
            c[i]+=1;
            c[i+1]+=1;
        }

        for( j=i+2; j<n; j++)
        ......

} how u see that it will pass time limit

here is a possible case

take n = 10^5 fill each element by 259

https://ideone.com/Vg7Sdd

@vijju123

(12 Mar, 18:10) square_root_pi0★
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:

×668
×208
×3

question asked: 12 Mar, 17:39

question was seen: 610 times

last updated: 13 Mar, 13:26