MOBKUN - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: Sai Panda
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

1242

PREREQUISITES:

None

PROBLEM:

A normal year contains N days, while a “Mob” year contains N+M days. Every K-th year is a “Mob” year.

Given X, does the (X-1)-th day fall in a “Mob” year?

EXPLANATION:

Let’s look at a consecutive set of K years, starting from the first.
Years 1, 2, \ldots, K-1 are not “Mob” years, while year K is.

In terms of days, this means the first (K-1)\times N days aren’t in a “Mob” year, while days (K-1)\times N + 1 to K \times N + M are in one.
Notice that this already gives us the answer for when 1 \leq X \leq K\times N + M.

What happens when X \gt K\times N + M?
Well, by symmetry we can just ignore the first K\times N + M days!
That is, the answer for X is the same as the answer for X - (K\times N + M).

So, we keep subtracting K\times N + M from X till we reach a point where 1 \leq X \leq K\times N + M, then use the condition we derived above to answer for this X.

However, this is too slow: for example, if K = N = M = 1, then we’d be subtracting 2 from X at each step, which is way too little when X is large.

Instead, notice that the operation we are performing is exactly the modulo operation!
That is, we are essentially computing X\pmod{K\times N + M}.

So, simply compute this quantity, for example using the % operator in most languages.
Notice that we want the result to be between 1 and K\times N + M, so if the result is zero then set it to K\times N + M.

Finally, use the condition derived above to answer the query. This gives us a solution in \mathcal{O}(1) per test case.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, m, k, x = map(int, input().split())
    x -= 1
    print('No' if k > 1 and x % (k*n + m) < (k-1)*n else 'Yes')
1 Like
2

Where am I going wrong?
public static void main (String[] args) throws java.lang.Exception

		// your code goes here
		FastScanner fs = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int T = fs.nextInt();
		while (T-- > 0)
		{
		    int N = fs.nextInt();
		    int M = fs.nextInt();
		    int K = fs.nextInt();
		    int X = fs.nextInt();
		    if (X%(N*K + M) <= N*(K-1))
		    {
		        pw.println("NO");
		    }
		    else
		    {
		        pw.println("YES");
		    }
		}
		pw.close();
	}
3

if we take two more scanner to …

4

Anime fan huh :wink::grin: me tooo :heart:

5

The problem says the day after (x -1) from day 1. That means xth day. Then why checking for (x -1)?

1 Like
6

same doubt bro

7

I assume you’re talking about the code linked at the bottom, because the editorial itself doesn’t use X-1 anywhere.
I used X-1 in the code just to make implementation simpler.

Notice that the editorial develops a logic where you check for whether X is less than or equal to (K-1)\cdot N, while the code checks whether X-1 is strictly less than (K-1)\cdot N. It should be obvious why these are equivalent.
The only thing this avoids is the edge case when X\% (KN + M) = 0, where you need to treat this value as KN+M and not 0. I’ve also mentioned this in the editorial:

This brings me to

In relation to the discussion just above this: what does your code do when X\%(KN + M) = 0?

8

Solution: 80937837 | CodeChef

check my solution u will understand i also wrote why things happende, and if it help don’t forget to drop a :heart: