Блог пользователя 2IA7A8E6A7

Автор 2IA7A8E6A7, история, 7 месяцев назад, По-английски

Recently I've had my first hacked problem: 372051449. I didn't really think much of hacking up until this point, but this problem made me rethink. I have a few questions in mind:

  1. What type of problems are most likely hackable?

  2. What are the general methods used to hack a submission?

  3. What preventive measures can be taken to protect a solution from hacks?

I'm interested in your ideas about hacking. Feel free to drop a comment!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Bruh, even I can feel your pain, you missed that CM because of the hack.

»
7 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I can think of mostly hashing problems and using hashtables (https://codeforces.me/blog/entry/62393) are easily hackable.

»
7 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +7 Проголосовать: не нравится

You could randomize your base to make it unpredictable

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() ^ (uintptr_t)(new char));
base = uniform_int_distribution<>(1e8, 1e9)(rng);
»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

That's it I'm using SHA-256

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can you explain me how a problem gets hacked ? sorry idk this :)

  • »
    »
    7 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    You basically submit a test case that makes the code fail, like, for example the code runs on O(n^2) and you use a test case with n=1e6 to make it TLE, or have a bunch of inputs to attempt MLE

  • »
    »
    7 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Usually, reading from a list is o(n) if you don't know the index because you need to search every item. However, in a hash map (which is a dict), a hash function is used on the item (modulo a number because it doesn't have to be very big) and that will be the index. This runs in o(1)

    A hash collision hack is taking advantage that if 2 items have the same hash (and thus the same index), the program will have to read the entire list to find it (which is very slow compared to hash maps). With a lot of collisions, you can get time-limit on a problem.

»
7 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

use more and larger prime mods.

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

hacks should not be allowed in such questions i feel

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Mostly hashing problems.

Add a random number to the base. Don’t use time(0) for seed, use chrono::steady_clock.

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Has anyone ever hacked a non-hashing problem? If so, can you tell me about the process of hacking it?