CPMagical CP Library

Problem solution · Python

CCC 2011 J5 - Unfriend

CCC 2011 J5 - Unfriend: a Python solution using sliding window or two pointers. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Sliding window or two pointers
Source
CCCSolutions
Length
68 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Sliding window or two pointers

For CCC 2011 J5 - Unfriend, the implementation maintains a moving interval and updates only the information that enters or leaves the window.

  1. Choose the invariant that makes a window valid or useful.
  2. Advance the right boundary and add the new element.
  3. Move the left boundary only as needed while maintaining the invariant and updating the answer.

Code notes

  • 68 lines of Python from the credited upstream file ccc11j5.py.
  • The implementation visibly relies on sequence storage.
  • No explicit loop blocks detected.

Complexity

Confirm that neither pointer moves backwards; if so, the scan is usually linear apart from the window’s data-structure operations.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2011 J5 - Unfriend · PythonPython
Use this to learn the idea, then write your own version.
# CCC 2011 Junior 5: Unfriend# written by C. Robart# March 2011 # this is a process of determining which sets are possible# to remove. Each set can be considered an integer. Since max N = 6,# the max number is 12345. (Or for n = 4 the max = 123)# Each number from 0 to the max will be considered:#  - all numbers with digits >= N are discarded.  (eg 57)#  - all numbers with digits which do not INCREASE are discarded (eg 223)#  - all numbers which do not contain the number of a person invited#    by a person who is in the number is discarded.#        (eg if 3 invited 1, then 23 is discarded)##  A count of all the numbers remaining is the answer.  # this chacks a given number i to ensure that it# has no digits equal or greater than N and the digits# all increase in value left to rightdef goodNumber(N, x):    last = N    ok = True    while x > 0 and ok:        digit = x % 10        ok = digit < last        last = digit        x = x // 10    return ok # this checks that all the digits of a number i# are related thru list l. For example if 4 invites 2, then any number# with a 4 digit must also have a 2 digit.def goodCombo(N,x,l):     # build the list of the digitis of x    digits = []    while x > 0:        digits.append(x % 10)        x = x // 10     # for each digit of x, see if it "invited" anyone,    # if so, that invitee must be in the list of digits.    for d in digits:        for x in range(0,N-1):            if d == l[x]:                if (x+1) not in digits:                    return False    return True # input the infoN = input()l = []for i in range(1,N):    l.append(input()) # count the valid numbers (or sets)max = eval("12345"[0:N-1])count = 1for i in range(1, max+1):    if goodNumber(N, i) and goodCombo(N, i, l):        count = count + 1print count

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗