FIRSTGEO - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a certain set of directions you can move in (some subset of up/down/left/right).
Starting at (0, 0), how many points (x, y) can you reach, such that -10 \leq x, y \leq 10?

EXPLANATION:

There are a couple of different ways to solve this problem.

Solution 1 (Simulation)

The solution that likely needs the least amount of thinking (but requires some implementation) is to just simulate moving and try to reach every possible point you can.
That is, let S denote the set of points you can reach. Initially, S = \{(0, 0)\} contains only the starting point.
Then, repeat:

  • For every point in S and direction you can possibly move in, try to move in that direction (as long as you remain within the [-10, 10]\times [-10, 10] region, of course.)
  • Add all newly visited points to S.
  • Stop the process when new points aren’t added.

This explicitly computes every point that can be visited, so in the end you can just print the size of S.
Since there are at most 441 points that can be visited at all (everything in [-10, 10]\times [-10, 10]), this process is fast enough.

Solution 2 (Casework)

An alternate solution that needs far less skill with implementation, but instead needs a bit of thinking, is to simply decide the answer based on the form of S.

Let’s look at the different forms S can have.

  • If S contains only a single 1, you can only move in a single direction. That means you can only reach 11 cells - for example, if moving right, the reachable cells are (0, 0), (1, 0), (2, 0), \ldots, (10, 0).
  • If S contains 4 ones, you can move in any direction. This allows you to reach any cell in the region, and there are 21\times 21 = 441 of them.
  • If S contains 3 ones, you have free movement either vertically or horizontally, and only one direction of movement in the other dimension.
    Here, you can see that you can visit about half the points.
    • For example, if you can move up/down/right, then you can visit every point (x, y) such that x\geq 0 and -10 \leq y \leq 10.
    • A total of 11\times 21 points can be visited.
  • If S contains 2 ones, there are two further cases:
    • Both allowed movements are in the same dimension, i.e up/down or left/right.
      In this case, 21 points can be visited.
    • Allowed movements are in different directions, like right/up.
      In this case, you can visit one entire quadrant of points, which gives a total of 11\times 11 = 121.

This covers all the cases, so the answer can be computed in constant time.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python, simulation) 
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(int(input())):
    s = input()
    reach = set()
    moves = []
    for i in range(4):
        if s[i] == '1': moves.append(dirs[i])
    
    reach.add((0, 0))
    while True:
        newpts = set()
        for x, y in reach:
            for dx, dy in moves:
                if -10 <= x+dx <= 10 and -10 <= y+dy <= 10 and (x+dx, y+dy) not in reach:
                    newpts.add((x+dx, y+dy))
        if len(newpts) == 0: break
        for x in newpts: reach.add(x)
    print(len(reach))
Editorialist's code (Python, formula) 
for _ in range(int(input())):
    s = input()
    ones = s.count('1')
    if ones == 1: print(11)
    elif ones == 3: print(231)
    elif ones == 4: print(441)
    else:
        if s[0] == s[1]: print(21)
        else: print(121)