12003 - Array Transformer

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

12003 - Array Transformer

Post by sith » Sat Nov 17, 2012 7:27 am

Hi
I solved this problem with O(n). but got TLE

Is there any faster algorithm. Do we need some faster structure, some thing like tree or Cartesian tree? Am I w

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12003 - Array Transformer -TLE

Post by brianfry713 » Tue Nov 20, 2012 3:35 am

It takes O(n+m) just to read the input so your program can't run correctly as fast as O(n).

Try splitting the array into sqrt(n) blocks.
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 12003 - Array Transformer

Post by Repon kumar Roy » Fri Mar 13, 2015 6:29 pm

get AC :)
wrong in binary search
1.Use sqrt-decomposition
2.Sort the every box/bucket

testcase :

Code: Select all

9 10 42
30 35 41 18 17 13 1 41 21 
3 9 28 8
6 8 15 8
1 4 31 1
1 6 35 5
6 7 30 9
1 3 31 3
5 7 8 9
4 8 40 3
3 4 3 7
4 8 23 3
Output :

Code: Select all

21
35 
25 
18 
28 
13 
0 
28 
14

Post Reply

Return to “Volume 120 (12000-12099)”