# iSCO June 2024 Official Tutorial
:::warning
:bulb: Please email the relevant problem writers/solvers or visit the official iSCO [Discord Server](https://discord.gg/V7Xf22Xf4F) if you have questions!
If you would like to request an edit to the tutorial, please email zkuah25@iskl.edu.my.
:::
## Table of Contents
1. Multilingual by Kaibo Ma
2. Sushi Stylist by Zhao Yang Kuah
3. Immaculate by Nobel Suhendra
4. Fizzbuzz 2 by Kaibo Ma
5. Flowers by Isabella Lin
6. Prom Date by Justin Jitra
7. Carrots by Isabella Lin
8. Arrakis by Nobel Suhendra
## Collaborator's Note
In addition to solutions in Java, Python, and C++, I've added Rust solutions that often take a different approach or utilize unique functionality of the language to simplify the solution. If you're interested in learning about different perspectives and approaches one might take on a problem, check out the Rust solutions, where I may have added some notes explaining how the solution is different from others.
\- Kaibo Ma
## A: Multilingual
[Problem Link](https://codeforces.com/gym/528561/problem/A)
Problem by Kaibo Ma (kaiboma06@gmail.com)
Tutorial by Kaibo Ma (kaiboma06@gmail.com)
Solutions by Kaibo Ma (kaiboma06@gmail.com)
### Description
The problem asks us to find the most spoken language given the different languages people speak. There are two ways to achieving this: through sorting or through using a map. We will discuss using a map.
An initial intuition for the problem would be storing the number of times we have seen someone know how to speak each of the languages, then finding the language with the largest frequency. (thus language spoken by the most people) As the identifiers for languages get as large as $10^{18}$, we cannot simply use the identifiers as indices to an array, as that would require us to store up to $10^{18}$ elements, which would take too much memory.
The solution is then to use a map. A map is a data structure that maps a key to a value. In here, the keys are the identifiers of different languages, while the values associated with the keys are the number of times we have seen the language.
Afterwards, we can iterate over all the entry within the map, and find the key whose associated value is the largest.
### Solutions
> Python Solution
:::spoiler
```python=
languages = {}
for _ in range(int(input())):
input()
for x in map(int, input().split(' ')):
languages[x] = languages.get(x, 0) + 1
print(max(languages.items(), key=lambda p: p[1])[0])
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <iostream>
#include <unordered_map>
using namespace std;
using ll = long long;
int main() {
int n; cin >> n;
unordered_map<ll, ll> m;
int max_frequency = -1;
ll max_lang;
for (int x = 0; x < n; x++) {
int langs; cin >> langs;
for (int y = 0; y < langs; y++) {
ll lang; cin >> lang;
m[lang]++;
}
}
for (auto it = m.begin(); it != m.end(); it++) {
if (it->second > max_frequency) {
max_lang = it->first;
max_frequency = it->second;
}
}
cout << max_lang;
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.Scanner;
import java.util.HashMap;
public class ml {
public static void main(String[] a) {
Scanner sc = new Scanner(System.in);
HashMap<Long, Integer> m = new HashMap<>();
int n = sc.nextInt();
for (int x = 0; x < n; x++) {
int langs = sc.nextInt();
for (int y = 0; y < langs; y++) {
long lang = sc.nextLong();
if (m.get(lang) == null) {
m.put(lang, 0);
}
m.put(lang, m.get(lang) + 1);
}
}
int maxNumSpeakers = -1;
long bestLang = 0;
for (Long language: m.keySet()) {
if (m.get(language) > maxNumSpeakers) {
bestLang = language;
maxNumSpeakers = m.get(language);
}
}
System.out.println(bestLang);
}
}
```
:::
<br/>
> **Bonus!** Rust solution
:::spoiler
```rust
use std::collections::HashMap;
use std::io::{stdin, BufRead};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut stdin = stdin().lock().lines();
let stuff = stdin.next().unwrap()?.parse::<u32>()?;
let mut langs: HashMap<String, usize> = HashMap::new();
for _ in 0..stuff {
stdin.next().unwrap()?;
for s in stdin.next().unwrap()?.split(' ') {
*langs.entry(s.to_owned()).or_default() += 1;
}
}
let v = langs.into_iter().max_by_key(|(_, x)| *x).unwrap().0;
println!("{v}");
Ok(())
}
```
:::
## B: Sushi Stylist
[Problem Link](https://codeforces.com/gym/528561/problem/B)
Problem by Zhao Yang Kuah (zkuah25@iskl.edu.my)
Tutorial by Zhao Yang Kuah (zkuah25@iskl.edu.my)
Solutions by Zhao Yang Kuah (zkuah25@iskl.edu.my)
### Description
There are two cases in which we cannot fit all sushis into the bento box:
1. **When the length of the bento box is less than the number of sushis.**
In this case, we simply output "no" if the number of sushis exceeds bento box length, disregarding forbidden combinations.
2. **The forbidden combinations cannot be spaced out with the remaining box length.**
In this case, we first find the number of forbidden combinations present in the chain of sushi. This is done by iterating through each consecutive pair of sushis in the box, counting the total occurrences of "ce", "ec", "es", "se", "st" and "ts".
:::warning
Note that combinations of chuka wakame and ebi may appear as either 'ce' and 'ec', which are both forbidden. This **reversibility** similarly applies to other forbidden combinations.
:::
In the Python solution, I checked whether an array of strings representing forbidden combinations (`forbidden = ["ce", "ec", "es", etc...]`) contains a 2-character substring of the sushi chain. In the C++/Java solutions, the same can be done using a string of space-separated forbidden combinations (`string forbidden = "ce ec es etc..."`).
It is also possible – as some of you have done – to check pairings of consecutive characters as you iterate through the sushi chain. There are many ways to go about this!
Finally, we subtract the number of sushis from the box length. This gives us the extra space we have. If the number of forbidden combinations exceeds this value, we return "no" – otherwise, we return "yes".
### Solutions
**Please read the labelled comments inside the Python solution.**
I've kept variable/function names the same between languages for consistency. Apologies to the C++/Java people who might get annoyed with my snake_case...
> Python Solution
:::spoiler
```python=
forbidden = ["ce", "ec", "es", "se", "st", "ts"]
def can_pack_sushi(length, types):
sushis = len(types)
# when the bento box is not long enough to fit all the sushi
if (length < sushis):
return "no"
# when the box is not filled/exactly filled, we can use the remaining length to space out forbidden combinations
if (num_of_forbidden(types) > length - sushis):
return "no"
else: return "yes"
def num_of_forbidden(types):
count = 0
for i in range(len(types)):
if (i > 0):
if (types[i-1:i+1] in forbidden):
count += 1
return count
# Read input
def main():
a = int(input())
for _ in range(a):
l = int(input())
t = input()
print(can_pack_sushi(l, t))
if __name__ == "__main__":
main()
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <iostream>
using namespace std;
string forbidden = "ce ec es se st ts";
int num_of_forbidden(string types)
{
int count = 0;
for (int i = 1; i < types.length(); i++)
{
if (forbidden.find(types.substr(i - 1, 2)) != string::npos)
count++;
}
return count;
}
string can_pack_sushi(int length, string types)
{
int sushis = types.length();
if (length < sushis)
{
return "no";
}
if (num_of_forbidden(types) > (length - sushis))
{
return "no";
}
else
{
return "yes";
}
}
int main()
{
int a;
int l;
string t;
cin >> a;
for (int i = 0; i < a; i++)
{
cin >> l;
cin >> t;
cout << can_pack_sushi(l, t) << endl;
}
return 0;
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.Scanner;
public class SushiStylist {
static String forbidden = "ce ec es se st ts";
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
for (int i = 0; i < a; i++) {
int l = sc.nextInt();
String t = sc.next();
System.out.println(can_pack_sushi(l, t));
}
}
static int num_of_forbidden(String types) {
int count = 0;
for (int i = 1; i < types.length(); i++) {
if (forbidden.contains(types.substring(i - 1, i + 1)))
count++;
}
return count;
}
static String can_pack_sushi(int length, String types) {
int sushis = types.length();
if (length < sushis) {
return "no";
}
if (num_of_forbidden(types) > (length - sushis)) {
return "no";
} else {
return "yes";
}
}
}
```
:::
<br/>
> **Bonus!** Rust solution
:::spoiler
The main divergence of this solution with the others is the approach to finding an answer. As it turns out, the case where the length of the bento box is less than number of sushis does not require separate handling.
The most interesting thing in this solution would be the call to `.windows(2)`. This returns all subarrays of length 2 in a sliding window, and removes our need to use `substring` ourselves.
```rust
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut l = std::io::stdin().lines();
let cases = l.next().unwrap()?.parse::<u32>()?;
let illegal = [b"ce", b"ec", b"es", b"se", b"ts", b"st"].map(|x| &x[..]);
for _ in 0..cases {
let n = l.next().unwrap()?.parse::<usize>()?;
let s = l.next().unwrap()?;
let combinations = s
.as_bytes()
.windows(2)
.filter(|w| illegal.contains(w))
.count();
let answer = ["no", "yes"][(combinations + s.len() <= n) as usize];
println!("{answer}");
}
Ok(())
}
```
:::
## C: Immaculate
[Problem Link](https://codeforces.com/gym/528561/problem/C)
Problem by Nobel Suhendra (71195@jisedu.or.id)
Tutorial by Nobel Suhendra (71195@jisedu.or.id)
Python and Java Solutions by Zhao Yang Kuah (zkuah25@iskl.edu.my)
C++ Solution by Nobel Suhendra (71195@jisedu.or.id)
### Description
It is important to note that the order of the input does not matter in the question. At the end of it, all the people at the party need to find someone else with a corresponding compatability score. It is also essential to notice that every compatability score requires a unique pairing: a person with compatability score $C$ needs to find someone with score $A-C$. The solution requires us to find the number of people who remain unpaired even after maximizing pairings.
Let M be an integer-to-integer mapping where $M_i$ represents the number of people with compatability score $i$. For every unique compatability score, we can find the difference between $M_i$ and $M_{A-i}$, adding this value to our final answer. In order to avoid double counting, the final answer needs to be divided to two.
An edge case to consider is for $i = \frac{A}{2}$. The parity of $\frac{A}{2}$ determines whether or not there is an individual with score $\frac{A}{2}$ that remains unpaired.
### Solutions
> Python Solution
:::spoiler
```python=
freq = dict()
s = set()
def getValue(key):
return freq[key] if (key in freq.keys()) else 0
n, a = map(int, input().split())
for c in map(int, input().split()):
s.add(c)
s.add(a-c)
freq[c] = getValue(c) + 1
ans = 0
for item in s:
ans += abs(getValue(item) - getValue(a-item))
print(int(ans / 2 + (0 if (a % 2 == 1) else (getValue(a/2) % 2))))
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> freq;
set<int> s;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, a; cin >> n >> a;
for (int i = 0; i < n; i++) {
int c; cin >> c;
s.insert(c);
s.insert(a-c);
freq[c]++;
}
int ans = 0;
for (auto item : s) ans += abs(freq[item] - freq[a - item]);
cout << ans/2 + (a % 2 ? 0 : (freq[a/2] % 2)) << endl;
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Immaculate {
public static void main(String[] args) {
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
Set<Integer> s = new HashSet<Integer>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
for (int i = 0; i < n; i++) {
int c = sc.nextInt();
s.add(c);
s.add(a - c);
freq.put(c, getValue(freq, c) + 1);
}
int ans = 0;
for (Integer item : s) {
ans += Math.abs(getValue(freq, item) - getValue(freq, a - item));
}
System.out.println((ans / 2 + ((a % 2 == 1) ? 0 : (getValue(freq, a / 2) % 2))));
}
public static int getValue(HashMap<Integer, Integer> map, int key) {
return map.containsKey(key) ? map.get(key) : 0;
}
}
```
:::
<br/>
> **Bonus!** Rust Solution
:::spoiler
You will notice that this solution does not divide anythign by 2. This is because of the way counting worked in this solution. When getting an extra number from the input, it either satisfies someone else's requirement for getting the correct compatibility score, subtracting that requirement by 1 (handled in `Some(1) => {}` and `Some(n) => { map.insert(x, n-1); }`) or adds a requirement as it can't find someone else to make the correct sum, in `map.entry(a - x).or_default() += 1`. The answer is then the nubmer of people with unsatisfied requirements.
```rust
use std::collections::HashMap;
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut l = std::io::stdin().lines();
let split = l.next().unwrap()?;
let mut split = split.split(' ');
let _n = split.next().unwrap().parse::<u32>()?;
let a = split.next().unwrap().parse::<u32>()?;
let mut map = HashMap::new();
for x in l.next().unwrap()?.split(' ') {
let x = x.parse::<u32>()?;
match map.remove(&x) {
None => *map.entry(a-x).or_default() += 1,
Some(1) => {}
Some(n) => { map.insert(x, n-1); }
}
}
println!("{}", map.into_values().sum::<usize>());
Ok(())
}
```
:::
## D: Fizzbuzz 2
[Problem Link](https://codeforces.com/gym/528561/problem/D)
Problem by Kaibo Ma (kaiboma06@gmail.com)
Tutorial by Kaibo Ma (kaiboma06@gmail.com)
### Description
The question asks us to find the length of the FizzBuzz sequence up to the $N$th output. $N$ can be as large as $10^{18}$, so it is infeasible to iterate over all integers from 1 to $N$ under the time limit. An intuition comes from how we can group the FizzBuzz output based on the power of ten (or number of digits) of the input.
Numbers that are multiples of $3$ appear once every three integers.
Numbers that are multiples of $5$ appear once every five integers.
Therefore, the number of integers up to $N$ that are divisible by $3$ are simply given by $\lfloor N / 3 \rfloor$ and for number of integers divisible by $5$, $\lfloor N/5 \rfloor$. (note that $\lfloor x \rfloor$ means "floor" which returns the greatest integer less than or equal to $x$ or rounding towards zero when $x$ is positive)
We can therefore find the number of characters the Fizzes and the Buzzes and the FizzBuzzes contribute to the total. It turns out this is $4 \lfloor N / 3 \rfloor + 4 \lfloor N/5 \rfloor$ since multiples of 3 and 5 contribute 4 characters and multiples of 15 contribute 8 characters.
We now consider the numbers that are not Fizzes or Buzzes or FizzBuzzes. The number of digits for a number changes, therefore we can examine the ranges 1-9, 10-99, 100-999 and so on until $N$. Let $X$ be the number of digits for a given range. We consider the number of integers that are neither multiples of 3 or 5.
Some careful counting tell us that:
* There are 3 multiples of 3, 1 multiple of 5, and 0 multiple of 15 in the range 1-9.
* There are 33 multiples of 3, 19 multiples of 5, and 6 multiples of 15 in the range 1-99.
* There are 333 multiples of 3, 199 multiples of 5, and 66 multiples of 15 in the range 1-999.
Therefore, for the range 1-9, there are 3 multiples of 3, 1 multiple of 5 and 0 multiple of 15.
For the range 10-99, there are 30 multiples of 3, 18 multiples of 5, and 6 multiples of 15.
For the range 100-999, there are 300 multiples of 3, 180 multiples of 5, and 60 multiples of 15.
With this knowledge and pattern, we can build the number of characters for numbers within a given range with $X$ digits. To prevent double counting, the number of integers that are either a multiple of 3, a multiple of 5, or both within the range is $3 \cdot 10^X + \lfloor 1.8\cdot 10^X \rfloor - \lfloor 0.6 \cdot 10^{X-1} \rfloor$, therefore, the number of characters the non-fizzbuzzers would contribute within such a range would be $X \cdot [9 \cdot 10^X - (3 \cdot 10^X + \lfloor 1.8\cdot 10^X \rfloor - \lfloor 0.6 \cdot 10^{X-1} \rfloor)]$.
The rest of the problem is then figuring out the answer in a subrange. For example, if $N = 1024$, we can compute the ranges up to 100-999, while we need to do some more careful counting with the non-fizzbuzzers in the range 1000-1024. The details of these are in the solution code.
### Solutions
Note about solutions: The tests were wrong in the actual contest, incorrectly marking answers which contained integer overflow as correct, and answers that do not have overflow as incorrect. The metric for whether a solution is actually correct is test #82. If the solution is incorrect on test #82 as reported by codeforces, your solution would be correct.
> Python Solution
:::spoiler
```python=
n = int(input())
result = (n//3 + n//5) * 4
log10 = current = 1
while current * 10 < n:
total = current * 9
by3 = current * 3
by5 = current * 18 // 10
by15 = current * 6 // 10
nonfizzbuzzers = total + by15 - by3 - by5
result += nonfizzbuzzers * log10
current *= 10
log10 += 1
prev = current - 1
total = n - prev
by3 = n//3 - prev//3
by5 = n//5 - prev//5
by15 = n//15 - prev//15
nonfizzbuzzers = total + by15 - by3 - by5
result += nonfizzbuzzers * log10
print(result)
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
int main() {
ll n; cin >> n;
ll result = 0;
result += n / 3 * 4;
result += n / 5 * 4;
ll log10 = 1;
ll current = 1;
while (current * 10 < n) {
ll total = current * 9;
ll by3 = current * 3;
ll by5 = current * 18 / 10;
ll by15 = current * 6 / 10;
ll nonfizzbuzzers = total + by15 - by3 - by5;
result += nonfizzbuzzers * log10;
current *= 10;
log10 += 1;
}
ll prev = current - 1;
ll total = n - prev;
ll by3 = n / 3 - prev / 3;
ll by5 = n / 5 - prev / 5;
ll by15 = n / 15 - prev / 15;
ll nonfizzbuzzers = total + by15 - by3 - by5;
result += nonfizzbuzzers * log10;
cout << result << endl;
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
public class fb2 {
public static void main(String[] x) {
long n = (new java.util.Scanner(System.in)).nextLong();
long result = n / 3 * 4 + n / 5 * 4;
long log10 = 1;
long current = 1;
while (current * 10 < n) {
long total = current*9, by3 = current*3;
long by5 = current*18/10, by15 = current*6/10;
long nonfizzbuzzers = total + by15 - by3 - by5;
result += nonfizzbuzzers * log10;
current *= 10;
log10 += 1;
}
long prev = current - 1;
long total = n - prev;
long by3 = n/3 - prev/3;
long by5 = n/5 - prev/5;
long by15 = n/15 - prev/15;
long nonfizzbuzzers = total + by15 - by3 - by5;
result += nonfizzbuzzers * log10;
System.out.println(Long.toUnsignedString(result));
}
}
```
:::
<br/>
> **Bonus!** Rust solution
:::spoiler
There's a bit of math that made this solution way simpler than the others. It treats each segment (1-9, 10-99) the same way other solutions treat the last segment (e.g. 100-145 when $n=145$), and is able to harmonize everything to a one-line solution.
```rust
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut l = std::io::stdin().lines();
let n = l.next().unwrap()?.parse::<usize>()?;
let x = &mut 10;
let answer = 4 * (n/3 + n/5) + std::iter::from_fn(|| Some(std::mem::replace(x, *x * 10)))
.take_while(|&x| x < n)
.chain(Some(n))
.map(|x| x + x/15 - x/3 - x/5)
.enumerate()
.fold((0, 0), |(prev, sum), (i, x)| (x, sum + (i + 1) * (x - prev))).1;
println!("{answer}");
Ok(())
}
```
:::
## E: Flowers
[Problem Link](https://codeforces.com/gym/528561/problem/E)
Problem by Isabella Lin (25isabellal@students.tas.tw)
Tutorial by Isabella Lin (25isabellal@students.tas.tw)
Solutions by Isabella Lin (25isabellal@students.tas.tw)
### Description
The formula for the number of each non-space character is already given in the problem statement. Thus, we just need to figure out how many spaces to put in front of the following lines:
Line 1: We leave space for one petal underneath, which is n+2 spaces.
Line 2: We leave space for the first '(' of the left petal so we output 1 space.
Line 3: Starts with a petal and no spaces.
Line 4 to 4 + (n-1)/2: Line 4 starts with the same amount of spaces as a petal (n+2). After going down each line, we increase the number of spaces by 1.
Line 5 + (n-1)/2 to 7 + (n-1): We start with n+1+(n-1)/2 spaces because it should be a petal length + up to the middle '@'. As we go down each line, decrease the number of spaces by 1.
### Solutions
> Python Solution
:::spoiler
```python=
import sys
n = int(sys.stdin.readline().strip())
#line 1
for _ in range(n+2):
print(' ', end='')
for _ in range(n):
print('_', end='')
print()
#line 2
print(' ', end='')
for _ in range(n):
print('_', end='')
print('(', end='')
for _ in range(n):
print('_', end='')
print(')', end='')
for _ in range(n):
print('_', end='')
print()
#3
print('(', end='')
print('_' * n, end='')
print(')', end='')
print('@' * n, end='')
print('(', end='')
print('_' * n, end='')
print(')', end='')
print()
#line 4 to 4 + (n-1)/2
for i in range(4, 4 + (n - 1) // 2 + 1):
for j in range(n + 2 + i - 4):
print(' ', end='')
for j in range(n - (i - 4) * 2):
print('Y', end='')
print()
#line 5 + (n-1)/2 to 7 + (n-1)
for i in range(5 + (n - 1) // 2, 7 + (n - 1) + 1):
for j in range(n - 1 + 2 + (n - 1) // 2 + 5 + (n - 1) // 2 - i):
print(' ', end='')
if i % 2 == (5 + (n - 1) // 2) % 2:
for j in range(i - 4 - (n - 1) // 2):
print('\\', end='')
print('|', end='')
for j in range(i - 4 - (n - 1) // 2):
print('/', end='')
else:
for j in range(1 + (i - 6 - (n - 1) // 2) // 2):
print("\\ ", end='')
print('|', end='')
for j in range(1 + (i - 6 - (n - 1) // 2) // 2):
print(" /", end='')
#if last line no line break
if i < 7 + (n - 1):
print()
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cout.tie(0);
int n;
cin >> n;
//line 1
for(int i = 0; i < n+2; i++) cout << ' ';
for(int i = 0; i < n; i++) cout << '_';
cout << endl;
// line 2
cout << ' ';
for(int i = 0; i < n; i++) cout << '_';
cout << '(';
for(int i = 0; i < n; i++) cout << '_';
cout << ')';
for(int i = 0; i < n; i++) cout << '_';
cout << endl;
//line 3
cout << '(';
for(int i = 0; i < n; i++) cout << '_';
cout << ')';
for(int i = 0; i < n; i++) cout << '@';
cout << '(';
for(int i = 0; i < n; i++) cout << '_';
cout << ')';
cout << endl;
//line 4 to 4 + (n-1)/2
for(int i = 4; i <= 4+(n-1)/2; i++){
for(int j = 0; j < n+2+i-4; j++) cout << ' ';
for(int j = 0; j < n-(i-4)*2; j++) cout << 'Y';
cout << endl;
}
//line 5 + (n-1)/2 to 7 + (n-1)
for(int i = 5 + (n-1)/2; i <= 7 + (n-1); i++){
for(int j = 0; j < n-1+2+(n-1)/2+ 5 + (n-1)/2 - i; j++){
cout << ' ';
}
if(i%2==(5 + (n-1)/2)%2){
for(int j = 0; j < (i - 4 - (n-1)/2); j++) cout << '\\';
cout << '|';
for(int j = 0; j < (i - 4 - (n-1)/2); j++) cout << '/';
}
else{
for(int j = 0; j < 1 + (i - 6 - (n-1)/2)/2; j++) cout << "\\ ";
cout << '|';
for(int j = 0; j < 1 + (i - 6 - (n-1)/2)/2; j++) cout << " /";
}
//if last line no line break
if(i < 7 + (n-1)) cout << endl;
}
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine().trim());
// Line 1
for (int i = 0; i < n + 2; i++) {
System.out.print(' ');
}
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.println();
// Line 2
System.out.print(' ');
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.print('(');
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.print(')');
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.println();
// Line 3
System.out.print('(');
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.print(')');
for (int i = 0; i < n; i++) {
System.out.print('@');
}
System.out.print('(');
for (int i = 0; i < n; i++) {
System.out.print('_');
}
System.out.print(')');
System.out.println();
// Line 4 to 4 + (n-1)/2
for (int i = 4; i <= 4 + (n - 1) / 2; i++) {
for (int j = 0; j < n + 2 + i - 4; j++) {
System.out.print(' ');
}
for (int j = 0; j < n - (i - 4) * 2; j++) {
System.out.print('Y');
}
System.out.println();
}
// Line 5 + (n-1)/2 to 7 + (n-1)
for (int i = 5 + (n - 1) / 2; i <= 7 + (n - 1); i++) {
for (int j = 0; j < n - 1 + 2 + (n - 1) / 2 + 5 + (n - 1) / 2 - i; j++) {
System.out.print(' ');
}
if (i % 2 == (5 + (n - 1) / 2) % 2) {
for (int j = 0; j < i - 4 - (n - 1) / 2; j++) {
System.out.print('\\');
}
System.out.print('|');
for (int j = 0; j < i - 4 - (n - 1) / 2; j++) {
System.out.print('/');
}
} else {
for (int j = 0; j < 1 + (i - 6 - (n - 1) / 2) / 2; j++) {
System.out.print("\\ ");
}
System.out.print('|');
for (int j = 0; j < 1 + (i - 6 - (n - 1) / 2) / 2; j++) {
System.out.print(" /");
}
}
//if not the last line then newline
if (i < 7 + (n - 1)) {
System.out.println();
}
}
}
}
```
:::
<br/>
> **Bonus!** Rust Solution
:::spoiler
Using the ability to repeat strings with the `.repeat` call, the Rust solution is much more easy to read and write compared to the others.
```rust
fn main() -> Result<(), Box<dyn std::error::Error>> {
let n = std::io::stdin().lines().next().unwrap()?.parse::<usize>()?;
let us = "_".repeat(n);
println!("{}{us}", " ".repeat(n + 2));
println!(" {us}({us}){us}");
println!("({us}){}({us})", "@".repeat(n));
for i in 0..=(n - 1) / 2 {
println!("{}{}", " ".repeat(n + 2 + i), "Y".repeat(n - 2 * i));
}
for i in 0..=(n - 1) / 2 + 2 {
let sp = " ".repeat((3 * n + 1) / 2 - i);
if i % 2 == 0 {
println!("{sp}{}|{}", "\\".repeat(i + 1), "/".repeat(i + 1));
} else {
println!(
"{sp}{}|{}",
"\\ ".repeat((i + 1) / 2),
" /".repeat((i + 1) / 2)
);
}
}
Ok(())
}
```
:::
## F: Prom Date
[Problem Link](https://codeforces.com/gym/528561/problem/F)
Problem by Justin Tjitra (justintylertjitra@gmail.com)
Tutorial by Justin Tjitra (justintylertjitra@gmail.com)
Solutions by Justin Tjitra (justintylertjitra@gmail.com)
### Description
Prom Date can be be solved most easily by using the floodfill algorithm through BFS (Breadth-First-search) on a three dimensional array of characters. One can store the current position of Nobel (position on a floor of x and y values, current floor he is on) along with the time that has passed using a tuple of elements.
### Solutions
> Python Solution
:::spoiler
```python=
from queue import Queue
INF = int(1e15)
dx = [0,-1,0,1]
dy = [1,0,-1,0]
def inside(x,y,m):
return(x>=0 & x<m & y>=0 & y<m)
def solve():
n,m = map(int,input().split())
arr = list()
for i in range(n):
a = []
for j in range(m):
c = input()
a.append(c)
arr.append(a)
vis = []
for i in range(n):
a = []
for j in range(m):
b = []
for k in range(m):
b.append(0)
a.append(b)
vis.append(a)
q = Queue(maxsize = INF)
q.put((0,0,0,0))
vis[0][0][0]=1
while(q.qsize()!=0):
cur = q.get()
x = cur[0]
y = cur[1]
floor = cur[2]
dist = cur[3]
if(x==m-1 & y==m-1 & floor == n-1):
return dist
if(arr[x][y][floor]=='0' & floor < n-1):
q.put((x,y,floor+1,dist))
vis[x][y][floor+1]=1
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if(inside(nx,ny,m)==1 & arr[nx][ny][floor]!='#' & vis[nx][ny][floor]==0):
q.put((nx,ny,floor,dist+1))
vis[nx][ny][floor]=1
return -1
tc = int(input())
while(tc>0):
tc-=1
print(solve(),'\n')
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
#define ll int
#define endl '\n'
using namespace std;
ll n, m;
ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {1, 0, -1, 0};
bool inside(ll x, ll y)
{
return (x >= 0 && x < m && y >= 0 && y < m);
}
void solve()
{
cin >> n >> m;
char arr[m][m][n];
bool vis[m][m][n];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int k = 0; k < m; k++)
{
cin >> arr[j][k][i];
}
}
}
queue<tuple<ll,ll,ll,ll>> q;
q.push(make_tuple(0,0,0,0));
vis[0][0][0] = 1;
while (!q.empty())
{
auto cur = q.front(); q.pop();
ll x = get<0>(cur), y = get<1>(cur), floor = get<2>(cur), dist = get<3>(cur);
// cout<<x<<' '<<y<<' '<<floor<<endl;
if (x == m - 1 && y == m - 1 && floor == n - 1)
{
cout << dist << endl;
return;
}
if(arr[x][y][floor]=='0' and floor < n-1) {
q.push({x,y,floor+1,dist});
vis[x][y][floor+1]=1;
}
for (int i = 0; i < 4; i++)
{
ll nx = x + dx[i];
ll ny = y + dy[i];
if (inside(nx, ny) && arr[nx][ny][floor]!= '#' && !vis[nx][ny][floor])
{
q.push({nx,ny,floor,dist+1});
vis[nx][ny][floor]=1;
}
}
}
cout << -1 << endl;
}
int main()
{
ll tc;
cin >> tc;
while (tc--)
{
solve();
}
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.*;
public class Main {
static int n, m;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static boolean inside(int x, int y) {
return (x >= 0 && x < m && y >= 0 && y < m);
}
static void solve(Scanner sc) {
n = sc.nextInt();
m = sc.nextInt();
char[][][] arr = new char[m][m][n];
boolean[][][] vis = new boolean[m][m][n];
sc.nextLine(); // consume the remaining newline
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
String line = sc.nextLine();
for (int k = 0; k < m; k++) {
arr[j][k][i] = line.charAt(k);
}
}
}
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0, 0, 0});
vis[0][0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1], floor = cur[2], dist = cur[3];
if (x == m - 1 && y == m - 1 && floor == n - 1) {
System.out.println(dist);
return;
}
if (arr[x][y][floor] == '0' && floor < n - 1) {
q.add(new int[]{x, y, floor + 1, dist});
vis[x][y][floor + 1] = true;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (inside(nx, ny) && arr[nx][ny][floor] != '#' && !vis[nx][ny][floor]) {
q.add(new int[]{nx, ny, floor, dist + 1});
vis[nx][ny][floor] = true;
}
}
}
System.out.println(-1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
while (tc-- > 0) {
solve(sc);
}
sc.close();
}
}
```
:::
<br/>
> **Bonus!** Rust Solution
:::spoiler
```rust
use std::error::Error;
use std::io::{stdin, Lines, StdinLock};
use std::mem::take;
fn main() -> Result<(), Box<dyn Error>> {
let mut lines = stdin().lines();
let n = lines.next().unwrap()?.parse::<usize>()?;
for _ in 0..n {
case(&mut lines)?;
}
Ok(())
}
fn case(lines: &mut Lines<StdinLock<'static>>) -> Result<(), Box<dyn Error>> {
let l = lines.next().unwrap()?;
let (n, m) = l.split_once(" ").unwrap();
let n = n.parse::<usize>()?;
let m = m.parse::<usize>()?;
let mut floors = Vec::with_capacity(n);
for _ in 0..n {
let mut ls = Vec::with_capacity(m);
for _ in 0..m {
ls.push(lines.next().unwrap()?.into_bytes());
}
floors.push(ls);
}
struct Grid {
floors: Vec<Vec<Vec<u8>>>,
visited: Vec<Vec<Vec<bool>>>,
bfs: Vec<(usize, usize, usize)>,
}
let mut grid = Grid { floors, visited: vec![ vec![ vec![ false; m ]; m ]; n ], bfs: vec![] };
impl Grid {
fn mark_visited(&mut self, floor: usize, y: usize, x: usize) {
if self.floors[floor][y][x] == b'0' {
self.mark_visited(floor + 1, y, x);
}
self.visited[floor][y][x] = true;
self.bfs.push((floor, y, x));
}
fn propagate_single(&mut self, floor: usize, y: usize, x: usize) {
if self.floors[floor][y][x] != b'#' && !self.visited[floor][y][x] {
self.mark_visited(floor, y, x);
}
}
fn propagate(&mut self, m: usize) -> bool {
let bfs = take(&mut self.bfs);
for (floor, y, x) in bfs {
if y > 0 {
self.propagate_single(floor, y - 1, x);
}
if y < m - 1 {
self.propagate_single(floor, y + 1, x);
}
if x > 0 {
self.propagate_single(floor, y, x - 1);
}
if x < m - 1 {
self.propagate_single(floor, y, x + 1);
}
}
!self.bfs.is_empty()
}
}
grid.mark_visited(0, 0, 0);
for steps in 0.. {
if grid.visited[n - 1][m - 1][m - 1] {
println!("{steps}");
break;
}
if !grid.propagate(m) {
println!("-1");
break;
}
}
Ok(())
}
```
:::
## G: Carrots
[Problem Link](https://codeforces.com/gym/528561/problem/G)
Problem by Isabella Lin (25isabellal@students.tas.tw)
Tutorial by Isabella Lin (25isabellal@students.tas.tw)
### Description
This problem uses [2D prefix sums](https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums), so that given any rectangle you can get the amount of carrots within that rectangle in O(1) time.
One way to implement the 2d prefix sums would be to have a 2D array, and then iterating from the bottom row to the top row, and in each row iterate from left to right. Keep track of the sum of all the carrots from the lower left origin up to whatever coordinate you are iterating on on the upper right (like a rectangle.) To get the sum of any rectangle, take the sum of the upper right coordinate and then subtract the sum of both the upper left and lower right coordinate. Then add back the sum of the lower left coordinate to get the sum of the considered rectangle.
Keep in mind that the input for this problem is a bit long so you may need to make the I/O faster to prevent TLE. For example, in Java you can use BufferedReader and StringTokenizer.
### Solutions
> Python Solution
:::spoiler
```python=
import sys
input = sys.stdin.read
data = input().split()
index = 0
def next_int():
global index
value = int(data[index])
index += 1
return value
f = [[0] * 1005 for _ in range(1005)]
s = [[0] * 1005 for _ in range(1005)] # sum array
n = next_int()
q = next_int()
e = next_int()
k = next_int()
for _ in range(e):
x = next_int()
y = next_int()
f[x][y] = 1
# Set up dp
for i in range(n):
for j in range(n):
s[i][j] = f[i][j]
if j > 0:
s[i][j] += s[i][j - 1]
if i > 0:
s[i][j] += s[i - 1][j]
if j > 0 and i > 0:
s[i][j] -= s[i - 1][j - 1]
results = []
for _ in range(q):
a = next_int()
b = next_int()
c = next_int()
d = next_int()
sum = s[c][d]
if a > 0:
sum -= s[a - 1][d]
if b > 0:
sum -= s[c][b - 1]
if a > 0 and b > 0:
sum += s[a - 1][b - 1]
if sum >= k:
results.append("YES")
else:
results.append("NO")
sys.stdout.write("\n".join(results) + "\n")
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int f[1005][1005];
int s[1005][1005]; //sum array
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
int n,q,e,k;
cin >> n >> q;
cin >> e >> k;
for(int i = 0; i < e; i++){
int x,y;
cin >> x >> y;
f[x][y] = 1;
}
//set up dp
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
s[i][j] = f[i][j];
if(j>0) s[i][j] += s[i][j-1];
if(i>0) s[i][j] += s[i-1][j];
if(j>0&&i>0) s[i][j] -= s[i-1][j-1];
}
}
//answer queries
for(int i = 0; i < q; i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
int sum = s[c][d];
if(a>0) sum-= s[a-1][d];
if(b>0) sum-= s[c][b-1];
if(a>0&&b>0) sum+=s[a-1][b-1];
if(sum>=k) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int[][] f = new int[1005][1005];
int[][] s = new int[1005][1005]; // sum array
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int e = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
f[x][y] = 1;
}
// Set up dp
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = f[i][j];
if (j > 0) {
s[i][j] += s[i][j - 1];
}
if (i > 0) {
s[i][j] += s[i - 1][j];
}
if (j > 0 && i > 0) {
s[i][j] -= s[i - 1][j - 1];
}
}
}
// Answer queries
StringBuilder result = new StringBuilder();
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int sum = s[c][d];
if (a > 0) {
sum -= s[a - 1][d];
}
if (b > 0) {
sum -= s[c][b - 1];
}
if (a > 0 && b > 0) {
sum += s[a - 1][b - 1];
}
if (sum >= k) {
result.append("YES\n");
} else {
result.append("NO\n");
}
}
System.out.print(result.toString());
}
}
```
:::
<br/>
> **Bonus!** Rust Solution
:::spoiler
```rust
use std::error::Error;
use std::io::{stdin, BufRead};
type Res<T = ()> = Result<T, Box<dyn Error>>;
fn main() -> Res {
let mut stdin = stdin().lock().lines();
let mut buf = stdin.next().unwrap()?;
let mut nextint = || {
if buf.is_empty() {
buf = stdin.next().unwrap()?;
}
let (a, b) = buf.split_once(" ").unwrap_or((&buf, ""));
let x = a.parse::<usize>()?;
buf = b.to_owned();
Res::Ok(x)
};
let n = nextint()?;
let q = nextint()?;
let e = nextint()?;
let k = nextint()?;
let mut arr = vec![vec![0; n + 1]; n + 1];
for _ in 0..e {
arr[nextint()? + 1][nextint()? + 1] = 1;
}
for i in 1..=n {
for j in 1..=n {
arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
}
}
for _ in 0..q {
let a = nextint()? + 1;
let b = nextint()? + 1;
let c = nextint()? + 1;
let d = nextint()? + 1;
let sum = arr[c][d] + arr[a - 1][b - 1] - arr[a - 1][d] - arr[c][b - 1];
if sum >= k {
println!("YES");
} else {
println!("NO");
}
}
Ok(())
}
```
:::
## H: Arrakis
[Problem Link](https://codeforces.com/gym/528561/problem/H)
Problem by Nobel Suhendra (71195@jisedu.or.id)
Tutorial by Nobel Suhendra (71195@jisedu.or.id)
C++ Solution by Nobel Suhendra (71195@jisedu.or.id)
### Description
A common assumption is that this problem utilizes graph theory. In reality, the solution to this problem requires linearizing and grouping rings together, separating different rings as different "levels".
This problem can be solved through dynamic programming. Let dp[current_ring][time_remaining] be a 2D array representing the maximum amount of spice that can be collected given the ring Jean is currently located on and the amount of time he has left. At every ring, Jean may opt to move either in the clockwise or anti-clockwise direction (or remain stationary), collecting all the spice in his path, before moving into an inner ring to buy himself additional time (4 days to be precise as moving to an inner ring itself requires a day).
Pre-computation can be conducted to calculate the amounts of spice that can be collected by Jean depending on the number of days he spend traveling within a ring and the direction of travel.
### Solutions
> Python Solution
:::spoiler
```python=
import sys
import itertools
# Constants
MULT = False
MAXN = int(2e2) + 5
MAXL = MAXN // 2
MAXM = MAXL * 5
n = 0
grid = [[0] * MAXN for _ in range(MAXN)]
mem = [[-1] * MAXM for _ in range(MAXL)]
paths = []
def init():
global paths
for i in range(n - 1, n // 2 - 1, -1):
paths.append([])
dist = 0
row = i
col = n - i - 1
len_ = n - col * 2
val = 0
if len_ == 1:
paths[-1].append((grid[row][col], 0))
continue
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
row -= 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
col += 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
row += 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
col -= 1
dist = 1
val = grid[row][col]
col += 1
for _ in range(len_ - 2):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
col += 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
row -= 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
col -= 1
for _ in range(len_ - 1):
paths[-1].append((val + grid[row][col], dist))
val += grid[row][col]
dist += 1
row += 1
def f(l, m):
if mem[l][m] != -1:
return mem[l][m]
if l >= len(paths):
return 0
mem[l][m] = 0
for item in paths[l]:
if item[1] <= m - 1:
mem[l][m] = max(mem[l][m], item[0] + f(l + 1, m - item[1] + 4))
return mem[l][m]
def run():
global n
input = sys.stdin.read
data = input().split()
idx = 0
n = int(data[idx])
idx += 1
for i in range(n):
for j in range(n):
grid[i][j] = int(data[idx])
idx += 1
init()
print(f(0, 5))
if __name__ == "__main__":
if MULT:
tc = int(input())
for _ in range(tc):
run()
else:
run()
```
:::
<br/>
> C++ Solution
:::spoiler
```cpp=
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define fr first
#define sc second
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
const bool MULT = 0;
const int MAXN = 2e2+5;
const int MAXL = MAXN/2;
const int MAXM = MAXL*5;
int n;
int grid[MAXN][MAXN];
int mem[MAXL][MAXM];
vector<vector<pii>> paths;
void init() {
for (int i = n-1; i >= n/2; i--) {
paths.pb(vector<pii>());
int dist = 0, row = i, col = n-i-1, len = n-col*2, val = 0;
if (len == 1) {
paths.back().pb({grid[row][col], 0});
continue;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
row--;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
col++;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
row++;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
col--;
}
dist = 1, val = grid[row][col];
col++;
for (int j = 0; j < len-2; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
col++;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
row--;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
col--;
}
for (int j = 0; j < len-1; j++) {
paths.back().pb({val + grid[row][col], dist});
val += grid[row][col];
dist++;
row++;
}
}
}
int f(int l, int m) {
if (mem[l][m] != -1) return mem[l][m];
if (l >= paths.size()) return 0;
mem[l][m] = 0;
for (auto item : paths[l])
if (item.sc <= m-1)
mem[l][m] = max(mem[l][m], item.fr + f(l + 1, m - item.sc + 4));
return mem[l][m];
}
void run() {
memset(mem, -1, sizeof(mem));
cin >> n;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> grid[i][j];
init();
cout << f(0, 5) << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
if (MULT) cin >> tc;
while (tc--) run();
}
```
:::
<br/>
> Java Solution
:::spoiler
```java=
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static final boolean MULT = false;
static final int MAXN = (int)2e2 + 5;
static final int MAXL = MAXN / 2;
static final int MAXM = MAXL * 5;
static int n;
static int[][] grid = new int[MAXN][MAXN];
static long[][] mem = new long[MAXL][MAXM];
static List<List<Pair>> paths = new ArrayList<>();
static class Pair {
long first;
int second;
Pair(long first, int second) {
this.first = first;
this.second = second;
}
}
static void init() {
for (int i = n - 1; i >= n / 2; i--) {
paths.add(new ArrayList<>());
long dist = 0;
int row = i;
int col = n - i - 1;
int len = n - col * 2;
long val = 0;
if (len == 1) {
paths.get(paths.size() - 1).add(new Pair(grid[row][col], 0));
continue;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
row--;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
col++;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
row++;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
col--;
}
dist = 1;
val = grid[row][col];
col++;
for (int j = 0; j < len - 2; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
col++;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
row--;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
col--;
}
for (int j = 0; j < len - 1; j++) {
paths.get(paths.size() - 1).add(new Pair(val + grid[row][col], (int)dist));
val += grid[row][col];
dist++;
row++;
}
}
}
static long f(int l, int m) {
if (mem[l][m] != -1) return mem[l][m];
if (l >= paths.size()) return 0;
mem[l][m] = 0;
for (Pair item : paths.get(l)) {
if (item.second <= m - 1) {
mem[l][m] = Math.max(mem[l][m], item.first + f(l + 1, m - item.second + 4));
}
}
return mem[l][m];
}
static void run(Scanner sc) {
for (int i = 0; i < MAXL; i++) {
for (int j = 0; j < MAXM; j++) {
mem[i][j] = -1;
}
}
n = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = sc.nextInt();
}
}
init();
System.out.println(f(0, 5));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc = 1;
if (MULT) tc = sc.nextInt();
for (int t = 0; t < tc; t++) {
run(sc);
}
sc.close();
}
}
```
:::
<br/>
> **Bonus!** Rust Solution
:::spoiler
```rust
use std::io::BufRead as _;
type Res<T = ()> = Result<T, Box<dyn std::error::Error>>;
fn main() -> Res {
let mut stdin = std::io::stdin().lock().lines();
let mut buf = stdin.next().unwrap()?;
let mut nextint = || {
if buf.is_empty() {
buf = stdin.next().unwrap()?;
}
let (a, b) = buf.split_once(" ").unwrap_or((&buf, ""));
let x = a.parse::<usize>()?;
buf = b.to_owned();
Res::Ok(x)
};
let size = nextint()?;
let mut grid = vec![vec![0; size]; size];
for row in &mut grid {
for cell in row {
*cell = nextint()?;
}
}
let rings = (size + 1) / 2;
let days = rings * 5;
let mut dp = vec![vec![0; days]; rings];
// ring from outmost to innermost
for ring in 0..(size + 1) / 2 {
let ringsize = size - ring * 2;
let (y, x) = (size - 1 - ring, ring);
let path1 = (0..ringsize)
.map(|off| grid[y - off][x])
.chain((1..ringsize).map(|off| grid[y + 1 - ringsize][x + off]))
.chain((1..ringsize).map(|off| grid[y + 1 - ringsize + off][x + ringsize - 1]))
.chain((1..ringsize-1).map(|off| grid[y][x + ringsize - 1 - off]));
let path2 = (0..ringsize)
.map(|off| grid[y][x+off])
.chain((1..ringsize).map(|off| grid[y - off][x + ringsize - 1]))
.chain((1..ringsize).map(|off| grid[y + 1 - ringsize][x + ringsize - 1 - off]))
.chain((1..ringsize-1).map(|off| grid[y + 1 - ringsize + off][x]));
// which day we can start on this ring
for start_day in ring..=ring * 5 {
let prev = ring.checked_sub(1).map_or(0, |ring| dp[ring][start_day - 1]);
let max_days_to_spend = (ring + 1) * 5 - start_day;
let (mut total1, mut total2) = (0,0);
let mut iter = path1.clone().zip(path2.clone());
for days_to_spend in 0..max_days_to_spend {
if let Some((p1, p2)) = iter.next() {
total1 += p1;
total2 += p2;
}
dp[ring][start_day + days_to_spend] = dp[ring][start_day + days_to_spend].max(prev + total1.max(total2));
}
}
}
println!("{}", dp[rings-1][days-1]);
Ok(())
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
