This problem is actually a fill-in-the-blank. Code is ONLY used to output the answer.

Hey, I am not really that good at math, but problem C is a classic. I have seen it before in different forms. I think that's totally acceptable for a C, especially since you can write a bit of code to test behavior and update your intuitions (which imo is a highly valuable skill for divs)

but isn’t cp and mathematics deeply correlated? so i think cpers should be willing to accept any kind of mathematical problem as a challenge, whether or not it directly contains algorithms. and the announcement itself already said that this round took a year to be fully made, and was also refined by many well known and highly rated members of the community, or is cp more like just applying algorithms that were already invented by some genius? either way, i’m learning a lot from this community in the hope of improving my problem solving skills, so i was genuinely curious about this

they should have a goofy edge case to troll the guessers

I can understand why it's so frustrating to be honest, I have to admit I am one of the guessers as well, especially the part about gcd(n, m) <= 2 was not so easy to observe. Had there been a need for proof I am sure more than half of the people including me would not be able to answer this correctly.

i think it was quite fairly easy to see that you need the two GCDs to be 1 but the gcd(n,m)<=2 thing may be based more of RNG

It didn't seem like that much guessing for me, but maybe because I have solved similar problems before.

Here is how I thought about it:

Assume you only move vertically; at the second $$$i$$$ you are at $$$(i \cdot a) \% n$$$. to be able to pass by every possible row, $$$gcd(a, n)$$$ must be equal to $$$1$$$, the same goes for horizontally, but then it's $$$gcd(b, m) = 1$$$.

Now to check if we will visit every possible cell we calculate the number of steps it takes us to get back $$$(1, 1)$$$ (and reach a cycle); we return to the first row when $$$(i \cdot a) \% n = 0$$$, this happens when $$$i \cdot a$$$ is a multiple of $$$n$$$, and of course $$$i \cdot a$$$ is a multiple of $$$a$$$, so we need to find the smallest number that is both a multiple of $$$a$$$ and $$$n$$$ and that $$$i \cdot a = lcm(a, n)$$$, $$$i = lcm(a, n) / a$$$, we can notice that we go back to $$$1$$$ at every $$$i$$$-th move.

Similarly, we calculate when we will return to the first column using $$$j = lcm(b, m) / b$$$, at each $$$j$$$-th move, we return back to the first column.

Now to find out when we will return to $$$(1, 1)$$$ it's simply $$$(lcm(i, j))$$$.

Here in each move we either move down then right, so we multiply by $$$2$$$, the number of cells we visit before we return to $$$(1, 1)$$$ is $$$2 \cdot lcm(i, j)$$$.

We compare it to $$$n \cdot m$$$ (the total number of cells).

Doing math (that I'm lazy to write) can get you to the gcd formula, but you don't really need to do so.

You have to practice to guess.

why are you blaming the problemsetters tho? id just remember the trick for next time and move on

Man can anyone guide me on how to solve that type of problems? like I was able to get A,B but C was over my head

Any ideas, or resources or thoughts

When I tried to guess this task, I got wa2. I needed to prove the conditions and I was satisfied with the solution, it was a good task for its position.

why couldn't you simply guess the solution?

i agree, pure math questions should be minimized

Mathematical forces!!

I'm weak in abstract math like things about mod,xor.Maybe it's educational,but is it suitable for D2C?Is it closer to a CP problem or a math problem?This round is absolutely a horrible memory for me.I'm trying hard to approach GM,but eventually I failed to get back to Master and unexpectedly receive a newbie performance.Worstly,I think some problem in the round are TOO CLASSICAL IN MATH THAT AI CAN SLOVE WITHOUT EFFORT.

bro fell for the ragebait

take a chill pill

Wow, I noticed one set is half of the needed set. So the size of needed set must be.... LET ME GUESS.... Twice of the size of first set? I am so good at math

All feelings aside, were there any set of skills (other than outputting the answer) unique to CP that the problem tested? Either way, I can't help but feel that this is just an Olympiad math problem forced to be in a CF contest.

To be honest, a large portion of modern CF problems requires no algorithm (especially first half of Div.2). And it might be healthier to think CF round as discrete puzzle contest rather than DS&algo contest.

If you really just want to solve algorithmic tasks, try ICPC or atcoder beginner contest. Though you would still meet such "mathy problems" but with less frequency.

No lol

I think it would be better if they start separate mathematical rounds.

It would also make it easier to find and practice problems with "pure math no implementation"

Although I guessed the part gcd(n,m)<=2 but then proof came naturally

I have seen fair share of bad problems, but C is not one of them. It's an observation based problem.

1) You need to visit each row and column, so n and a must be coprime, similarly m and c

2) If n and a is coprime, We know that after exactly n moves we will be back to row no 1. Similarly, other rows are going to be repeated every n moves

3) Now the problem becomes simpler, if we can prove that we can completely finish one single row, we can definitely finish every other row, since row and column movements are independent.

3) Let's assume that we go d->r->d->r.... after n down steps and n right steps we will be at a certain position in row no 1. let it be x1, just before the last right step, we will be at another position in row 1, let it be x2 = (x1 — b) % c. We can notice that this process will keep repeating after every n steps, shifting the values of x1 and x2 by the initially found value of x1. Now you get another subproblem, you need to figure out if given these conditions we can complete a row or not, which is not difficult to do. You can calculate for both possible ways to start, but proving for one is enough.

This is not a very math heavy problem. It's a number theory based problem, which is well within the bounds of CP and it is a topic you need to master to get good at CP. It is not very easy, but not too mathematically complex for CP either.

The tutorial of C was wrote very bad ngl

One way to guess is brute-force small cases and find something xddd

I revieved the problem 1091C and I think it's mostly not mathforces and CERTAINLY not guessforces. First of all, guessing the appropriate condition in this problem seems extremely unlikely, especially as you suggest for hundreds or thousands of participants. The solution is too specific for anyone to guess it without at least partial solving and only then "guessing" that one of the conditions is gcd(n, m) < 3 (which still seems pretty unlikely to me). In particular, my thought process in this problem followed a path very similar to the editorial: start by observing 1D case (that's how you get a sufficient condition gcd(n, a) == 1 and the other one), consider when in 2D going by diagonal, you arrive again to the row 1 at some offset coprime to n.

I understand that you think the problem is guessing, because the condition like gcd(n, a) == 1 seems pretty ad-hoc, but if you think about it, it's just a shorthand to writing "each column in the row is visited at least once". You don't have to formalize this idea using gcd, if you just start to think about when hopping by a constant jump allows you to visit all spaces. For a master like me, this is trivial that it's gcd(n, a) == 1, because I immediatelly see this as "when does $$$ak \mod n$$$ cycle through all values if $$$a$$$ is const?", which then I immediatelly see this as equivalent to "when is $$$a$$$ invertible $$$\mod n$$$?" which is again equivalent to "when is $$$a$$$ coprime to $$$n$$$?" to which the immediate answer is $$$\gcd(a, n) = 1$$$. So as you can see, this is a very natural way of thinking and requires 0 guessing skills.

I understand that this line of reasoning I used here may seem like I know some number theory, but in fact I just saw this many times in my life. You equally can just play with some examples and see the patterns without knowing any of this. Just pick a clock, start from 12 and jump by constant step, when you will visit all the numbers? You will quickly see, that jumps 2, 4, 6, 8 and 10 are always looping through even numbers, jumps 3 and 9 are looping over multiples of 3, and you are left with coprimes. Now you can generalize this immediatelly: if $$$n$$$ and $$$a$$$ share a divisor, this process always loops over multiples of this divisor, so you will never visit everything.

So really I don't see how you can say this problem could use any guessing? I think it's an OK problem, especially for D2C; actually I'd even say it's a pretty easy problem, because it's just a 2D variant of the classic clock game I described in the previous paragraph.

Agreed, a little now and then is fine, too much is uncomfortable.

Obviously the problem is not a guess problem. It is a knowledge check on Bézout's theorem.

If you didn’t solve problem C, then you simply don’t know the definition of gcd.

This was absolutely trivial for a problem C, and not solving it should be a reality check for you. Maybe study math?

Not sure if this is rage bait…

Mathforces classic. I found this one to be quite fun, however. Math is a fundamental part of many competitive programming tasks, especially GCD.