Solving Codeforces Problem: 136A - Presents

Today we are going to attempt to solve the Codeforces problem: 136A - Presents. Alright! so let's begin.

Table Of Contents

• The Question
• My Analysis with Sample Examples
• Code and Complexity
• Links and References

The Question

Problem Statement

Little Petya very much likes gifts. Recently he has received a new laptop as a New Year gift from his mother. He immediately decided to give it to somebody else as what can be more pleasant than giving somebody gifts. And on this occasion he organized a New Year party at his place and invited n his friends there.

If there's one thing Petya likes more that receiving gifts, that's watching others giving gifts to somebody else. Thus, he safely hid the laptop until the next New Year and made up his mind to watch his friends exchanging gifts while he does not participate in the process. He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi. He also remembered that each of his friends received exactly one gift.

Now Petya wants to know for each friend i the number of a friend who has given him a gift.

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. The second line contains n space-separated integers: the i-th number is pi — the number of a friend who gave a gift to friend number i. It is guaranteed that each friend received exactly one gift. It is possible that some friends do not share Petya's ideas of giving gifts to somebody else. Those friends gave the gifts to themselves.

Output

Print n space-separated integers: the i-th number should equal the number of the friend who gave a gift to friend number i.

My Analysis with Sample Examples

Now, before discussing the solution, I first need to address a mistake in the description in the input of the question as given on Codeforces. In the input description, it says that:

the i-th number is pi — the number of a friend who gave a gift to friend number i.

This is not how the input is given in the various test cases. On closer inspection this is very similar to the description of the expected output of the questions:

i-th number should equal the number of the friend who gave a gift to friend number i.

So, now the natural question you'll be asking is "What exactly is the input format?"

If we re-examine the description of the Problem Statement above, we see the line:

He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi.

Eureka! This is the correct description of the input format! We can verify this as well with the given sample examples. Let's try that now.

Example-1

Input

4
2 3 4 1

Here, on the first line we are given that Petya invited 4 friends to the party (I sincerely hope none of his friends got left out 😅), and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

1. Friend 1 gave a present to Friend 2
2. Friend 2 gave a present to Friend 3
3. Friend 3 gave a present to Friend 4
4. Friend 4 gave a present to Friend 1

Alright, so now what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

4 1 2 3

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

1. Friend 4 gave a present to Friend 1
2. Friend 1 gave a present to Friend 2
3. Friend 2 gave a present to Friend 3
4. Friend 3 gave a present to Friend 4

Output

4 1 2 3

Example-2

Input

3
1 3 2

Here, on the first line we are given that Petya invited 3 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

1. Friend 1 gave a present to Friend 1
2. Friend 2 gave a present to Friend 3
3. Friend 3 gave a present to Friend 2

Alright, so other than the fact that Friend 1 doesn't seem to have the New Year spirit, what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

1 3 2

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

1. Friend 1 gave a present to Friend 1
2. Friend 3 gave a present to Friend 2
3. Friend 2 gave a present to Friend 3

Output

1 3 2

Example-3

Input

2
1 2

Here, on the first line we are given that Petya invited 2 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

1. Friend 1 gave a present to Friend 1
2. Friend 2 gave a present to Friend 2

Alright, so other than the fact that Friend 1 and Friend 2 should starting asking themselves why they came with presents to the party, what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

1 2

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

1. Friend 1 gave a present to Friend 1
2. Friend 2 gave a present to Friend 2

Output

1 2

Code and Complexity

Alright, so now we know how to interpret out input and process it to get our output. To be extra sure we have also verified our logic over the given examples as well. Let's now translate this logic into code. For this I'll be using modern C++ (C++11 and beyond), so that it's easier to get the big picture logic which is implemented in the code.

Another interesting reason to use modern C++ is that some of its features make the code more readable and similar looking to Python code (many people consider this a plus).

/**
 * @file 136A-Presents.cpp
 * @author Rishit Chaudhary (@rishitc)
 * @version 1.0
 * @date 2021-06-23
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    int p;

    std::cin >> n;

    int ans[n];

    for (int i = 1; i < n + 1; ++i)
    {
        std::cin >> p;

        ans[p - 1] = i; // Zero index correction for p
    }

    for (int i = 0; i < n; ++i)
    {
        std::cout << ans[i] << " ";
    }
    std::cout << "\n";
}

Complexity

Complexity Type	Answer	My Comments
Time Complexity	O(n)	n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party.
Space Complexity	O(n)	n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party.
Difficulty (subjective value)	Easy	The use of language in the question combined with the mistake in the description of the input does make the question a bit hard to grasp at first.

Links and References

Link to the problem: https://codeforces.com/problemset/problem/136/A
Link to my submission: https://codeforces.com/contest/136/submission/120021060
Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/136A-Presents.cpp

Comments

[Thivyaa Mohan]

Great explanation! Thankyou for posting :)