Блог пользователя lovro-sinda

OR — task

Автор lovro-sinda, 10 лет назад, По-английски

The given is N non-negative numbers, select exactly K who provide minimal result of OR operation (binary OR operation).

Input The first line contains an integer N (1 ≤ K ≤ N ≤ 50). The next line contains N integers not exceeding 1000 000 000

Output

Print result of OR operation selected K numbers.

Examples:

entrance

2 2
1 3

output

3

entrance

6 3
5 2 4 1 7 5

output

5

Any ideas how to solve it?

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where I can submit it?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is the task form Croatian contest, but if you want to submit you can use this link https://zatemas.zrs.hr/?app=evaluator&evlshw=solver&cd=Bo%C5%BEo%2F2013%2FDrugi+ogled%2F&evlsolve=Ili That link provide you on task at the evaluator. And you must be register to submit solution.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you submit this code?

      #define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

long long ans = 1e18, Min, sum = 1e18, mas[60];
bool used[60];

int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++)
		scanf("%d", &mas[i]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			used[j] = 0;
		used[i] = 1;
		ans = mas[i];
		for (int j = 0; j < K; j++) {
			Min = -1;
			for (int k = 0; k < N; k++) {
				if (!used[k] && Min == -1)
					Min = k;
				else if (!used[k] && (mas[i] | mas[k]) < (mas[i] | mas[Min]))
					Min = k;
			}
			ans |= mas[Min];
			used[Min] = 1;
		}
		if (ans < sum)
			sum = ans;
	}
	printf("%I64d\n", sum);
	return 0;
}
      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится
        1. 16 0.00 OK! Good solution.
        2. 0 0.00 Your program printed "383", but it should be "100".
        3. 0 0.00 Your program printed "10111", but it should be "10000".
        4. 0 0.00 Your program printed "1015805", but it should be "785407".
        5. 0 0.00 Your program printed "1245079", but it should be "1234567".
        6. 0 0.00 Your program printed "13612917", but it should be "12878913".
        7. 0 0.00 Your program printed "62781311", but it should be "12345678".
        8. 0 0.00 Your program printed "1004535807", but it should be "999111222".
        9. 0 0.00 Your program printed "123723101", but it should be "123456789".
        10. 0 0.00 Your program printed "939524095", but it should be "536870911".

        16/160 points

        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

backtracking should be enough if you prune the search when possible.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Could you please submit my solution

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    1. 16 0.00 OK! Good solution.
    2. 16 0.00 OK! Good solution.
    3. 16 0.00 OK! Good solution.
    4. 16 0.00 OK! Good solution.
    5. 16 0.00 OK! Good solution.
    6. 16 0.00 OK! Good solution.
    7. 16 0.00 OK! Good solution.
    8. 0 0.00 Your program printed "1004535807", but it should be "999111222".
    9. 16 0.00 OK! Good solution.
    10. 16 0.00 OK! Good solution.
    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

You can do this using a greedy algorithm. Let 2^x be the highest power of two smaller than or equal to the biggest of the integers in the input.

  • If there are less than k numbers with bit x not set (easy case): you will be forced to pick at least one number with bit x set, so answer will have bit x set no matter what you do.

  • If there are k or more numbers with bit x not set: it's always better to ignore all numbers in the input that have bit x set, because by not picking it you always get a smaller answer.

I submitted this solution and it was accepted, but I'll leave the implementation to you.

→ Ответить