lovro-sinda's blog

OR — task

By lovro-sinda, 11 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where I can submit it?

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

    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.

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

      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;
}
      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it
        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

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could you please submit my solution

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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.
    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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.

→ Reply