USACO 2018 Open Contest Silver, Problem 1.
Difference between en1 and en2, changed 72 character(s)
Hello everyone, ↵

Since yesterday I have been reading the above stated problem but am not still able to come up with a solution, I have seen the editorial but i don't understand the proof for the algorithm.↵

LINK TO PROBLEM: [http://usaco.org/index.php?page=viewproblem2&cpid=834](http://usaco.org/index.php?page=viewproblem2&cpid=834)↵

EDITORIAL: http://usaco.org/current/data/sol_sort_silver_open18.html↵


**PROBLEM STATEMENT**↵

Keeping an eye on long term career possibilities beyond the farm, Bessie the cow has started learning algorithms from various on-line coding websites.↵
Her favorite algorithm thus far is "bubble sort". Here is Bessie's implementation, in cow-code, for sorting an array A of length N.↵


~~~~~↵
sorted = false↵
while (not sorted):↵
   sorted = true↵
   moo↵
   for i = 0 to N-2:↵
      if A[i+1] < A[i]:↵
         swap A[i], A[i+1]↵
         sorted = false↵
~~~~~↵


Apparently, the "moo" command in cow-code does nothing more than print out "moo". Strangely, Bessie seems to insist on including it at various points in her code.↵


Given an input array, please predict how many times "moo" will be printed by Bessie's code.↵

**N<=100,000, each element being an integer in the range 0…10^9. Input elements are not guaranteed to be distinct.**↵



Please help me find an easier to understand solution to the problem, Thanks.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English algo3rythm 2019-06-25 14:11:34 72
en1 English algo3rythm 2019-06-25 14:00:36 1345 Initial revision (published)