Pinely Round 2 Editorial

4 weeks ago, # |

-10

can't understand editorial of b

→ Reply

amansingh81757

4 weeks ago, # ^ |

take for example a permutation where 2 appears after 3 whereas to make the permutation sorted 2 needs to appear before 3. For this to happen we must choose 2 as our x and perform the operation this will reposition 3 after 2. Hence we do this for all x where x+1 lies before x in the given permutation.

→ Reply

Kapil707

4 weeks ago, # ^ |

How do you understand the institution, or did you saw any pattern in this? I'm very slow, any suggestions to solve questions related to strings and arrays on competitive platforms, I feel they are tough for beginners like me

→ Reply

Medeali

4 weeks ago, # ^ |

My advice is solve more problems,for improving your implementation so you can crack A quickly solve topcode div2 and for constructive problems just keep solving more problems as time goes on ideas will repeat i know it seems like impossible but yes and this way you train your brain to think of different patterns. So as conclusion if you want to have intuition solve problem especially constructive but don't forget about learning other new algorithms and implementing them or using them to solve the problems.You need to find the balance that's it and of course it takes real time to improve so you need to keep hardwork.

→ Reply

Akr.

4 weeks ago, # ^ |

The worst case for this will be O(n^2). Won't it give me TLE?

→ Reply

4 weeks ago, # ^ |

← Rev. 3 →

it can be done in O(n) using map or visited array or it can also be done as mentioned in this comment

→ Reply

4 weeks ago, # ^ |

thanks for the help and apologies for the late reply

→ Reply

Benny20

4 weeks ago, # ^ |

← Rev. 2 →

It says that if the pair of values $$$(k, k+1)$$$ appears inverted in the input permutation, then you need to perform the operation with $$$x = k+1$$$ in order to get rid of that inversion. Now, just note that if you consider all these pairs and perform the operation when needed, starting from $$$k = 2$$$ until $$$ k = n$$$, the permutation will be ordered.

→ Reply

4 weeks ago, # ^ |

thanks for the help and apologies for the late reply

→ Reply

Has_Aim

4 weeks ago, # ^ |

let's start from k = 1 and see if the (k + 1) position comes after the k position we stop when the condition fails and count it as a turn we chose x as the last item that we get, then we pick another k just the last item we didn't get from the previous turn, Each time we write a set of numbers in the correct order as much as we can, So the answer is the number of turns. To do that just count how many pos[i] > pos[i + 1] for all i from 1 to n — 1. It's exactly this problem : Collecting Numbers

→ Reply

4 weeks ago, # ^ |

← Rev. 3 →

thanks for the help and apologies for the late reply split sort and Collecting numbers can be done like this sort the array keeping their index start iterating from i = 2 if(index of i < index i — 1) ans++

it can further be optimised as number are 1 — n, we can just place the index of x to the index x in sorted array

thanks suggesting the Collecting Numbers as it made me understand the concept https://cses.fi/paste/17d0c105267da8d76a177b/

→ Reply

ismoilmirzouz

4 weeks ago, # |

-24

Video tutorial for problems A&B&C in english: https://youtu.be/X08zbEDtaI8

Thought would be useful to the community

→ Reply

Son_of_Dijkstra

4 weeks ago, # |

+12

really liked D and E. I hope there will be more such great contests!

→ Reply

Phyus003

4 weeks ago, # ^ |

me too

→ Reply

manitianajay45

4 weeks ago, # |

← Rev. 2 →

+10

Video Editorial for problem A,B,C,D.

→ Reply

YashBihany

4 weeks ago, # |

how is O(N^2) possible in F with the given constraints on N? also can you provide test case 3? 1863F - Разделяй, считай XOR и властвуй

→ Reply

Sinocchi

4 weeks ago, # |

+23

Finally, editorial written not in broken English

→ Reply

kratos56

4 weeks ago, # |

Can't understand E. explain

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

+19

Let, firstly, solve simpler problem. Assume starting time is $$$0$$$ (meaning the first imaginary quest which is prerequisite of any other quest was done at day 0, hour 0). Maintain a $$$dp$$$ array, where $$$dp[v]$$$ is the day when the quest $$$v$$$ is completed. It's clear that if the quest has no prerequisite it's $$$dp$$$ value is zero. Otherwise, let $$$u_1,...,u_k$$$ be prerequisites of $$$v$$$, then $$$dp[v] = max(dp[u_i] + f(u_i))$$$ where $$$f(x) = 1$$$ if $$$h[x] > h[v]$$$ and $$$f(x) = 0$$$ otherwise. Answer to the problem is maximum value of $$$dp[v] * k + h[v]$$$ (Since we are counting starting time as $$$0$$$ and $$$v$$$'s quest is done after $$$dp[v]$$$ days on $$$h[v]$$$ hours). However, we need to choose optimal starting time and somehow maintain the answer. Notice that optimal starting time is some $$$h[i]$$$, where $$$i$$$'s quest has no prerequisite. Assume $$$v_1,...,v_k$$$ are such quests and WLOG assume $$$h[v_1] <= ... <= h[v_k]$$$. We will update starting time from $$$0$$$ to $$$h[v_1]$$$, from $$$h[v_1]$$$ to $$$h[v_2]$$$ and so on to $$$h[v_n]$$$. Let assume we are making transition from $$$h[v_i]$$$ to $$$h[v_{i+1}]$$$. So firstly we must update $$$dp[v_{i + 1}]$$$, then we mist update it's children. So we can simple use DFS. Also notice that every quest will be updated only once, so it should pass the time limit.

→ Reply

AndiR

4 weeks ago, # ^ |

← Rev. 2 →

don t you update dp[vi] in the transition?

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

Yes, I do. Its value increases by 1.

→ Reply

NotImplemented

4 weeks ago, # ^ |

We only going deeper from the current vertex only if dp[v] is increased by one (and this can happen only once). Correct me if I am wrong, please.

→ Reply

4 weeks ago, # ^ |

Indeed.

→ Reply

FragmentsZZ

4 weeks ago, # ^ |

oh, you're so helpful. It confused me a lot, I'm always thinking why the complexity is right, thank you.

→ Reply

ParasBedi298

4 weeks ago, # |

← Rev. 2 →

Would someone please help me understand why my submission for E (221172178) giving TLE. According to me, the time complexity of this code should be O(m+n*lgn), since I am traversing through each edge only once while doing DFS.

→ Reply

b-baka

4 weeks ago, # ^ |

Your final for loop is O(N^2) since you call max_element

→ Reply

ParasBedi298

4 weeks ago, # ^ |

Ohh, got it. Thanks!
I was stuck finding mistake in recursive function, just ignored this. Thanks a lot :)

→ Reply

StarSilk

4 weeks ago, # |

+80

EFG are all excellent problems. Failed to solve F because I mistakenly thought that 1<=n<=1e5.

→ Reply

AndiR

4 weeks ago, # |

← Rev. 2 →

Why for problem E f(x, y) is defined only with y?

→ Reply

pedrosorio

4 weeks ago, # ^ |

+11

Has to be a typo. In the definition they meant to write z >= max(x, y).

→ Reply

anikpodder

4 weeks ago, # |

Thanks for the fast editorial!

→ Reply

bestial-42-centroids

4 weeks ago, # |

Thanks for this nice round, and fast editorial!

Here is my advice about the problems:

Also, could you please clarify a bit the second part of the editorial of F please ? Maybe I'm just bad at english but I don't understand what mask_start and mask_end correspond to

Thanks :)

→ Reply

JeanBombeur

4 weeks ago, # ^ |

+11

For point $$$i$$$, if the xor of an interval $$$[i, r[$$$ contains a bit of $$$maskStart_i$$$, then it means it is obtainable, since at one point prior, an interval $$$[i, r'[$$$ with $$$r' > r$$$ had that bit for most significant bit of the xor. Same for $$$maskEnd_i$$$.

So you keep these $$$2N$$$ masks as you iterate over subarrays in length non-increasing to know which ones are obtainable.

By the way I love your profile picture, where is it from ?

→ Reply

bestial-42-centroids

4 weeks ago, # ^ |

Thanks, very clear!

You already know where it comes from

Spoiler

→ Reply

Algeo3603

4 weeks ago, # |

C can also be solved using binary lifting. Overkill, but if you spot it quickly, you could just a use a template for insta solve Here is my solution

→ Reply

Omars

4 weeks ago, # |

In problem E, can ternary search be used for finding the optimal starting point?

→ Reply

4 weeks ago, # ^ |

I thought on the same idea during the contest, but couldn't do it. The problem with the ternary search was that the function isn't strictly increasing/decreasing, meaning there is some value x, for which $$$f(x) = f(x + 1)$$$, but $$$f(x)$$$ isn't extremum of the function.

→ Reply

applepi216

4 weeks ago, # ^ |

+24

I think it's not just about $$$f(x) = f(x + 1)$$$, but that the function can also alternate going up and down wildly (or at least, that's what I saw when testing this locally).

→ Reply

4 weeks ago, # ^ |

You could be right. I just tested the given examples and noticed the problem I mentioned above. I didn’t dig deeper.

→ Reply

butterflies

4 weeks ago, # |

Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-pinely-2/. This will help us get more data so users can have a platform to:

share/discover hints/insights on various problems
find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

→ Reply

Medeali

4 weeks ago, # |

i think the problem C was very easy especially compared to B too bad i did not read it early.

→ Reply

Kurta_Sofia

4 weeks ago, # |

thanks for the exciting tasks, as for me the gap between D and E is too big

→ Reply

Soultaker

4 weeks ago, # |

+17

For problem E, I didn't understand the editorial, and most other solutions seemed to use some form of Dynamic Programming, which seems different from what I did.

I start by calculating the maximal end time when you start questing at the earliest possible time, which is easy to calculate in O(V + E) time using the topological ordering of the DAG. However, this might not be optimal: it can be better to defer some quests to day 2 so we can start later in day 1, without affecting the end time. So I consider all the starting times of quests that have no dependencies. The key is that I update the end times for other quests incrementally, for an overall O(V + E log V) solution.

Submission with a (too many) comments: 221200048

→ Reply

tfg

4 weeks ago, # ^ |

There's no need for that log, that's what I did as well. Your first step is dp, so I don't get why you're talking about others "using some form of DP".

→ Reply

mohitejaikumar

4 weeks ago, # ^ |

mark me if I am wrong ? What I got from your code is that particular (ith) quest with (0 dependency) can either be done at (h[i] or h[i]+k) hours so after that you are checking effect of (h[i]+k) ending on other quest so , its complexity will be O((number of 0 dependency node)*(ElogV)) how its possible to get accepted , or It is like each quest can be updated one ,if it is then why it is updated once , please explain

→ Reply

Soultaker

4 weeks ago, # ^ |

I tried to explain that in the last two paragraphs of the comments at the top of the file. It's not immediately obvious, but for each vertex v, we increase end_time[v] at most once, by exactly K. That means it's actually just O(V + E log V) time overall, not O(V + VE log V) as it would otherwise be.

And tfg pointed out, correctly, that the priority queue is not needed, so instead of O(E log V) it could be something like O(E), but the really important part is that it's not O(VE), which would be much too slow to pass. The difference between O(E) and O(E log V) is relatively small.

→ Reply

primesadist

4 weeks ago, # ^ |

Honestly, your explanation should be to the editorial. It's so much simpler to understand.

→ Reply

Rose

11 days ago, # ^ |

Thank you so much. Easy to understand.

→ Reply

NoLove

4 weeks ago, # |

It is the greatest contest I have ever seen

→ Reply

MMihalev

4 weeks ago, # |

How to solve D if you must colour all cells, not only the domino ones?

→ Reply

4 weeks ago, # |

+29

Why I didn’t solve F

→ Reply

4 weeks ago, # ^ |

Here's my wrong idea on F: (maybe it's right, I don't know)

Let $$$s(l,r)=a_l\oplus a_{l+1}\oplus\dots\oplus a_r$$$.

First let's reverse the operations. Instead of changing subarray $$$[1,n]$$$ into $$$[i,i]$$$, we try to expand $$$[i,i]$$$ into $$$[1,n]$$$. For a subarray $$$[l,r]$$$, we need to find an adjacent subarray (either $$$[r+1,x]$$$ or $$$[x,l-1]$$$) which has a smaller $$$xor$$$ value than $$$s(l,r)$$$, and merge them.

Let's look at the maximum most significant bit of all $$$a_i$$$. Let $$$cnt$$$ be the number of $$$a_i$$$ s that have this bit. Let $$$b_1,b_2,\dots,b_{cnt}$$$ be all $$$i$$$ that $$$a_i$$$ has this bit.

If $$$cnt$$$ is odd, then only $$$b_1,b_3,\dots,b_{cnt}$$$ are valid.

If $$$cnt$$$ is even, then all $$$i\in[b_{2k-1}+1,b_{2k}-1]$$$ are invalid. We can merge all $$$a_{b_{2k-1}}\ \ ,a_{b_{2k-1}\ \ +1},\dots,a_{b_{2k}}$$$ into one number, which is $$$s(b_{2k-1},b_{2k})$$$. Then, the maximum most significant bit is gone and we go on to solve the problem for a smaller bit. What I still can't figure out is how to solve for $$$a_{b_i}$$$. Maybe it could be solved using Segment Tree.

→ Reply

tfg

4 weeks ago, # ^ |

Some people like gamegame solved it in something like you tried to do. https://codeforces.com/contest/1863/submission/221171705

→ Reply

https://codeforces.com/contest/1863/submission/221150801

4 weeks ago, # ^ |

Thanks! This code is even faster than the editorial. I will check it out.

→ Reply

Renauga

4 weeks ago, # ^ |

← Rev. 4 →

Can you explain why we can merge in the part when $$$cnt$$$ is even?

→ Reply

Phyus003

4 weeks ago, # |

+10

I love F very much.Hope there will be more problems like this.

→ Reply

maxlevel_youmu

4 weeks ago, # |

+10

Can I ask? Why my 7th test got a negative number? I didn't see any "out range" in my variety (for example, when I'm finding the missing number, I'm using long long)

→ Reply

Omars

4 weeks ago, # ^ |

+10

(n+1) * n will overflow because n is an int. Cast n to long long or declare it that way from the beginning

→ Reply

4 weeks ago, # ^ |

When you multiply (n+1) and n, because they are both int values, it overflows before stored into variable missing. Just change one of them into long long then multiply.

long long missing = (n + 1) * (n) / 2; should be changed to long long missing = 1ll * (n + 1) * (n) / 2; or long long missing = (long long)(n + 1) * (n) / 2;.

→ Reply

maxlevel_youmu

4 weeks ago, # ^ |

+10

I see, thank you both for helping me.

→ Reply

old_wrp

4 weeks ago, # |

+18

is there any other solutions to f？

→ Reply

_DuMoH4uK_

4 weeks ago, # |

Can someone explain F more clearly?

→ Reply

falak_singla

4 weeks ago, # |

what is test 72 in test case 2 in D?

→ Reply

arn200

4 weeks ago, # ^ |

← Rev. 3 →

4 4

LRLR
.LR.
.LR.
LRLR

→ Reply

TheHoodyGang

4 weeks ago, # ^ |

How did you know about this @arn

→ Reply

Jupiter_is_BIG

4 weeks ago, # |

Can someone help me with P5? My idea was to perform a dfs to find pairs (s1,s2) of optimal start time and end time for each component of the directed graph. If d is the number of connected components in the graph, then we will have d such (s1,s2) pairs. Then, I sorted this vector of pairs and found the optimal time.

Issue is I am getting TLE on test case 18. I don't see which operation is being so expensive. Any help will be highly appreciated.

Source Code

Code

#include <bits/stdc++.h>
using namespace std;

#define ANAND ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rep(i, m, n)  for (ll i = m; i < n; i++)

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> vecc;
typedef vector<pll> vecp;

ll k;

void dfs(vecc& graph, ll root, vec& h, ll day, ll time, vec& visited, ll& s2) {

	if (visited[root] > day*k + time) return;

	visited[root] = day*k+time;

	s2 = max(visited[root], s2);

	for(auto& q: graph[root]) {
		if (h[q] < h[root]) {
			dfs(graph, q, h, day+1, h[q], visited, s2);
		} else {
			dfs(graph, q, h, day, h[q], visited, s2);
		}
	}
	
}


void SOLVE() {
	ll n, m;
	cin >> n >> m >>k;

	vec h(n+1); // hours of i is h[i]

	rep(i,1,n+1) cin >> h[i];

	vecc graph(n+1);
	rep(i,0,m) {
		ll a,b;
		cin >> a >> b;
		graph[a].push_back(b);
	}
	
	vec visited(n+1, -1); // visited stores the time required to be completed with inital value -1 (if unvisited)
	vecp sdata; // (s1,s2)

	ll newMax = -1;

	rep(i,1,n+1) {
		if (visited[i] != -1) continue;
		
		ll s1 = h[i];
		ll s2 = h[i];

		dfs(graph, i, h, 0, h[i], visited, s2);
		newMax = max(newMax, s2);
		sdata.push_back({s1,s2});
	}

	sort(sdata.begin(), sdata.end());

	ll d = sdata.size();
	ll ans = newMax - sdata[0].first;

	rep(i,0,d-1) {
		ll newMin = sdata[i+1].first;
		newMax = max(sdata[i].second + k, newMax);
		ans = min(ans, newMax - newMin);
	}
	cout << ans << "\n";
}


signed main() {
	ANAND;
	
	ll _;
	cin >> _;
	while(_--) {
		SOLVE();
	}
	return 0;
}

→ Reply

tcskiran

4 weeks ago, # |

What is test 72 in test case 2 of D

Getting wrong answer for that https://codeforces.com/contest/1863/submission/221170325

→ Reply

Mango.Shake

4 weeks ago, # ^ |

← Rev. 2 →

LRLR
.LR.
.LR.
LRLR

→ Reply

aditya_108

4 weeks ago, # |

← Rev. 2 →

In problem E can anybody help me understand why every node's time is going to be updated at most once ??

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

If you start the process on the 2nd day instead of the first, every value will increase by 1. So, if you had started earlier (meaning on any time of the day 1), values couldn’t have been bigger. Hence, they can increase only once.

→ Reply

liwuyou

4 weeks ago, # |

How difficult are the H and I questions? How come no one has worked them out during the contest... Including our dear Tourist, Radewoosh, JiangLY and so on...

→ Reply

systuum

4 weeks ago, # |

221228312 please help me with the test case on which this submission is failing in the problem 1863D - Two-Colored Dominoes

→ Reply

yuvrajsingh_1

4 weeks ago, # |

I just want to ask what happens if the number in the array provided is not in 0 to n as it is obvious that it wil come in 0 to n+1 with leaving the last element but how can a person do that question because in c it is already given it is in 0 to n So what wil be the difficulty of the above with the present C?

→ Reply

electric_boogaloo

4 weeks ago, # ^ |

+11

If the original array could have duplicates or values outside of range [0, n] the solution would be still pretty much the same. You can manually perform one operation on the original array, now all values are going to be MEX of some arrays of length $$$N$$$, so that guarantees that all values are now in range [0, n], moreover, after performing such an operation there can't be two duplicate values in the array. All that's left to do now is to decrease k by one and calculate the cyclic shift for k modulo n + 1.

→ Reply

yuvrajsingh_1

4 weeks ago, # ^ |

Yes it's true but can you please explain how to implement this in O(n). Thanks for replying.

→ Reply

electric_boogaloo

4 weeks ago, # ^ |

← Rev. 2 →

+11

Well this is the approach I came up with during the contest, my submission: 221139985

Although I believe it has $$$O(nlogn)$$$ time complexity because I used a set<int> to calculate the MEX values, also you might want to be a little bit more careful to handle the out of range and duplicate values correctly

→ Reply

yuvrajsingh_1

4 weeks ago, # ^ |

Ohh thankyou so much that's what my intention is your code is same like that

→ Reply

Comsic

4 weeks ago, # |

In problem C, let n=1,k=1,arr={3} then MEX would result " -2 according to code " but in question its states that mex cannot be negative. Please justify.

→ Reply

woonder

4 weeks ago, # ^ |

+11

Elements in array can't be bigger than n.

→ Reply

Comsic

4 weeks ago, # ^ |

Ok got it. Thanks woonder!

→ Reply

ljr1234

4 weeks ago, # |

In the solution of problem F，should the condition be $$$s & mask_start_l > 0$$$ or $$$s & mask_start_r > 0$$$

→ Reply