https://codeforces.me/contest/2171/submission/365464004
My idea is simple. Divide the array into maximal strictly increasing subarrays.
Inside each subarray, connect adjacent elements with undirected edges.
For every subarray i starting from the second one, connect the last element of that subarray to the minimum element that appeared before it (I maintain a running minimum from previous parts).
After building the graph, I run DFS to check if the graph becomes connected.
If it is connected, I print "yes" and output the tree.
My code builds the graph exactly like this, but it gives wrong answers on some test.
So I want to know:
Is the logic itself incorrect, or is there likely an implementation mistake?
If the logic is wrong, where exactly does this idea fail?
Any hints would help.
Would permutation 3 2 1 4 be a counter example? I didn’t run your code but the increasing sub arrays are 3; 2; 1 4 and you will connect only the last two. Although solution exists: it’s the star graph with center 4
UPD I run the code and indeed it produces "no" for the test
Your code assume that if a subarray cannot connect to the running minimum of the elements before it,then the graph must be permanently disconnected. By adding at most 1 backward edge per subarray :
you are essentially building a straight chain of components.The problem is that a future subarray with a large element can act as a bridge to connect multiple previously disconnected components.
A counterexample I can think of:
p = [4,5,1,3,2,6]Your code will give output no when it should be yes.You're on the right track,just the wrong train.
ok, so I did this now: I calculated the prefix minimums for the vector of vectors, then the suffix maximums, and then I just connected the i-th prefix to the (i+1)-th suffix. But I'm still getting it wrong, bro. It's actually frustrating that I cannot break the 1600 barrier. Please help me if you can.
https://codeforces.me/contest/2171/submission/365532494
By only connecting the
pref[i]tosuffix[i+1],you run the risk of generating the exact same edge multiple times across different block boundaries.Since you use ausedmap to prevent duplicate edges,you end up adding nothing for that boundary,leaving the middle block completely stranded.For
p=[2,10,3,4,1,5]:[2,10],[3,4],[1,5]prefarray:[2,2,1]suffixarray:[10,5,5]Now look at your connection loop:i=0:u=pref[0]=2,vv=suffix[1]=5.It adds the edge 2-5.i=1:u=pref[1]=2,vv=suffix[2]=5.It tries to add 2-5 again.Because of your used map,your second attempt is ignored. Your code outputs No when it should be Yes.
I just solved this problem for you.Take a look.
https://codeforces.me/contest/2171/submission/365554006