Rubanenko's blog

CFR #260 D
By Rubanenko, 10 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I think the mistake is in the answer procedure. The check if(k > NUMBER_OF_BLOCKS*2) does not use the global k (as i think you intended), but the local parameter.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be deque very slow. Try use arrays instead of deques.

This is author's solution.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I get MLE even when set it to 200... And I don't believe that something may lead to over 8-times memory overhead.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I just want to say that I can't make it closer to .

        → Reply
»
10 years ago, # |
  Vote: I like it -29 Vote: I do not like it

The only explanation is that Java sucks for programming contests and one should use C++. Java is good for enterprise development though.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    The fact that Petr uses Java proves that you are wrong

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Egor too.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it -9 Vote: I do not like it

      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.

      → Reply