Mostafa_Alaa99's blog

About Problem B (Startup), Dictionary in Python Hack
By Mostafa_Alaa99, history, 12 days ago, In English

UPD2: It is my first time to make a post here, can I know why many people are making downvotes (nearly those didn't write a comment), I think if they told me the reason for that maybe this will be helpful for both of us

Again, someone hacked my B solution coz of the Python Dictionary (this can happen also when using CPP unordered_map)

But I noticed that it can be done using an array because the constraint bi <= k which will allow to avoid Py dict

So, I wonder did the problem setter put this constraint for Python users to be able to solve it also in Python as they can avoid dictionary because of it, or the constraint exists for any other reason?

UPD1: Now, I have used d[str(key)] = value and it works and got ACC not TLE like the previous

Submission: 289783097

brands = defaultdict(int)
for _ in range(k):
    bi, ci = read_numbers()
    brands[str(bi)] += ci

brands = list(brands.values())
brands.sort(reverse=True)
ans = 0
for i in range(min(n, len(brands))):
    ans += brands[i]

print(ans)

the only change is the str(bi) instead of bi, can anyone try to hack it or show me something that will let this not work

coz I really wants to use Python all time (recursion problem has no idea how to solve it yet, but I am speaking now about this problem)

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

this restriction really helps python users avoid using dictionaries and use arrays, it was introduced mainly in order to ensure the optimality and simplicity of solving the problem in any programming languages

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

    Exactly, I really liked it, but I was very stressed in the contest and wanna solve most of it, so I didn't resubmit and said I hope no one will do this hack

    → Reply
    • »
      »
      »
      12 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No issues don't worry, next time just watch for the constraints first. They are set in a way so that every user could do it.

      → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was surprised to see this, where unordered_map performs as well as python's dict(). Again defaultdict performs better than dict(). I got TLE on B too I was using that.

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use dicts like this: d[str(key)] = val, string hash func is much more stable

→ Reply
»
12 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Learnt this the hard way from a previous contest, but use a custom hash to avoid getting hacked while using unordered_map in c++

Leaving the code Snippet below, will link the original blog below if and when I find it

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

Use unordered_map<int, int, custom_hash> or map<int,int, custom_hash>

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

    Original Blog: Here

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

    I was thinking too about creating my own hash function, but I was afraid of some genius one searching and deeply know about the function I used and then also hack me

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply