oj.uz

Submission #647680

# Submission time Handle Problem Language Result Execution time Memory
647680 2022-10-03T15:28:49 Z mircea_007 Brperm (RMI20_brperm) C++17
0 / 100
 365 ms 83384 KB 
#include "brperm.h"

#include <stdio.h>

/*

can we somehow make a hash that reorder elements of a string?

rabin karp:
  H(str) = str[0] + 26 * str[1] + 26^2 * str[2] + ... mod 1e9+7

can't change mod

can we mess with the base? modular inverse etc?
we can flip the string by using 26^-1 as a base and multiplying at the end by 26^(N-1)

can we use 26^2?

H2(str) = H(str[0]0str[1]0str[2]0str[3]0....str[N/2-1]0) + 26^N * H(str[N/2]0str[N/2+1]0....str[N-1]0)

we would like a hash that does this:

goodH(str) = goodH(str[0]0str[1]0str[2]0str[3]0...str[N/2-1]0) + goodH(0str[N/2]0str[N/2+1]0....str[N-1])


H(abcd) = (a * 1 + c * 26^2) + 26 * (b + 26^2 * d)

we can use H(ac) and H(bd) but with different bases


*/

#define magic_sauce inline __attribute__((always_inline))

using ll = long long;

const int MAXN = 5e5;
const int MAXL = 20;
const int MOD = 1e9 + 9;
const int BASE = 26;

ll pb[1 + MAXN]; // automatic conversion

int normal_hash[MAXL][MAXN];
int perm_hash[MAXL][MAXN];

void init( int n, const char s[] ){
  int i, l, k, p2;

  pb[0] = 1;
  for( i = 1 ; i <= n ; i++ )
    pb[i] = (BASE * pb[i - 1]) % MOD;
  
  for( i = 0 ; i < n ; i++ )
    normal_hash[0][i] = perm_hash[0][i] = s[i] - 'a';

  for( l = 1 ; (p2 = (1 << l)) <= n ; l++ ){
    // calculate normal hash
    for( i = 0 ; i + p2 <= n ; i++ )
      normal_hash[l][i] = (normal_hash[l - 1][i] + pb[1 << (l - 1)] * normal_hash[l - 1][i + (1 << (l - 1))]) % MOD;
    
    for( i = 0 ; i < n ; i++ )
      perm_hash[l][i] = s[i] - 'a';
      
    for( k = 1 ; k <= l ; k++ )
      for( i = 0 ; i + (1 << k) <= n ; i++ )//      vv last iteration multiplies by 26 and the coefficient squares each time we go up
        perm_hash[l][i] = (perm_hash[l][i] + pb[1 << (l - k)] * perm_hash[l][i + (1 << (k - 1))]) % MOD;
  }

  /*for( l = 0 ; (1 << l) <= n ; l++ ){
    for( i = 0 ; i + (1 << l) <= n ; i++ )
      printf( "%d ", normal_hash[l][i] );
    printf( "\n" );
  }
  for( l = 0 ; (1 << l) <= n ; l++ ){
    for( i = 0 ; i + (1 << l) <= n ; i++ )
      printf( "%d ", perm_hash[l][i] );
    printf( "\n" );
    }*/
}

int query( int i, int k ){
  return normal_hash[k][i] == perm_hash[k][i];
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 365 ms 83384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -