YAXS - Yet Another Xor Sequence


Fizz have an array A of n integers which ranges between [1, 5] inclusive. Let f(i) denote number of times i occurs in the array.

Fizz wants to maximize the value of max(f(1), f(2), f(3), f(4), f(5)). To achieve it, he can perform one operation in the array as many time as he likes.

In each step Fizz can choose two integers Ai and Aj such that:

  • i != j
  • 1 <= (Ai ⊕ Aj) <= 5, where ⊕ is the symbol for bitwise xor.

After choosing the integers, Fizz will remove them from the array and he will insert a new element (Ai ⊕ Aj).

Fizz is very good in cricket but not so in programming, so please help him to find the maximum possible value of max(f(1), f(2), f(3), f(4), f(5)).

Input Format

First line will contain an integer T(1 <= T <= 3000) denoting number of testcases. Each test case will contain two lines. First line will consist n (1 <= n <= 1000) and second line will consist n space separated integers between 1 to 5.

Output Format:

For each case, print the case number and the expected answer.

Sample

8
2 3 4 2 3 5 1 2

Output
Case 1: 5

hide comments
zbillion_: 2020-05-29 21:57:03

Note:
you have to find the maximum possible frequency of all possible numbers and then find maximum of them. NOT maximum possible frequency of the current element/s with the highest frequency.
so find all numbers maximum frequency

Last edit: 2020-05-30 19:22:40
vivek_dwivedi: 2018-06-18 03:46:36

easiest problem i solved on spoj ! Just kidding. ;)

Shafaet: 2016-10-27 20:49:41

I have fixed the sample. the dataset is correct.

:D: 2016-10-25 13:24:31

I'm pretty sure alfa_razra is correct here. I've wrote a basic brute force that verifies this:
http://ideone.com/bjxXFM

Shafaet please hide the problem and check your solution.

alfa_razra1505: 2016-10-24 15:41:13

why the sample test case give answer 4 ? i can make it have answer 5 :
4 xor 5 = push 1 to the array.
now, you have f(1) = 2 and f(3) = 2,
1 xor 3 = push 2. you can do this twice. so, you push 2 twice.
and now, f(1) = 0, f(2) = 5, f(3) = 0, f(4) = 0, f(5) = 0. so the answer is 5. am i wrong ?


Added by:Shafaet
Date:2016-10-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own problem, Bangladesh National Collegiate Contest Preliminery Round