Game Theory in Competitive Programming
Game Theory in Competitive Programming Series: Part 1
Part 1 of Game Theory in CP — Mezo Playing Zoma (Codeforces)
Welcome to Game Theory in CP — Part 1.
This series will consist of questions and tutorials of Competitive Programming which involve Game Theory. The series will kick off with a very basic question and raise the level moving forward. The link to the question for this part is given below. A brief explanation is provided as well.
Problem
Link to Problem — https://codeforces.com/contest/1285/problem/A
Mezo is playing a game. In the game, Zoma is a character who is initially standing in a long corridor at position x = 0. Mezo can send two types of commands to Zoma which are ‘L’ and ‘R’ using his controller.
The commands result in the following actions:
- ‘L’: Zoma moves 1 step to the left such that its position changes from x to x - 1.
- ‘R’: Zoma moves 1 step to the right such that its position changes from x to x + 1.
Unfortunately Mezo’s controller is malfunctioning. Some commands are sent properly and some are ignored.
For example, if Mezo sends commands “LRLR”, then here are some possible outcomes (bold and italic commands are sent successfully):
- “LRLR” — Zoma moves to the left, to the right, to the left again and to the right for the final time, ending up at position 0;
- “LRLR” — Zoma receives no commands, doesn’t move at all and ends up at position 0 as well;
- “LRLR” — Zoma moves to the left, then to the left again and ends up in position −2;
Mezo doesn’t know which commands will be sent successfully beforehand. Thus, he wants to know how many different positions may Zoma end up at.
Input
The first line contains N (1 ≤ N ≤ 10⁵) — the number of commands Mezo sends.
The second line contains a string S of N commands, each either ‘L’ (Left) or ‘R’ (Right).
Output
Print one integer — the number of different positions Zoma may end up at.
Give a try to solve the problem and read further for a hint.
Hint for solving the problem:
Think in terms of minimum and maximum positions that Zoma may end up at. Try to solve it again and then come back for the solution.
Read further for the solution and code in C++.
We have N: the number of commands and S: the string of commands.
Let X be the position Zoma ends up at if all commands are sent and A and B be the number of ‘L’ and ‘R’ commands in S, respectively.
⇒ B - A = X
⇒ A + B = N
(Note that the order of commands doesn’t affect X)
The maximum position Zoma can end up at will be when all ‘L’ commands are ignored.
This position will be equal to X + A. (MAX = X + A)
Similarly, the minimum position will be when all the ‘R’ commands are ignored, it will be equal to X - B. (MIN = X - B)
Now, canceling any number of commands from S will result in a position that is between these values inclusive of MAX and MIN.
The total number of possible positions will be equal to MAX - MIN + 1.
⇒ (X + A) - (X - B) + 1
⇒ X + A - X + B + 1
⇒ A + B + 1
⇒ N + 1
As it turns out, the final answer depends only on the number of commands.
C++ implementation for this problem is given below.
#include <iostream>
#include <string>int main(){long N; // The number of commands Mezo sends.std::cin >> N; // Taking input : Nstd::string S; // The string consisting of commandsstd::cin >> S; // Taking input : Sstd::cout << N+1; // Writing the answer to the output/* As shown, the total number of possible outcomes forN commands is N+1 */return 0;}
That’s all for today! Stay tuned for Part 2 of Game Theory in CP.
