1 of 29

Neuqua Valley Computing Team

Main Building D200 | Thursdays 2:35-3:30 | nvcomputing.com

Today’s Agenda:

Day 7 - More Contest 2 Topics!

Intro Problems

Lesson

HW

Discord!

Website!

2 of 29

Attendance

3 of 29

ACSL

  • PAY THE PUSHCOIN ASAP!
  • Register: https://forms.gle/WKrB7BEFHdQePYeUA

22 people completed this so far. If the number of people in attendance and the number of people registered for ACSL are different, something is WRONG.

4 of 29

WARMUP PROBLEM

  1. 2018
  2. 2040
  3. 2032
  4. 2030
  5. 2042
  6. 2048
  7. 2031

AUTOJUDGER

5 of 29

Topic 2 (Contest 2): Bit String Flicking

6 of 29

Connection to Computer Number Systems

Bit strings are strings of binary digits (0s and 1s)

We have different ways to manipulate these strings.

While it seems simple, it is useful for many things like assembly language, code optimization, and hardware design.

7 of 29

Example:

  • 00000
  • 11111
  • 0
  • 1
  • 01010101

These are all bit strings.

8 of 29

Operators

Just like math with regular numbers, we can use different operators on bit strings. They also follow an order of precedence (similar to PEMDAS).

From high priority to low priority, they are:

(HIGH) Parenthesis, NOT, SHIFT and CIRC, AND, XOR, OR (LOW)

9 of 29

NOT, AND, OR, XOR

All of these are binary operators (except NOT). �Meaning, they take in two operands of the same length.

¬ is a NOT.�& is an AND.�| is an OR.�⊕ is XOR. (This is ^ in most programming languages)

10 of 29

NOT

NOT takes an input and returns a string where every bit is the opposite. Every 1 becomes 0 and every 0 becomes 1.

NOT(00001) = 11110

NOT(1111) = 0000

11 of 29

AND, OR, XOR

Let’s say our two inputs are

10101 and 11100

AND, OR, XOR do something on each bit

1 if both are 1, otherwise is 0

1 if at least one is 1

1 only if exactly one 1 and one

12 of 29

Shift (SHIFT)

Shifts: Move all bits left/right some amount. Bits that move off the edge get chopped off and replaced with 0s.

Example: LSHIFT-2(01101)

Our string is 01101, when we shift, we get 01101__

What we have left is 101__. Let’s fill the blank with 0s.

10100

shifted off!!

13 of 29

Circle (CIRC)

Similar to shift, but instead of getting chopped off, the bits circle around.

EXAMPLE: RCIRC-2(01011)

Original

After 1st

After 2nd

0 1 0 1 1

1 0 1 1 0

0 1 1 0 1

14 of 29

15 of 29

CHALLENGE PROBLEMS

Which value of X is invalid? (submit the letter)

(RSHIFT–1 (LCIRC–2 X)) OR (NOT(RCIRC–3(LSHIFT–1 00100))) = 11110

  1. 10000
  2. 01000
  3. 01100
  4. 00001

16 of 29

17 of 29

ANSWER: 10111

18 of 29

19 of 29

ANSWER: 00010

20 of 29

Topic 3 (Contest 2): LISP

21 of 29

LISP

  • "LISt Processor”
  • Lots of S-expressions (parenthesis)
  • John McCarty is responsible if you ever struggle on a LISP problem
  • Family of programming languages
    • Current “dialects” include Modern Lisp, Scheme, Racket, Clojure
    • ACSL uses their own, sorta

22 of 29

LISP

Everything in LISP is either a list or an atom

  • A atom is just one element
    • Ex: hello, Hi
  • A list is a multiple atoms separated by a space and enclosed in ()
    • Ex: (Hello Hi Bonjour)
  • A list can contain another list within it
    • Ex: (Hello (Hi Hola) (Gutentag Bonjour))
  • NIL is the only exception → NIL = null, nothing
  • Apostrophe ‘ means DO NOT EVALUATE

23 of 29

Math Functions

Statement

Value

(ADD 2 3)

5

(SUB 4 2)

2

(MULT 2 3)

6

(DIV 4 2)

2

(SUB (ADD 2 3) (MULT 2 2))

5-4= 1

24 of 29

Math Functions Practice

(ADD (MULT 2 3) (ADD 8 9) (ADD 4 5))=

(ADD (MULT 4 6) (SUB 8 9) (ADD 6 5))=

(MULT (SUB 2 3) (DIV 9 3) (ADD 4 5))=

25 of 29

Math Functions Practice

(ADD (MULT 2 3) (ADD 8 9) (ADD 4 5))=32

(ADD (MULT 4 6) (SUB 8 9) (ADD 6 5))=34

(MULT (SUB 2 3) (DIV 9 3) (ADD 4 5))=-27

26 of 29

Understanding the Apostrophe ‘

  • the apostrophe acts similarly to double quotes in BASIC or C++; it tells you to treat what follows it as one list and not to evaluate that list
  • ex. ‘ (MULT 1 2 3 4) does not make 24, it makes the list (MULT 1 2 3 4)
  • Be careful about what the apostrophe applies to (make sure you consider everything that follows it)
  • Common pitfall →
    • ‘ ((MULT 1 2) (ADD 5 7)) ≠ ‘ (MULT 1 2) (ADD 5 7)

27 of 29

POTW - “Casino Conspiracy”

(Prefix sums!)

Thanks to Shiven, Atharva, Sandilya, Ian, April for doing last weeks POTW… Late submissions for previous problems and faulty code now earn 3 points (AKA please try, it’s also good practice for ACSL programming and USACO)

28 of 29

Homework

  • It’s LITERALLY 3 problems

  • We will notice and like you a lot if you do it

  • You will be more prepared for the ACSL contests which will be starting up sooner than later

29 of 29

Contact Information

Our Official Email - nvhscomputing@gmail.com

Steven He - stevenh7023@k12.ipsd.org

Armaan Sidhu - armaansid0712@k12.ipsd.org

Arthur Cai - arthurca3607@k12.ipsd.org

Kundan Baliga - kundanbal2969@k12.ipsd.org

CLUB INFORMATION