ZZZ's Site

狗蛋儿

27 July 2020

[Codeforces 1381C] Mastermind

by zzz

Problem Description

Problem Link

Given two arrays of length n, where the value belongs to [1, n + 1], there will be x exact matching (value and index), and y matching values.

The problem is given one of the two arrays, x and y, try to figure out the other array.

Sample Input

7
5 2 4
3 1 1 2 5
5 3 4
1 1 2 1 2
4 0 4
5 5 3 3
4 1 4
2 3 2 3
6 1 2
3 2 1 1 1 1
6 2 4
3 3 2 1 1 1
6 2 6
1 1 3 2 1 1

Sample Output

YES
3 1 6 1 2
YES
3 1 1 1 2
YES
3 3 5 5
NO
YES
4 4 4 4 3 1
YES
3 1 3 1 7 7
YES
2 3 1 1 1 1

Solution

Solution Link

Outline

  1. Find x exact match.
  2. Find y-x value but not index match.
  3. Fill other positions with the missing elements.

Step 1

It’s easy to figure out we need to use the most frequent element as much as possible.

Step 2

There are several good and bad ideas.

  1. Using the most frequent elements. Pop out two most frequent elements and assign to each other. This is incorrect! One counterexample is 1 2 3.
  2. Sort the elements and match with the reverse of the sorted array. This is incorrect! One counter example is 1 1 2 2 2 3 3.
  3. Using the most frequent elements, and for >2 number of same top frequenet of elements, we need to use them at the same time, by shifting them by 1.
  4. Sort the elements and shift the elements by the max number of occurance.
  5. Sort the elements and shift the elements by the half of the array length.

Looking back

The victory of acceptance makes the hard work to solve the problem totally worth it!

tags: Codeforces - Constructive - Matching - Shiftnig

Posts

subscribe via RSS