Project SEKAI CTF 2023 - Wiki Game

Description

Category: PPC

Welcome to Project SEKAI Online Judge!

Author: sahuang

http://algo-server.chals.sekai.team

Downloads:

• Wiki_Game.pdf
• 1.in

Resolution

1. Overview

This is a Professional Programming and Coding challenge and here we need to determine if it exists a path of length lower than 6 in a Unweighted directed graphs¹.

2. Shortest path algorithm²

My first idea was to use Breadth-first search algorithm and checks if the length of the path. However this algorithm doesn’t work in a directed graph.

So I decided to use Dijkstra’s algorithm which works for directed graph by setting a weight 1 for each edge.

I use the implementation of econchick which worked perfectly with graph which contains loops whereas other ones didn’t work (cf Dijkstra with Parallel edges and self-loop).

## https://gist.github.com/econchick/4666413
from collections import defaultdict

class Graph:
  def __init__(self):
    self.nodes = set()
    self.edges = defaultdict(list)
    self.distances = {}

  def add_node(self, value):
    self.nodes.add(value)

  def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.distances[(from_node, to_node)] = distance


def dijsktra(graph, initial):
  visited = {initial: 0}
  path = {}

  nodes = set(graph.nodes)

  while nodes:
    min_node = None
    for node in nodes:
      if node in visited:
        if min_node is None:
          min_node = node
        elif visited[node] < visited[min_node]:
          min_node = node

    if min_node is None:
      break

    nodes.remove(min_node)
    current_weight = visited[min_node]

    for edge in graph.edges[min_node]:
      weight = current_weight + graph.distances[(min_node, edge)]
      if edge not in visited or weight < visited[edge]:
        visited[edge] = weight
        path[edge] = min_node

  return visited

3. Handle input/output

The only thing left to do is parsing the input and solve it:

## Read data
data = []
while True:
    try:
        line = input()
    except EOFError:
        break
    data.append(line)

def get_ints(l):
    a, b = data[l].strip().split(" ")
    return int(a), int(b)

cases = []
T = int(data[0])

l = 1
while l < len(data)-1:
    n, m = get_ints(l)
    g = Graph()
    for i in range(l+1, l+m+1):
        u, v = get_ints(i)
        g.add_node(u)
        g.add_node(v)
        g.add_edge(u, v, 1)

    cases.append((g, get_ints(l+m+1)))

    l += m + 2

assert len(cases) == T

## Solve
def solve(case):
    g = case[0]
    src, dst = case[1]


    if dijsktra(g, src).get(dst, float('inf')) <= 6:
        print("YES")
    else:
        print("NO")

for case in cases:
    solve(case)

We submit the code to the algo server and after passing all the tests, we get the flag: SEKAI{hyp3rL1nk_cha115_4r3_EZ}.

Additional resources

1. Unweighted directed graphs - University of Minnesota ↩

2. Shortest path problem - Wikipedia ↩