title: Proof of Correctness of Codeforces Problem: Boxers (rated 1500)
body: <p>Consider  this problem appearing in Codeforces (rated 1500):</p>
  
  <blockquote>
    <p>There are n boxers, the weight of the i-th boxer is ai. Each of them can change the weight by no more than 1 before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.</p>
    
    <p>It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers' weights in the team are different (i.e. unique).</p>
    
    <p>Write a program that for given current values ​ai will find the maximum possible number of boxers in a team.</p>
    
    <p>It is possible that after some change the weight of some boxer is 150001 (but no more).</p>
    
    <p><strong>Input</strong>
    :The first line contains an integer n (1≤n≤150000) — the number of boxers. The next line contains n integers a1,a2,…,an, where ai (1≤ai≤150000) is the weight of the i-th boxer.</p>
    
    <p><strong>Output</strong>
    :Print a single integer — the maximum possible number of people in a team.</p>
  </blockquote>
  
  <p>Here is the code I implemented which was accepted by the Codeforces as a correct submission (Python 3.7):</p>
  
  <pre class="lang-py prettyprint-override"><code>n=int(input())
  inputlist=list(map(int, input().split()))
  inputlist.sort()
  boxerset=set()
  for i in inputlist:
      if i-1 not in boxerset and i!=1:
          boxerset.add(i-1)
      elif i not in boxerset:
          boxerset.add(i)
      elif i+1 not in boxerset:
          boxerset.add(i+1)
      else:
          continue
  print(len(boxerset))
  </code></pre>
  
  <p>However, I am not able to rigorously prove that this algorithm necessarily give the correct answer. For example, when inputlist is [1, 1, 1, 2, 2, 5 , 8], both [1, 2, 3, 4, 7, 8](my algorithm) and [1, 2, 3, 6, 7, 8] is the correct output boxerset, although the answer for both the cases comes out to be 6. </p>
  
  <p>My question is this: </p>
  
  <p><strong>How can I prove my algorithm is correct? How will my proof work to show that out of all possible legal selections of boxers, the selection by my algorithm has the maximum amount of boxers (that is how do I show that my there exists no other selection for which the number of boxers can be greater than the selection done by my algorithm)?</strong></p>
  
  <p>I have tried proof by contradiction but to no avail (although I think the proof has to have the natural structure of a proof by contradiction).</p>
  
  <p><a href="https://codeforces.com/problemset/problem/1203/E" rel="nofollow noreferrer">https://codeforces.com/problemset/problem/1203/E</a></p>