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

×

SPOJ ANDROUND TLE

http://www.spoj.com/problems/ANDROUND/

https://ideone.com/mq6vOl

getting TLE even after using FAST I/O. Can anyone help??

asked 19 Dec '14, 19:41

abeyaar's gravatar image

1★abeyaar
33422140
accept rate: 30%


what is the need of segment trees in this question? Can you elaborate? I think this problem can be solved through pure logic. What you need to do is store the states of all the bits of all the elements in the array seperately and handle only the the 'k' positions adjacent to the bits which are 0...

link

answered 19 Dec '14, 19:59

gvaibhav21's gravatar image

7★gvaibhav21
947210
accept rate: 25%

well the logic for using segment tree was that after K rounds the ith number in the array will be influenced by (i-K)th till (i+K)th number,i.e., basically a continuous range of numbers. Hence the usage of segment tree. Well the time complexity of my solution is and O(n) for building/test case and O(nlog(n)) for querying/test case,and in terms of number of iterations the maximum number is 3800000 per test case and 1910^7 for 50 test cases..which i think should pass in 3 seconds..considering 10^8 operations are performed per second.

(19 Dec '14, 21:17) abeyaar1★

hey

i also tried this problem just now, implemented with segment tree , and yeah same result it is. TLE then i read this after many trails.. some forum on topcoder

read this, it will help

I was searching for the reason but alas, i still dont know why tle came, may be cause of pyramid cluster :/

link

answered 19 Dec '14, 23:48

dracowane's gravatar image

6★dracowane
59316
accept rate: 48%

that's what i suggested!! no need for segment trees, u just need to store the state of bits in separate arrays...

(20 Dec '14, 01:53) gvaibhav217★
1

but segment tree should pass.. O(logn) per query is equivalent to no. of bits in max(all array elements). dont know why TLE :/

(20 Dec '14, 11:51) dracowane6★

Try using the fact that if 2*K >= N then the answer to each index will be and of all elements in the initial array. else we use simple range query using either a BIT or segment tree. Below is my code for reference.

https://github.com/imegor/spoj/blob/master/ANDROUND.cpp

link

answered 02 Oct '18, 22:55

egor6174's gravatar image

2★egor6174
11
accept rate: 0%

edited 02 Oct '18, 22:57

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,768
×1,138
×184

question asked: 19 Dec '14, 19:41

question was seen: 4,919 times

last updated: 02 Oct '18, 22:57