You guys should've read problem I first, smh

By the way it's my meme.

what happened to "doomsday" and tester comments :O

tricky Questions!!

problem C — summing all values of consecutive differences and checking if its greater than zero passes the system tests, I don't know whether its based on some proof and is correct or its wrong and bad system tests that let it pass. Any help will be appreciated.!

link to solution

https://codeforces.me/contest/1375/submission/85969397 can u please tell me what's going wrong in this??

Extremely liked problems C & F, thanks a lot for such a nice trolling!

Thanks for the interesting round and editorial!!! now I can solve the problem e, f

this is my solution for D which fails in tc 2 because my resultant array is 0 1 2 3 4 5 7 and not 0 1 2 3 4 5 6 in test number 2 if there is any other mistake please inform me ....thanks ....pretty good contest and kudos to the problem setters

[deleted]

Why so many wrong submissions for C even by red coders.

~~~~~
There also exists O(n) solution for d
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define tf(x) get<0>(x)
#define ts(x) get<1>(x)
#define tt(x) get<2>(x)
#define endl '\n'
#define F first
#define S second 
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define ve vector <int>
#define vep vector<pii >
#define mod 1000000007
#define maxn 2e5+5
#define ld long double
#define in insert
#define fr(i,a,b) for(int i=a;i<b;i++)
#define forn(i,n) for(int i=0;i<n;i++)
#define fora(m) for(auto it:m)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

void solve() {
	int n;
	cin>>n;
	int a[n];
	forn(i,n) cin>>a[i];
	map <int,int> m;
	ve v;
	forn(i,n) {
		if(a[i]==n) v.pb(i);
		else {
			if(!m[a[i]]) m[a[i]]=i+1;
			else v.pb(i);
		}
	}
	int b[n];
	forn(i,n) b[i]=-1;
	fora(m) b[it.S-1]=it.F;
	ve aux;
	fora(m) aux.pb(it.F);
	sort(all(aux));
	int l=0,r=0;
	if(aux.size()==0) aux.pb(-1);
	forn(i,n) {
		if(l==aux.size() || i!=aux[l]) {
			b[v[r]]=i;
			r++;
		}
		else l++;
	}
	set <int> s;
	forn(i,n) 
		if(b[i]!=i) {
			s.in(i);
		}
	int curr=n;
	l=-1;
	if(s.size()!=0) l=*s.begin();
	 while(!s.empty()) {
	 	int tmp=b[l];
	 	b[l]=curr;
	 	v.pb(l);
	 	if(s.find(l)!=s.end() )s.erase(l);
	 	l=tmp;
	 	curr=tmp;
	 	if(curr==n and s.size()!=0) l=*s.begin();
	 }
	 if(l!=n and l!=-1) v.pb(l);
	 cout<<v.size()<<endl;
	 fora(v) cout<<it+1<<" ";
	 cout<<endl;
}
signed main() {
	IOS
	int t=1;
	cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

Thank you very much for this round :p

nearly 21000 participants registered and only about 8000 solved problem A so either participants are becoming too much conscious about their rating that they don't submit if they didn't solve problem A fast or problems were that tough but i don't think A and B were tough.so its actually the former point

Another way to look Ques C:

If largest in present array is at position 1 or smallest is at position n, then it is not possible.

The final logic might be same but this one is easy to visualise or interpret. If you have smallest element at the rightmost spot or largest at leftmost spot you can never get they final array

Now largest is n and smallest is 1, start from either largest and smallest and check above condition.

I did C in different way:

for(int i=0;i<n-1;i++)
       {
           sum=sum+(a[i+1]-a[i]);
       }
       if(sum<0)
       cout<<"NO\n";
       else
       cout<<"YES\n";

Anyone else who used this logic??

what is the significance of this line in question B:"exactly k of its neighboring cells have a number greater than 0 written on them."

keep make like this announcements

they keep Cowards away

Well, I see that those testers comment were not lying, tho

A crazy $$$\textbf{D&C}$$$ solution for A :

#include <bits/stdc++.h>

using namespace std;

#define fios        ios::sync_with_stdio(false), cin.tie(), cout.tie();
#define fr          first
#define sc          second
#define all(v)      v.begin(), v.end()
#define scan(a, n)  for(int i = 0; i < n; i++)cin >> a[i];
#define print(a, n) for(int i = 0; i < n; i++)cout << a[i] << ' '; cout << '\n';

typedef long long ll;
typedef pair<int, int> pt;

const int MN = 3e5+7;

int a[MN], n;

void inp(){
    cin >> n;
    scan(a, n);
}

int f(int l, int r){
    if(l == r)return 0;
    int sw = 1, ssw = 1;
    for(int i = l+1; i <= r; i++)if(a[i] < a[i-1])sw = 0;
    for(int i = l+1; i <= r; i++)if(a[i] > a[i-1])ssw = 0;

    if(sw == 1 || ssw == 1){
        for(int i = l; i <= r; i+=2)a[i] = -a[i];
        return ((r-l)&1);
    }

    int ii = -3;
    for(int i = l+1; i < r; i++){
        if(a[i] >= a[i-1] && a[i] >= a[i+1]){
            ii = i;
            break;
        }
    }
    if(ii == -3){
        for(int i = l; i <= r; i+=2)a[i] = -a[i];
        return ((r-l)&1);
    }
    int le = f(l, ii-1), re = f(ii+1, r);

    if(abs(le+re) > 1){
        for(int i = l; i < ii; i++)a[i] = -a[i];
        return 0;
    }
    return le+re;
}

void slv(){
    for(int i = 0; i < n; i++)a[i] = abs(a[i]);
    f(0, n-1);
    print(a, n);
}

signed main()
{
    int t = 1;
    cin >> t;
    while(t--){
        inp();
        slv();
    }
    return 0;
}
 

Thanks for such a wonderful contest! Thank_u

drunk coordinator

Thanks anthoctryhardO_o for this beautiful round!!

Welcome to the new era of AdHocForces

https://codeforces.me/contest/1375/submission/86002430 I am not able to get where is my logic is going wrong for problem C? Logic: I have stored the first element of every increasing continuous sub-array(as it will be replaced by it only, when we will apply operations) in list(say A), except last element of array and then check whether any element greater then last element in list A, if no then ans is YES, otherwise NO. Please help anyone! Thank you.

For problem C, I used stack, in which if a smaller element is there I will not push a larger element and is a smaller element comes I push it and try to empty the stack using larger number coming.. Can anyone tell where it fails..... my code..85979051

Typical adamant problem)

Hi guys, As a beginner i faces a lot of problems understanding solution of problems I always taught that can there be some creative way of easily explaining solution, then i realizes the best was is by visual explanation

so i have prepared visual explanation and solution of problem A,B,C as i was able to get them under control

Links: -

Problem A

Problem B

Problem C

I have just started with this i hope it will be helpful to lot of beginners and i will also improve my explanation skills as we proceed in this new Journey

Hope it helps :) :) Waiting for valuable feedback :) :)

Wow I got tricked on G :(

I didn't think G was that easy (in fact I thought of this solution 30 secs after I read it), but then instead thought of some crazy DP, and then gave up and didn't really try it...

These days I dream of codeforces' contest with problems based on algorithms and data structures. DREAMS.

How to solve D for minimum number of operations?

Your text to link here...

can anyone tell me why it is not accepting

Appreciate the hard work that goes into making a problem. But it would be really great to see more problems related to data structures and algorithms. Now we can mostly find ad-hoc or else greedy problems. Most people solve upto C or D and it would be really interesting to have DSA problems in this range too. I hope you guys agree with this and relevant people can see this comment so we can see a change in future contests. I am sorry if my comment is inappropriate.

Here is my approach for Problem C(using stack) : https://youtu.be/xOFkewgFhjA

Let me know if you find this helpful :)

I have not seen someone printing the matrix for B here, so this is how it looks like

2 3 3 3 3 2
3 4 4 4 4 3
2 3 3 3 3 2

If any part of the input matrix is larger than the above matrix, the result is "NO".

problem C, sum of differences of all consecutive numbers in the array equals (a[n]-a[1]).

[problem:C] 85966335

Can anyone believe todays problem C was just one if-else!!! :D

if(a[0]<a[n-1]) cout << "YES\n"; else cout << "NO\n"; The fuck!!

These days there is a trend of Adhoc problems on codeforces.

Here's another (almost equivalent) solution for C.

It is easy to see that $$$a_1<a_n$$$ is a necessary condition. If $$$a_1>a_n$$$, no matter what we do, for the last two elements (let them be $$$a_i$$$ and $$$a_j$$$), we must have $$$a_1 \leq a_i$$$ and $$$a_j \leq a_n$$$, so $$$a_i>a_j$$$, which is not reducable. To prove its sufficiency, I devised the following algorithm :-

Take the smallest element in the permutation. Obviously, it will be $$$1$$$ initially. Let its position in the array be $$$i$$$ (note that it cannot be $$$n$$$ because then $$$a_1<a_n$$$ would not hold). I will use this element to delete every element to the right of $$$i$$$ except $$$a_n$$$. I can do this because by definition $$$a_i$$$ is the smallest so $$$a_i<a_{i+1}$$$ will always hold. Now my array is $$$a_1, a_2,... , a_{i-1}, a_i, a_n$$$. Here I will use $$$a_i<a_n$$$ to delete $$$a_i$$$. So, my array is $$$a_1, a_2,... , a_{i-1}, a_n$$$. Repeat this process until a single element remains.

Can anyone please tell me why this approach is wrong or if the code is wrong. Please tell me I have no clue whatsoever regarding why I am passing the Test Case 1 and not 2. https://codeforces.me/contest/1375/submission/85968254 is the solution link.

85986603

I am curious about the correctness of my submission in problem D

My approach is to eliminate those duplicate numbers from left to right, then to apply the algorithm introduced in the editorial, this is, to say that "the number of duplicated numbers" $$$+$$$ "the number of cycles" — "number of fixed points" $$$\leq n$$$

The approach might sound ridiculous at first glance, but I can't find any counter case. Even more surprisingly( or obviously?), there are a lot of cases that my algorithm needs exactly $$$2n$$$ operations.

For example, any $$$a_1, ..., a_n$$$ has the form $$$a_1 = a_2 = ... = a_n = n - 1$$$ will achieve the equality, and this is not the only case the equality holds.

For instance, consider the following case where $$$n = 7$$$,

$$$6, 4, 5, 5, 4, 6, 6 \Rightarrow 6, 4, 5, 0, 1, 2, 3$$$ has $$$3$$$ cycles and $$$4$$$ repeated numbers.

So, the problem is, is there any proof about this amazing fact? Or this is just simply wrong.

I have never ever seen a problem set like this.

When I saw the tester comments I thought they were joking but now I know they weren't （

Question are really tricky. Even I did not able to solve a single Problem in first hour of contest. And thinking lot about problem I solved first four problems until the end of contest. The logics to solce problems are really tricky and unique logic.

A simpler explanation for problem E: We need to apply all inversion swaps, so we must keep other inversions when swap a pair. We can achieve this by swapping the pair whose corresponding array elements have smallest difference.

How to effectively find the pair? See tourist's submission: 85960652. In this submisison, it first squeezes array values to 0..n-1, then only swaps the pair whose corresponding difference is 1. Such pair always exists.

Question number D can be solved in O(n). We can calculate the mex of the arr in the beginning only and try to place 0 to n-1 elements from left to right of the array and also store the frequency of every number from 1 to n. Then by using logic that which element you are replacing then you will be having two choices that the number you replaced was smaller than the previous mex or grater than the previous mex. If the number you replaced was lesser than current mex and its frequency was 1 then definitely new mex will be replaced number. In this way we have to travel the whole array once only for calculating mex. I have not solved it though

For Div2D, I thought of a different approach which sounds logically correct to me, but it gives WA on tc2. Here is the submission 86000887. If someone could give a test case where this fails that would be helpful.

Algorithm Description: - 1) make all elements unique. This can be done by performing the MEX of the first n-1 elements, taking n-1 operations. - 2) make the last element equal to n. If there is an element already equal to n, perform MEX at that index, and then perform MEX on the last index. If there is no element equal to n, perform MEX on the last index. This guarantees that the elements are unique and the last element is equal to n in at most n+1 operations. - 3) Note we have n-1 spots but n numbers to choose from (0 to n-1 inclusive) since the last element has already been fixed. Therefore, at least one number between 0 to n-1 will be excluded from the array. Let us try all possibilities of exclusion. Suppose we are excluding the element 2 from our array. Then, our array needs to look like: 0 1 3 4 ... n. We will find the MEX of the current array, which must be somewhere between 0 and n-1 inclusive. The MEX will fill the corresponding index from the array above, indexing the array from 0 but decrementing the index if MEX is > 2. If MEX is exactly 2, then we will stop the simulation early and check for validity. Otherwise, we perform n-1 operations and then check for validity, for a total of 2n operations. I claim that some exclusion iteration will always produce a valid answer.

how the author directly arrives at the conclusion that above algorithm will take at most 1.5n operations. Can someone elaborate?

Another approach for G:

We can have only one node as the centre node in the star graph. Let's find for each vertex the minimum cost of building the star graph if it was the centre node.

Let's initially root the tree at node $$$1$$$ and define $$$dp[u]$$$ the minimum cost to convert the subtree of node $$$u$$$ to star graph. Therefore, $$$dp[u]$$$ can be calculated as:

here $c[u]$ denotes children of node $$$u$$$ and $$$c[c[u]]$$$ means grandchildren of node $$$u$$$. Now, $$$dp[1]$$$ stores the minimum cost of building a star graph for node $$$1$$$. Now, we can simply do a dfs on the tree and on the go update the $$$dp$$$ values of the adjacent nodes.

Submission

Is there any way to recompute MEX in less than O(n) time?? Problem D.

can someone explain the problem E editorial using examples say 3,2,2 ? .According to the editorial we swap (1,3) thus we get 2,2,3 .$$$a_1>a_2$$$ but $$$b_1=b_2$$$ .

How to generally approach a problem like C as there were some key observations needed and to prove that the observation work requires a lot of time. I usually get lost in a dead-end in such type of problems.

For G, would the solution still be the same if in each operation we only delete the edge connecting a and b and add the edge connecting a and c?

https://codeforces.me/contest/1375/submission/86033992 Getting runtime error, don't know why!

Video for D: Replace MEX

Can someone explain or give an idea on how to solve the problem E Inversion Swapsort? I don't quite understand the editorial above.

Looking forward to AC4

I thought the tutorial's method to D in the contest, but it wasnt enough.

I didnt konw what to do if the mex is exactly n. So, I just went to the other way and deviated futher from the right method lol.

And now I konw that if the mex in n, we can just change any unfixed point, what a nice and meaningful way to handle it! And also learn how to find the mex in $$$log(n)$$$ time, nice round!

antontrygubO_o Could you explain general way how to aproach problems like F? How did you come up with the solution?

can someone explain why a simple bubble sort for problem E is wrong answer? it will give u,v with au>av.

For problem E,could anyboy tell me why it's wrong when I just simple swap the biggest number each time .86083757

I should read F and G first Hmmmmm :((

Problem H segment tree details:

The basic idea is that instead of splitting the nodes by index ranges, we split the nodes by the array value ranges. This allows us to merge child node results with a single operation.

The values stored in each node of the segment tree are the indices whose array values are within some range $$$[lb, rb]$$$ and the map of subset IDs for each possible subsequence of the stored indices. These subsequences can be represented as a pair consisting of the leftmost index and rightmost index of the subsequence. For example, with array $$$3,7,1,5,2,4,6$$$ and range $$$[4,7]$$$, the node stores indices $$$2,4,6,7$$$. One possible subsequence pair would be $$$(4, 7)$$$ representing index sequence $$$4,6,7$$$ and subsequence $$$5,4,6$$$ in the array.

When querying on the range $$$[l_i, r_i]$$$ for a some node, we first get the longest subsequence that is within the range. This can be done using lower_bound() and upper_bound() on the stored indices. Then, if that subsequence already has a subset ID registered in the map, we return it. Otherwise, we query the left and right nodes without shrinking the $$$[l_i, r_i]$$$ range (since the nodes are split by array values).

If we were successfully able to get a subset ID from both the left and right nodes, we merge the two into a new subset. This is possible because all the left node array values are less than the right node array values. Once merged, we register the new subset ID in the node's subsequence map. If we only get one subset ID from either the left or right node, we register that instead.

Overall time complexity: $$$O(n \sqrt{q} \log n)$$$ (see proof in the replies)

My submission