IOI '19 P1 - Arranging Shoes - DMOJ: Modern Online Judge

IOI '19 P1 - Arranging Shoes

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 1G

Problem types

Allowed languages

C++

Adnan owns the biggest shoe store in Baku. A box containing $n$ $n$ pairs of shoes has just arrived at the store. Each pair consists of two shoes of the same size: a left and a right one. Adnan has put all of the $2n$ $2 n$ shoes in a row consisting of $2n$ $2 n$ positions numbered $0$ $0$ through $2n-1$ $2 n - 1$ from left to right.

Adnan wants to rearrange the shoes into a valid arrangement. An arrangement is valid if and only if for every $i$ $i$ $(0 \le i \le n-1)$ $(0 \leq i \leq n - 1)$ , the following conditions hold:

The shoes at positions $2i$ $2 i$ and $2i+1$ $2 i + 1$ are of the same size.
The shoe at position $2i$ $2 i$ is a left shoe.
The shoe at position $2i+1$ $2 i + 1$ is a right shoe.

For this purpose, Adnan can make a series of swaps. In each swap, he selects two shoes that are adjacent at that moment and exchanges them (i.e., picks them up and puts each one on the former position of the other shoe). Two shoes are adjacent if their positions differ by one.

Determine the minimum number of swaps that Adnan needs to perform in order to obtain a valid arrangement of the shoes.

Implementation details

You should implement the following procedure:

Copy

long long count_swaps(std::vector<int> S)

$S$ $S$ : an array of $2n$ $2 n$ integers. For each $i$ $i$ $(0 \le i \le 2n-1)$ $(0 \leq i \leq 2 n - 1)$ , $|S[i]|$ $| S [i] |$ is a non-zero value equal to the size of the shoe initially placed at position $i$ $i$ . Here, $|x|$ $| x |$ denotes the absolute value of $x$ $x$ , which equals $x$ $x$ if $x > 0$ $x > 0$ and equals $-x$ $- x$ if $x < 0$ $x < 0$ . If $S[i] < 0$ $S [i] < 0$ , the shoe at position $i$ $i$ is a left shoe; otherwise, it is a right shoe.
This procedure should return the minimum number of swaps (of adjacent shoes) that need to be performed in order to obtain a valid arrangement.

Examples

Example 1

Consider the following call:

Copy

count_swaps({2, 1, -1, -2})

Adnan can obtain a valid arrangement in $4$ $4$ swaps.

For instance, he can first swap shoes $1$ $1$ and $-1$ $- 1$ , then $1$ $1$ and $-2$ $- 2$ , then $-1$ $- 1$ and $-2$ $- 2$ , and finally $2$ $2$ and $-2$ $- 2$ . He would then obtain the following valid arrangement: $[-2,2,-1,1]$ $[- 2, 2, - 1, 1]$ . It is not possible to obtain any valid arrangement with less than $4$ $4$ swaps. Therefore, the procedure should return $4$ $4$ .

Example 2

In the following example, all the shoes have the same size:

Copy

count_swaps({-2, 2, 2, -2, -2, 2})

Adnan can swap the shoes at positions $2$ $2$ and $3$ $3$ to obtain the valid arrangement $[-2,2,-2,2,-2,2]$ $[- 2, 2, - 2, 2, - 2, 2]$ , so the procedure should return $1$ $1$ .

Constraints

$1 \le n \le 100\,000$ $1 \leq n \leq 100 000$
For each $i$ $i$ $(0 \le i \le 2n-1)$ $(0 \leq i \leq 2 n - 1)$ , $1 \le |S[i]| \le n$ $1 \leq | S [i] | \leq n$ .
A valid arrangement of the shoes can be obtained by performing some sequence of swaps.

Subtasks

( $10$ $10$ points) $n = 1$ $n = 1$
( $20$ $20$ points) $n \le 8$ $n \leq 8$
( $20$ $20$ points) All the shoes are of the same size.
( $15$ $15$ points) All shoes at positions $0, \dots, n-1$ $0, \dots, n - 1$ are left shoes, and all shoes at positions $n, \dots, 2n-1$ $n, \dots, 2 n - 1$ are right shoes. Also, for each $i$ $i$ $(0 \le i \le n-1)$ $(0 \leq i \leq n - 1)$ , the shoes at positions $i$ $i$ and $i+n$ $i + n$ are of the same size.
( $20$ $20$ points) $n \le 1\,000$ $n \leq 1 000$
( $15$ $15$ points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

line $1$ $1$ : $n$ $n$
line $2$ $2$ : $S[0] \ S[1] \ S[2] \ \dots \ S[2n-1]$ $S [0] S [1] S [2] \dots S [2 n - 1]$

The sample grader outputs a single line containing the return value of count_swaps.

Comments

1

python6645 commented on Nov. 29, 2020, 12:33 a.m.

Why is there only one language allowed?

3

Kirito commented on Nov. 29, 2020, 2:04 a.m.

DMOJ only supports signature grading in C/++. As the IOI no longer supports C, this leaves C++ as the only language supported by this problem.

5

ChrisT commented on Nov. 29, 2020, 3:26 a.m.

Note that as of 2021, IOI also no longer supports Java.

0

Dan4Life commented on Sept. 7, 2020, 2:19 p.m.

Can anyone explain the BIT solution

2

MohamedNguira commented on Sept. 7, 2020, 3:45 p.m.

Hint: check what should you update whenever you move the chosen shoe and try updating that with a BIT.

0

EntrenamientoIOIChile commented on Aug. 31, 2020, 1:51 p.m.

Hello! I coded some subtask and DMOJ gave me WA. Looking at the test cases I found my program works fine, but there are some strange codes in the first line of each case. Could you check that, please? :-)

3

Kirito commented on Aug. 31, 2020, 2:52 p.m.

It's a very basic anti-cheating measure employed by the IOI. Unless you're trying to bypass the signature grader it shouldn't matter.