redsexx's blog

whats wrong with my logic?
By redsexx, history, 6 weeks ago, In English

https://mirror.codeforces.com/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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

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 

1
4
3 2 1 4
→ Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

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 :

if(vihh[i].back()>=minnele)

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.

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/2171/submission/365532494

    → Reply
    • »
      »
      »
      6 weeks ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +1 Vote: I do not like it

      By only connecting the pref[i] to suffix[i+1],you run the risk of generating the exact same edge multiple times across different block boundaries.Since you use a used map 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]:

      • Your blocks are : [2,10],[3,4],[1,5]
      • pref array:[2,2,1]
      • suffix array:[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.

      → Reply
    • »
      »
      »
      6 weeks ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      I just solved this problem for you.Take a look.

      https://mirror.codeforces.com/contest/2171/submission/365554006

      → Reply