Doubt in an interactive codeforces problem

so this is the problem, It is an interactive problem, grader provides ai.aj for any two index i, j where 1<=i<=j<=6 and we’re suppose to return the correct permutation of the array [ 4, 8, 15, 16, 23, 42], can ask up to 4 queries.

so my doubt is how we’ll know exact index where a value belongs, like for input array 42 23 16 15 8 4
if by grader we are given value of a[3].a[5] which is 128, how I’ll know if value at index 3 needs to be 16 or 8.

2 Likes

There are numerous ways to solve this. You could simply bruteforce the products. My approach to it was to figure out 3 numbers by asking 2 queries.

The numbers 15, 23, 42 can be easily identified. Consider the following:
Suppose a, b, c are a[1], a[2], a[3] and ab, bc are their products. The following cases arise-

  • Both ab and bc are divisible by 15: Obviously b has to be 15. Hence we can find a and c
  • Only ab is divisible by 15: a has to be 15, consequently, we can find b and c
  • Only bc is divisible by 15: c has to be 15, consequently, we can find b and a

The same argument can be applied to 23 as well as 42. Problem occurs when the 3 numbers we ask turn out to be a permutation of 4, 8, 16. For this, I simply bruteforced the possibilities.

Here’s my code: https://codeforces.com/contest/1167/submission/54193218

Hope that helps :slight_smile:

1 Like

Ask 4 queries:
a1.a2 = num1
a2.a3 = num2
a4.a5 = num3
a5.a6 = num4
Now we find the factor of num1 and num2 which is common to both. We know that only a2 is common to both num1 and num2. Hence we know what is a2.
And, a1=num1 / a2, a3=num2/a2

Similarly we find a4,a5,a6

1 Like

This is such an easy problem and I was mindlessly banging my head cuz I thought those 6-integers can be any integers,but I realized they are always, 15,32…
Simplest solution:-Try all 6! combinations and whichever satisfies the constraints,output it :slight_smile:

1 Like