I've implemented a solution for the last contest's problem D which works correct but dramatically slow! It works more than ten minutes on my PC which seems to be quite slower than naive approach. I divide the data into blocks, and store cnt[] array in every block and a deque for maintaining update queries. I cut blocks sometimes, so I rebuild structure when the number of blocks is above 2 * initialNumberOfBlocks. Probably the problem is that I'm a Java noob, who knows :D
If you have a couple of minutes, please have a look at my code. I tried to make it readable... hope it is :)
Thanks!
UPD
After I fixed the but mentalist found, the program got ML. It's also quite strange because I didn't rely on garbage collector and create no more than 400 Blocks. Each Block has int cnt[100000] inside, so total memory usage should not be more than something about 40 mb, but it exceeds 256 mb on practice. Code
I think the mistake is in the
answerprocedure. The checkif(k > NUMBER_OF_BLOCKS*2)does not use the globalk(as i think you intended), but the local parameter.Thanks a lot! It was a mistake that made my program work dramatically slow. Now it's simply slow :) Need to do some constant optimizations.
May be deque very slow. Try use arrays instead of deques.
This is author's solution.
зачем rebuild?
Потому что есть cut().
то есть блоки непостоянной длины и приходится регулировать их длину? просто я никогда не кодил декомпозицию и по туториалу тоже не понял для чего rebuild
Мне удобно когда начало запроса — это начало какого-то блока. Точно так же с концом. Пишем процедуру, которая режет по какому-то индексу. Когда мы режим блок, то он превращается в два блока. Таким образом количество блоков растет на О(1) после каждого запроса. Поэтому, когда их стало, скажем, два корня из Н, давайте заново все перестроим.
I think you can probably blame your MLE on Java's overhead and its garbage collector being flaky at times. As for the slowness, your NUMBER_OF_BLOCKS variable is 100, and you might want to change it to something closer to
. As it stands, a query on the whole array will affect 1000 blocks, leading to at least 100 million operations, and pretty expensive operations at that -- not a good thing in a language that's already pretty slow.
I get MLE even when set it to 200... And I don't believe that something may lead to over 8-times memory overhead.
Yeah, changing that number won't help with the MLE, but it might speed it up a bit, since you mentioned it was too slow as well.
I just want to say that I can't make it closer to
.
The only explanation is that Java sucks for programming contests and one should use C++. Java is good for enterprise development though.
The fact that Petr uses Java proves that you are wrong
Egor too.
That's stupid argument. The fact that Sebastian Vettel can drive Formula 1 car very well doesn't prove that you will be able to do that as well and you can drive it in the city. Every tool has its own application and my point of view is that C++ is more suitable for programming competitions because it's faster on the short run, consumes less memory and needs less attention when time/memory limits are strict. One still can use Java/Formula 1 car to solve contest problems/drive in city limits but one needs more experience and carefulness to do that.