Preparing algo competition

frequent question types

• Implementation
  • Parsing
  • Hashing
  • Sort
  • Simulation
  • String / RE (Regular Expression)
  • Bitmasking
  • Set / Map by tree or hash
• Search
  • Graph
  • DFS / BFS
  • Full search (Backtrack)
  • MST
• Data structure
  • Stack
  • Queue
  • Deque
  • Heap
  • Tree
• Algorithm
  • Greedy
  • DP
  • Binary search
  • Dijkstra
  • Union Find
• Mathematics
  • Prime numbers
  • Euclidean
  • Geometry
  • Number theory
  • Linear Algebra

Figuring out what algo should be used and which standard library to use

Depending on input number N, We have to figure out complexity to select correct methods that will satisfy time and memory limit.
Python calculates about 20,000,000 per sec.
2^10 ~ 1000 : OK
2^20 ~ 1M : OK 2^30 ~ 10 Billion (1,000,000,000) : TLE

• If time limit : < 1 sec.
  • N = 500 : Can use O(N^3)
  • N = 2000 : Can use O(N^2)
  • N = 100,000 : Use O(N log N)
  • N = 10,000,000 : Must use O(N)

• Remember Standard library functions’ complexity and make use of it.
  Check out complexities for iterable functions in Python

• checking time consumption in Python

  import time
  st = time.time()
  process()
  print(time.time() - st)
  

Languages

• C++: Better for recursion, data structure
• Python: Better for string, sort, parsing

Error Types

• CE: Compile Error –> Correct grammer error 문법오류
• TLE: Time Limit Exceeded –> Need optimization 시간초과 (최적화 필요)
• MLE: Memory Limit Exceeded –> Need optimization 메모리 초과 (최적화 필요)
• RE: Runtime Error 과정 오류
  1. div by 0
  2. index out of bound
  3. inf loop (TLE)
• WA: Wrong Answer 틀림
  1. limit and up/down check 제한 및 대소관계 (이상이하초과미만 minmax)
  2. Exception handling 예외처리 (예: 단, 없는경우 -1 출력)
  3. Input / output (공백, 양식 ,순서, 정렬유무)
  4. TLE / MLE 시간제한 / 메모리제한
  5. Correct algorithm? 알고리즘 맞는가?
  6. Is this the logic I thought of? 내가 생각한 로직대로 구현했나?
  7. Unnecessary loop? 불필요한 반복문 있나?
  8. Duplciation handle 중복처리

VS Code setup

Most of free online IDE such as repl.it are generally open to public. This means that your solutions can be caught as cheating in competetion. (Paid account may have private sessions). Therefore, I will use VS Code for solving problems.
In Windows, I/O redirection is not supported. Install WSL2(Windows Subsystem for Linux 2) for I/O redirection support in VS Code. Linux and Mac does not need any optional action.

1. Install Python extension.
2. In VS Code, press cntl + p or cmd + p and search for launch.json and add args line for I/O redirection.
   launch.json:

   "version": "0.2.0",
    "configurations": [
        {
            "name": "Python: Current File",
            "type": "python",
            "request": "launch",
            "program": "${file}",
            "console": "integratedTerminal",
            "args": ["<", "in.txt", ">", "out.txt"]
        }
    ]
   

   Now I/O redirection is activated for your VS Code system.

3. Create input.txt and output.txt. Open both files and locate them as shown in the picture. This will allow you to check the output immediately.