Bekh's blog

By Bekh, history, 5 years ago, In English

Hello,

I was trying to solve 1117D - Magic Gems using Matrix Exponentiation. I'm trying to use an implementation (It was moriss821028's if I recall correctly) for Matrix Power since it's much faster than mine. I'm using 2 transformation matrices and multiply them to get the final transformation matrix named transform and then raise it to the power of n.

This submission: 58207232 gets AC, while on my machine it gives segmentation fault on line: 108, the line where I raise the transform matrix to the power of n. Following it with the debugger, it doesn't enter the operator ^ function at all, it stops on the definition line and halts.

Reducing the dimensions of the array v to 180 x 180 seems to fix the issue locally but the code doesn't seem to take that much memory. Idk if this is related to a memory leak or what.

My IDE is CLion, the compiler is MinGW version 5.0, my CMake version is 3.13.2, and I'm using C++ 14.
It prints exit message Process finished with exit code -1073741571 (0xC00000FD).
If there is any more information you need, please ask. I'm a kind of a newbie when it comes to these stuff.

Any help would be appreciated

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This is a stack size problem, increasing the stack size or declaring the matrices globally or dynamically in the heap fixes the issue.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thank you. I totally forgot that it's creating static arrays in the stack. Declaring them globally fixed the issue.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I had the same issue for a while. While creating global arrays is a workaround, you can solve the underlying issue by opening your CMakeLists.txt file in CLion and adding the following line to the end:

set (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wl,--stack=268435456")

This sets your stack size to the same 256MB limit enforced by most Codeforces problems.