COOMILK - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kamil Debowski
Tester: Niyaz Nigmatullin
Editorialist: Kamil Debowski

DIFFICULTY:

CAKEWALK

PREREQUISITES:

none

PROBLEM

Given a sequence of strings “cookie” and “milk”, you should check whether after each “cookie” the next string is “milk”.

EXPLANATION

We should implement exactly what is written in the statement.
For each string s[i] if it is “cookie” then we must check if s[i+1] is “milk”.
So the answer will be “NO” in two cases (assuming that s[i] == “cookie”):

  1. i = N, what means that s[i] is the last string
  2. s[i+1] == "cookie"

Let’s see the pseudocode of this intended solution:

bool answer = true
for i = 1 to N do
	if (s[i] == "cookie") then
		if (i == N or s[i+1] != "milk") then
			answer = false
if (answer) then
	print("YES")
else
	print("NO")

POSSIBLE MISTAKES

One wrong approach is to think that the answer is “NO” if and only if some two consecutive strings are both equal to “cookie”.
For example, (“milk”, “cookie”, “cookie”, “milk”) indeed gives answer “NO”.
The last of given in the statement example test cases shows that this claim isn’t correct.
The answer is “NO” also if the last string is “cookie”.
In such a situation Limak indeed eats a cookie and doesn’t drink milk in the next minute.

ALTERNATIVE APPROACH

A mistake described in the previous paragraph can be fixed by additionally checking the last string of the given sequence.
So we can get a slightly different implementation:

bool answer = true
for i = 1 to N-1 do   #we iterate to N-1 only!
	if (s[i] == "cookie" and s[i+1] == "cookie") then
		answer = false
if (s[N] == "cookie") then
	answer = false

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.

2 Likes