All problems were proposed by Mikhail MikeMirzayanov Mirzayanov.

1283A - Minutes Before the New Year

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
int h, m;
scanf("%d %d", &h, &m);
printf("%d\n", 1440 - h * 60 - m);
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
cin >> n >> k;
int full = n - n % k;
full += min(n % k, k / 2);
cout << full << endl;
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> f(n);
vector<int> in(n), out(n);
for (int i = 0; i < n; ++i) {
cin >> f[i];
--f[i];
if (f[i] != -1) {
++out[i];
++in[f[i]];
}
}
vector<int> loops;
for (int i = 0; i < n; ++i) {
if (in[i] == 0 && out[i] == 0) {
loops.push_back(i);
}
}
if (loops.size() == 1) {
int idx = loops[0];
for (int i = 0; i < n; ++i) {
if (in[i] == 0 && i != idx) {
f[idx] = i;
++out[idx];
++in[i];
break;
}
}
} else if (loops.size() > 1) {
for (int i = 0; i < int(loops.size()); ++i) {
int cur = loops[i];
int nxt = loops[(i + 1) % int(loops.size())];
f[cur] = nxt;
++out[cur];
++in[nxt];
}
}
loops.clear();
vector<int> ins, outs;
for (int i = 0; i < n; ++i) {
if (in[i] == 0) ins.push_back(i);
if (out[i] == 0) outs.push_back(i);
}
assert(ins.size() == outs.size());
for (int i = 0; i < int(outs.size()); ++i) {
f[outs[i]] = ins[i];
}
for (int i = 0; i < n; ++i) {
cout << f[i] + 1 << " ";
}
cout << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(NULL));
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<int> x(n);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
queue<int> q;
map<int, int> d;
for (int i = 0; i < n; ++i) {
d[x[i]] = 0;
q.push(x[i]);
}
long long ans = 0;
vector<int> res;
while (!q.empty()) {
if (int(res.size()) == m) break;
int cur = q.front();
q.pop();
if (d[cur] != 0) {
ans += d[cur];
res.push_back(cur);
}
if (!d.count(cur - 1)) {
d[cur - 1] = d[cur] + 1;
q.push(cur - 1);
}
if (!d.count(cur + 1)) {
d[cur + 1] = d[cur] + 1;
q.push(cur + 1);
}
}
cout << ans << endl;
shuffle(res.begin(), res.end(), rnd);
for (auto it : res) cout << it << " ";
cout << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n;
vector<int> a, cnt;
int solvemin(){
int res = 0;
forn(i, n){
if (!cnt[i]) continue;
++res;
i += 2;
}
return res;
}
int solvemax(){
int res = 0;
int dist = 2;
bool right = false;
forn(i, n){
if (!cnt[i]){
++dist;
continue;
}
int j = i - 1;
int sum = 0;
while (j + 1 < n && cnt[j + 1]){
++j;
sum += cnt[j];
}
res += (j - i + 1);
if (sum > j - i + 1 && (!right || dist > 1)){
--sum;
++res;
}
right = false;
if (sum > j - i + 1){
right = true;
++res;
}
i = j;
dist = 0;
}
return res;
}
int main() {
scanf("%d", &n);
a.resize(n);
cnt.resize(n + 1);
forn(i, n){
scanf("%d", &a[i]);
++cnt[a[i] - 1];
}
printf("%d %d\n", solvemin(), solvemax());
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n - 1);
for (int i = 0; i < n - 1; i++)
{
scanf("%d", &a[i]);
a[i]--;
}
int root = a[0];
int last = -1;
vector<int> used(n, 0);
printf("%d\n", root + 1);
int cur = n - 1;
for (int i = 0; i < n - 1; i++)
{
used[a[i]] = 1;
while (used[cur])
cur--;
if (i == n - 2 || used[a[i + 1]])
{
printf("%d %d\n", a[i] + 1, cur + 1);
used[cur] = 1;
}
else
printf("%d %d\n", a[i + 1] + 1, a[i] + 1);
}
return 0;
}
```

Very cool problem set, except weak C pretests :(.

Amen

I found a $$$O(n)$$$ solution for C that's I think quite easy to both code and understand. We keep everyone who hasn't received a gift in a sorted vector and do the same for the ones that haven't gifted (

$$$rec$$$

and$$$give$$$

). We can construct them in linear time as the input already gives us the second ordered vector and the first one can be constructed using a boolean array that says whether the $$$ith$$$ person has already been gifted. Now we just iterate these two vectors at the same time, and if in the $$$ith$$$ position we find that$$$rec[i]==give[i]$$$

we do$$$swap(give[i], give[i-1])$$$

(if $$$i=0$$$ swap with $$$i+1$$$). It's easy to prove it by induction, as the case where $$$n=2$$$ is trivial and if you already have a correct array with size $$$n-1$$$,$$$n > 2$$$

, if the $$$nth$$$ term is already matched to a different index we don't need to do anything, else we will swap it with it's predecessor and our matching is still valid, as we know we aren't matching it's predecessor with itself as the vector is ordered and$$$rec[n]==give[n]$$$

. My code: 67844246Nice solution. Thanks

I managed to do not exactly the same but yeah it was something like this. But became overconfident when the pretests passed. Could have applied the logic in the end. But fortunately my solution got hacked.

thnx bro

brilliant,thank you very much for this solution

hello,I wonder why that we need to swap(give[i],give[i-1]) can be correct,if we meet rec[i]==give[i],why it is wrong every time we meet that situation we swap (give[i],give[1])

D and E are good problems for Div3 contestants.

Thank you Vovuh for this amazing year!

Explain E?

why does using unordered_map give tle whereas using map my answer got accepted..(I am using BFS in D )

In the worst case, unordered_map runs in linear time. It's risky.

so, when do we use umap and map.

You should use unordered map with custom hash function, otherwise don't use it. Use map or coordinate compression.

Hi Where can I learn coordinate compression from. Can someone provide me with a link.

It is because of the complexity for unordered_map can be O(n). But for a map it is always O(logn).

This generally happens when there are collisions due to which the worst case time complexity of an unordered map is O(n). Problem setters generally make the test cases in such a way that collisions will happen and your solution will time out. Either you can use map or write your own customized hash function.

Consider this link. It explains how an unordered_map works, and how it is probable to be hacked with a TLE verdict, and how it can be prevented by a custom hash. It also includes one custom_hash, but you can always feel free to write one of your own :P

Thank you vovuh for cool amazing contest. My first problem solved in codeforce contest.

Got it1283C I am new to CP. Can anyone explain whats wrong in this approach ?

It is given that the data provided is such that always some solution will exist. So what we do is we just order the edges with next greater element and largest one with smallest. like if we have 2 1 0 0 0

lets iterate till 3 (numbered 1 to 5) then check next greater element who doesn't have any gift , and give it to him. So we give it to 4 then we get to 4 and give his give to 5 and when we get to 5 we give it to smallest that is 3. Whats wrong here? We will get following answer :-

2 1 4 5 3

and for knowing who have any gift i created an array r[i] such that for r[f[i]] = 0 if he have not recieved and r[f[i]] = 1 if he has

For problem C, i found a solution which is easier to both think and code, the time complexity is

O(nlogn), here's my solution :67860783Let's assume the input array and the output array is a[i].Since the answer is a permutation with n distinct integers, and we can only put numbers in postions where in the input a[i] is equal to 0, so firstly i want to know what numbers i can use to put in these positions, you can use

std::setto do that.And then we can iterate from the

`last`

element to the`first`

element, if the current element is equal to 0, we just put the smallest element we can use(your_set_name.begin()) in this positon, and erase it.After that, you may obtain the correct answer, or there is

`only one`

postion i where a[i] is equal i, that's because when we iterate it, we put the element from the last to the first in increasing order, which is decreasing order from the first to the last, so if postion`i`

satisfies`a[i] == i`

, it must be`a[i] > i`

on his left side element he put in, and`a[i] < i`

on his right side element he put in, so there's at most one postion is not correct. At last, we just need to swap the number in this positon`i`

with any postion which was 0 in the input except position`i`

, after the swap, you get the correct answer.I took the same approach but I tried to simplify and just took next greater element. But it was wrong approach as 2 0 1 5 3 0 would give 2 4 1 5 3 0 from my solution. I wish i did as u did , and didn't try to oversimplify things

yep, that's why you have to make sure the number you put in should be in decreasing order, that's more simple to implement it.

I did exactly the same and thought it in the same way but see my foolishness, after even analyzing that there will be a case in which there is one position of i which will satisfy a[i]==i , I didn't check the array again. And eventually I paid the price, my solution got hacked. Here's what I did. Used simple marked array to mark the already existing numbers and then put the numbers which are not present in the array, let's say absent array. Then I sorted it in the increasing order. Then simply iterate through the input array and check if there's an element whose value is zero then I picked the maximum number from the absent array and place it there.67826491

My solution of C: find all chains. How? Beginnings of chains are people who doesn't receive gifts. To find ending: just traverse it until chain ends. When you have

$$$s_i,e_i$$$

— start and end of chains, you just need to connect $$$e_i$$$ with$$$s_{i+1}$$$

, and you're done.For C, I tried a randomized approach. I tried to randomly assign values, not already present in the array, at the vacant positions until a valid solution is found. This approach has a success probability of about 36% (link).

Link: 67832203

However, I don't know why, but the same code received TLE when I submitted it in Pypy2, because of which I ended up spending more than 1 hour for this problem :(

Link to the TLEd Pypy submission: 67817623

My solution of E: lets construct both answers.

Construction of maximum. Sort all people using counting sort of

$$$O(n\,\log(n))$$$

sort. Make array $$$b_i$$$ — how many people will have coordinate $$$i$$$ — result of construction. Iterate over sorted list of people. Assign each friend to lowest unused position he may achieve. Count all used positions. This is maximum. Why? If there is some friend that may move to unused coordinate to the left, it will not decrease number of used cells. It may increase but not decrease. (google charging argument)Construction of minimum.

$$$cnt_i$$$

— how many friends living in coordinate $$$i$$$. Make array $$$b_i$$$ — how many people will have coordinate $$$i$$$ — result of construction. Iterate over $$$i$$$ from $$$1$$$ to $$$n$$$. If$$$b_{i-1} > 0$$$

or $$$b_i > 0$$$ then assign$$$cnt_i$$$

to corresponding coordinate. Otherwise, assign to $$$i+1$$$ coordinate. This is minimum. Why? (not rigorous) Well, we move 'leftmost' friends to the 'rightmost' and merge all that may come in same place. Then we do same untill all friends processed.C has a much easier approach using deque data structure. Insert the positions in deque which are not pointed by anyone. And now put values on place of zero by checking first and last element in deque. Here's my code: https://codeforces.com/contest/1283/submission/67862320

i tried almost the same solution as you but i didn’t check the cnt<2 condition and got hacked after contest :/ But nice solution

As i think map is better than unordered_map. Give me example where Unordered_map is better than map..!

Any help for problem m F

For Problem F, we can think of the tree as rooted at the lamp connected to the power grid. We first notice that the first number in the input array must be the root. We can then maintain a list of all the "leaf" nodes (those that never appear in the input array, i.e. those nodes that are never the "main lamp" for any wire). Then, because the parent of largest leaf node would have appeared earlier in the input, we can match the smallest unprocessed leaf to the last number in the input array, remove the leaf, then update the list of unprocessed leaves (if necessary), and do this repeatedly.

Consider the sample input:

The first number in this input array is $$$3$$$, so $$$3$$$ is the root of our tree.

We know that every node (except the root) has exactly one parent, and some number of children nodes, so we can start by maintaining a

`degree`

array, which is equal to`1`

(for the connection to the parent) plus`x`

, if the node appears in the input array $$$x$$$ times (it is the parent of $$$x$$$ nodes). For the given input, the degree array will then be:We note that the degree of $$$3$$$ is one more than the true degree, because $$$3$$$ has no parent. So, we decrement $$$1$$$ from the degree of $$$3$$$.

From our

`degree`

array, we can look for all nodes with a`degree`

of $$$1$$$, which will be our unprocessed leaf nodes, in this case`[2, 4]`

. This can be effectively maintained using a`priority_queue`

or other such data structures.Now, we iterate backward through the input array to match each leaf to its parent. We process all the leaves in sorted order, because the parent of a lighter leaf would appear later in the input.

The last number in our input array is $$$5$$$, so the parent of $$$2$$$ (the smallest unprocessed leaf) is $$$5$$$. Now we remove $$$1$$$ from the

`degree`

of $$$2$$$, and one from the`degree`

of $$$5$$$, and add an edge in our final output between $$$2$$$ and $$$5$$$. We do not need to consider the node $$$2$$$ anymore. For node $$$5$$$, it has now become a new leaf (its`degree`

is now $$$1$$$) so we push it into our`priority_queue`

for processing.Now, the smallest leaf is $$$4$$$, so we can look at the next item in the input array (going backwards), which is $$$1$$$. We add an edge in our output between $$$4$$$ and $$$1$$$. We decrement the

`degree`

of $$$1$$$ and $$$4$$$, and as the degree of $$$1$$$ now also becomes $$$1$$$, we push it to our leaf`priority_queue`

. We do not need to consider the node $$$4$$$ anymore.We repeat this process until we have processed all leaf nodes (we need to be careful not to process $$$3$$$, as it is the root), and then output our answer.

thanks for your solution nice method~

In what case will F have no answer? when to print -1?

There is always an answer (:

Easy solution for C. https://codeforces.com/contest/1283/submission/67815280 just map thing

My solution for F. You can observe that you can make the more important link's main as the parent of the less important link's main. Thus we iterate through the array and make the next number as the child of the first number. Else, if we can't do that, that is the next number in the array is already used, we can make the biggest number available as its child. This comes from the fact that a power of 2 is bigger than all other powers of 2's less than itself. Otherwise, if there is no number left to assign, then we say that such an arrangement is not possible.

Good round, thanks to organizers :)

can any one tell me that how is my code wrong if it is same as editorial solution...? please tell me i couldn't understand this.

Solution link -> https://codeforces.com/contest/1283/submission/67808841

## include

using namespace std;

int main() { long int tc; cin>>tc; while(tc--) { long long int n,k,i,j; cin>>n>>k; if(n<=k) cout<<n<<endl; else { if(n%k==0) cout<<n<<endl; else { j = (n%k-(k/2)); if(j>0) i = n — j; else i = n;

}

D was nice problem

Can You Please Explain the Solution of D ?

Ez solution for E https://codeforces.com/contest/1283/submission/67867801

Could anyone help out on why is my solution getting a TLE for Problem D ? (https://codeforces.com/contest/1283/submission/67857488)

are you sure that m reaches 0. your m-- is inside if condition.

wrong answer The value of nf_7 should be equal to f_7

my solution 67869058 for C is failing 2nd test case with this error can someone explain me this.

very easy solution for E. https://codeforces.com/contest/1283/submission/67869665 just map thing..!

Can you explain the solution?

My approach for problem C:

First, I store all the node with

`indegree`

equals to`0`

, which I call list of starting node, iterate all of these nodes, at each node $$$v$$$, just go to next node unless you can't, assuming now you are on node $$$u$$$, connect $$$u$$$ with the node after $$$v$$$ in the list of starting node. My submissionProblem E is exactly greedy approach, but the provided implementation is quite hard, my implementation is just greedy and lay each person at greedy position, afterward count the number of positions which were occupied. My submission

how does the solution of new year parties work? can anybody explain in simple terms? in maximization case?

To weak C pretests.

Can someone tell me what's wrong with my solution to the problem C? First I collected all points s.t. a[i] = 0 and i does not give gift to anyone. Then I rotated the array. For all other points, I simply printed it as it. Here is the link https://codeforces.com/contest/1283/submission/67874440

My DP solution for E,both subtasks are similar,sort the array,now however we move the people,the final positions should be sorted too,there are only 3 states possible.Try them all! https://codeforces.com/contest/1283/submission/67875164

The code is almost same for both subtasks(change min to max)

# SAY-NO-TO-GREEDY

Please explain problem E :/

Hi guys, am getting WA on test case 44 for problem D

can someone please identify my mistake

MY Approach:- am using visited (map) to mark all unavailable points, and in the pair ( pair<int,int>) am storing point x in first part of pair and in second part of pair 1 for forward movement and 0 for backward movement then i take points one by one and according to the movement type i check is the movement of the point i just selected possible or not , e.g if the point that i took out of queue is forward based then i check is it possible to take the point after this using the visited map if possible then push the next point to queue and c is a queue used to store the corresponding distance of the point in queue 'v' , took c separately so as to make code more readable

please help me find my mistake

my_solution

Thanks in Advance

https://codeforces.com/contest/1283/problem/C

how to add the elements that are not present in the array in the places where Zeroes are present.. anyone please help

## include <bits/stdc++.h>

## include

## include <string.h>

## include <math.h>

using namespace std;

int main() {

int n,x;

cin>>n;

vectorv;

vectora;

vectorv3;

for(int i=0;i<n;i++){

cin>>x;

if(x!=0) a.push_back(x);

v.push_back(x);

}

//int ans[3] = {2,4,5};

for(int j=1;j<=n;j++){

int flag = 1;

for(int i=0;i<3;i++){

cout<<j<<" "<<a[i]<<endl;

if(j == a[i]){

}

for(int i=0;i<v.size();i++){

if(v[i] == 0 && v3[i] != i){

}

for(int i=0;i<v.size();i++){

}

return 0; }

Can anyone please tell me what is wrong in this code for PROBLEM-1283B

`~~~~~`

- 1. — 1. — ~~~~~ Your code here... ~~~~~int main() { ll t,i; cin>>t; while(t--) { ll n,k; cin>>n>>k; if(n<k) { ll val1=k/2; n=min(n,val1); cout<<n<<endl; } else {ll rem=n%k; ll val=k/2; if(rem!=0) rem-=val;

}

}

``~~~~~``

``n=5, k = 4 your answer is 6, it should be 5

I've got a very good solution to Problem D using Binary Search :O

Can you explain your solution to me please?

Can somebody explain his solution of C, how to consider permutation as a graph?

Hi,guys,I want to know the reason of get WA on problem C in my solution. Order the list of unreceiver from greater to less,if the size of the list is odd,swap the mid one and the mid one + 1,and output them,if now position is zero,output the previous list by order. But I get WA in test 12,i don't know why...,hope someone could give me an example. Very thanks.

i dont clearly understand that how should we choose the first tree-posotion from which the multisource bfs should start.

While solving problem 1283C - Friends and Gifts, a vey weird thing happened. When i submit my solution 68002964 in pypy , it says wrong answer on testcase 5, but when i submit the same code in python 68003409, it becomes accepted. Does anybody have any idea as to why it might be happening?

vovuh Thanks for great contest :)

when you will write a tutorial for problem F 1283F - DIY Garland

(F) why does this O(n^2) solution work?

It looks like it is $$$O(n^2)$$$ but actually it is $$$O(n)$$$ since each element is visited at most once by both $$$i$$$ and $$$cur$$$ leading to $$$2n$$$ operations.

O(n) solution for C: https://codeforces.com/contest/1283/submission/67981767

Algo: 1) Keep a boolean array for received and a array for gift-to index (which is the input basically). 2) Iterate through gift-to array. If you find a zero, iterate in reverse through the received array. If you find a false ie that person hasnt send a gift break. 3) if the indexes of both loops are not equal simply assign and push the index in the assigned vector. 4) But if the indexes are equal we have to either of both things either or both of which is possible. * Swap from the assigned vector. But what if the assigned vector is empty? [This is exactly why my initial solution got hacked :( ] * Iterate through boolean array using a temporary index initialized at current index. Find another index that hasn't gifted and assign. Then reset that index to the current index.

If you want a problem D Video tutorial: https://www.youtube.com/watch?v=mb9two5KApU

editorial of F reminds me Half-life 3)

The problem F is simply just decode the given Prüfer code.

Can anyone explain B problem?, I couldn't get it.

Soon...? It's been a month already.

Got hacked for a test case C