Discussion @ 1896. War Games 2.1 @ Timus Online Judge

lxn range tree [11] // Problem 1896. War Games 2.1 9 Jun 2016 16:15

Is there a solution without randge tree structure?

Shen Yang Re: range tree [10] // Problem 1896. War Games 2.1 23 Aug 2016 17:26

I use Fenwick Tree get AC,0.452 seconds

xurshid_n Re: range tree [3] // Problem 1896. War Games 2.1 17 Jan 2017 16:33

There possible segment tree with uint16_t for indexes greater than 2^15, and uin32_t for less 2^15. (two arrays: uint16_t tree[N+N]; and uint32_t rem[32768] )
But I got WA38 ((

xurshid_n Re: range tree // Problem 1896. War Games 2.1 17 Jan 2017 20:57

I Got AC with segment tree!! uraaaaa.

Felix_Mate Re: range tree [1] // Problem 1896. War Games 2.1 27 Feb 2018 21:41

You can use segment tree where vertex is segment with length=4.

1 2 3 4 5 6 7 8 9 10 => [1,2,3,4] [5,6,7,8] [9,10,11,12]

Memory is N*sizeof(int)+N*sizeof(bool)
Complexity is N*log(N/4)*4+N*log(N/4)

🙂 Nayami_[PermSU] Re: range tree // Problem 1896. War Games 2.1 22 Nov 2021 01:13

decomposition also works here, i've chosen amount of block about 300

Mahilewets Re: range tree [5] // Problem 1896. War Games 2.1 9 Jul 2017 21:42

I can't do that. C/C++.
I am using two cycles.
One to set up Fenwick tree and one to calculate the answer.
Probably you are avoiding the use of the set up cycle somewhat.
I tested my solution on war games 2 and have got 93 ms.

UPD: got 46 ms on version 1

Edited by author 09.07.2017 22:20

Mahilewets Re: range tree [4] // Problem 1896. War Games 2.1 9 Jul 2017 22:39

Finally, I understood how to get rid of initialization cycle. Still TLE the same test 37.

Mahilewets Re: range tree [3] // Problem 1896. War Games 2.1 9 Jul 2017 22:47

http://ideone.com/cUMY7U
I have no idea what can be optimized.

Mahilewets Re: range tree [2] // Problem 1896. War Games 2.1 9 Jul 2017 22:57

Maybe bitwise operations are faster with UNSIGNED integers...

Mahilewets Re: range tree [1] // Problem 1896. War Games 2.1 10 Jul 2017 13:24

So, I tried to not calculate cnt=n-i+1 every iteration, made while (1) cycle, not call decrement on Fenwick tree after last soldier.
TLE#37.

Mahilewets Re: range tree // Problem 1896. War Games 2.1 6 Aug 2017 15:09

My mistake was

I was using queries for O(log(N) *log(N)) time in Fenwick tree

But for that task, there are suitable queries in just O(log(N))

Discussion of Problem 1896. War Games 2.1