# Posts published in “Simulation”

Problem:

https://leetcode.com/problems/teemo-attacking/description/

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.
This poisoned status will last 2 seconds until the end of time point 2.
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.
So you finally need to output 4.


Example 2:

Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.
This poisoned status will last 2 seconds until the end of time point 2.
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.
So you finally need to output 3.


Note:

1. You may assume the length of given time series array won’t exceed 10000.
2. You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

Idea: Running Process

Compare the current attack time with the last one, if span is more than duration, add duration to total, otherwise add (curr – last).

C++

Java

Python3

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ""X", and "O".  The ” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (” “).
• The first player always places “X” characters, while the second player always places “O” characters.
• “X” and “O” characters are always placed into empty squares, never filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Note:

• board is a length-3 array of strings, where each string board[i] has length 3.
• Each board[i][j] is a character in the set {" ", "X", "O"}.

Idea: Verify all rules

C++

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Note:

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won’t start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

Solution: Simulate using stack

Problem:

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

• If the droplet would eventually fall by moving left, then move left.
• Otherwise, if the droplet would eventually fall by moving right, then move right.
• Otherwise, rise at it’s current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.

We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.

Idea:

# Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

# Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

## Example 1:

Input: grid =
[[0,1,0,0,0,0,0,1],
[0,1,0,0,0,0,0,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
[0,1,0,0,0,0,1,1],
[0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.


## Example 2:

Input: grid =
[[1,1,1],
[1,0,1],
[1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.


## Example 3:

Input: grid =
[[1,1,1,0,0,0,0,0,0],
[1,0,1,0,1,1,1,1,1],
[1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.


## Note:

1. The number of rows and columns of grid will each be in the range [1, 50].
2. Each grid[i][j] will be either 0 or 1.
3. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

# Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

# Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)