Soluție HackerRank pentru XOR Subsequences. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: XOR Subsequences

Cerinta completa

Consider an array, [Expresie matematică indisponibilă în copia arhivată], of [Expresie matematică indisponibilă în copia arhivată] integers ([Expresie matematică indisponibilă în copia arhivată]).
We take all consecutive subsequences of integers from the array that satisfy the following:

[Expresie matematică indisponibilă în copia arhivată]

For example, if [Expresie matematică indisponibilă în copia arhivată] our subsequences will be:

  1. [Expresie matematică indisponibilă în copia arhivată]
  2. [Expresie matematică indisponibilă în copia arhivată]
  3. [Expresie matematică indisponibilă în copia arhivată]
  4. [Expresie matematică indisponibilă în copia arhivată]
  5. [Expresie matematică indisponibilă în copia arhivată]
  6. [Expresie matematică indisponibilă în copia arhivată]

For each subsequence, we apply the bitwise XOR ([Expresie matematică indisponibilă în copia arhivată]) operation on all the integers and record the resultant value. Since there are [Expresie matematică indisponibilă în copia arhivată] subsequences, this will result in [Expresie matematică indisponibilă în copia arhivată] numbers.

Given array [Expresie matematică indisponibilă în copia arhivată], find the XOR sum of every subsequence of [Expresie matematică indisponibilă în copia arhivată] and determine the frequency at which each number occurs. Then print the number and its respective frequency as two space-separated values on a single line.

Input Format

The first line contains an integer, [Expresie matematică indisponibilă în copia arhivată], denoting the size of the array.
Each line [Expresie matematică indisponibilă în copia arhivată] of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines contains a single integer describing element [Expresie matematică indisponibilă în copia arhivată].

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

Print [Expresie matematică indisponibilă în copia arhivată] space-separated integers on a single line. The first integer should be the number having the highest frequency, and the second integer should be the number’s frequency (i.e., the number of times it appeared). If there are multiple numbers having maximal frequency, choose the smallest one.

Sample Input 0

4
2
1
1
3

Sample Output 0

1 3

Explanation 0

Let’s find the XOR sum for all consecutive subsequences. We’ll refer to the frequency of some number [Expresie matematică indisponibilă în copia arhivată] as [Expresie matematică indisponibilă în copia arhivată], and keep a running sum for each frequency:

  1. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată]
  2. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]
  3. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]
  4. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  5. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  6. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  7. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  8. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  9. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]
  10. [Expresie matematică indisponibilă în copia arhivată], frequencies: [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]

Our maximal frequency is [Expresie matematică indisponibilă în copia arhivată], and the integers [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] all have this frequency. Because more than one integer has this frequency, we choose the smallest one, which is [Expresie matematică indisponibilă în copia arhivată]. We then print the respective smallest number having the maximal frequency and the maximal frequency as a single line of space-separated values.

Limbajul de programare folosit: cpp14

Cod:

// Fast Walsh transform to accelerate XOR convolution
#include <cstdio>
using namespace std;

typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

int ri()
{
  int x;
  scanf("%d", &x);
  return x;
}

const int LOGM = 16, M = 1 << LOGM;
ll c[M];

void walsh_dit2()
{
  for (int m = 2; m <= M; m *= 2) {
    int mh = m/2;
    for (int i = 0; i < M; i += m)
      REP(j, mh) {
        ll x = c[i+j], y = c[i+j+mh];
        c[i+j] = x+y;
        c[i+j+mh] = x-y;
      }
  }
}

void arith()
{
  for (int m = 2; m <= M; m *= 2) {
    int mh = m/2;
    for (int i = 0; i < M; i += m)
      REP(j, mh) {
        ll x = c[i+j], y = c[i+j+mh];
        c[i+j] = x;
        c[i+j+mh] = x+y;
      }
  }
}

void arith_minus()
{
  for (int m = 2; m <= M; m *= 2) {
    int mh = m/2;
    for (int i = 0; i < M; i += m)
      REP(j, mh) {
        ll x = c[i+j], y = c[i+j+mh];
        c[i+j] = x;
        c[i+j+mh] = y-x;
      }
  }
}

void xorConvolution()
{
  walsh_dit2();
  REP(i, M)
    c[i] *= c[i];
  walsh_dit2();
  REP(i, M)
    c[i] /= M;
}

void orConvolution()
{
  arith();
  REP(i, M)
    c[i] *= c[i];
  arith_minus();
}

int main()
{
  int n = ri(), acc = 0;
  c[0]++;
  REP(i, n) {
    acc ^= ri();
    c[acc]++;
  }
  xorConvolution();
  int x;
  ll y = 0;
  FOR(i, 1, M)
    if (c[i] > y)
      y = c[x = i];
  printf("%d %lld\n", x, y/2);
}

Scor obtinut: 1.0

Submission ID: 464656310

Link challenge: https://www.hackerrank.com/challenges/xor-subsequence/problem

XOR Subsequences