Hello, Codeforces!
I'd like to invite you to take part in Codeforces Round 593 (Div. 2). It will held on Oct/17/2019 16:35 (Moscow time). The round will be rated for the participants with rating lower than 2100.
You will be given 6 problems and 2 hours to solve them.
Scoring distribution: 500—1000—1000—1750—2000—2500.
The problems of this round were developed by me. Thanks a lot to isaf27 for his excellent coordination, to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platform, and to mnaeraxr, antontrygubO_o, NIWIS, win11905 for testing.
This is my first round ever. I hope everyone will enjoy it.
Good luck!
UPD: The round is over! Congratulations to the winners:
Div.1 + Div.2 participants:
Official participants:
UPD: Now the Editorial is available.
It's the contest season again :D
Is it rated?
The round will be rated for the participants with rating lower than 2100
PS. I hope anyone record the process of preparing one problem with commentary, will publish it on Youtube after the contest. It's useful.
https://youtu.be/IaViSV0YBog
Who else is going to make this contest a priority to gain back the rating points that we lost in Tourist's contest ?
I have a suspicion that contenst was just a measure to target rating inflation at Codeforces.
I hope I can do that. Good luck!
well,I did too badly on tourist's contest I don't think one contest is enough to make it up. Anyway,I wish you all good luck and high rating.
Best of luck for your first contest
How short the announcement is!
However, hope your first round will be successful!
Request for This contest :: Please make large inputs downloadable
Hope for a great contest as it’s your first time !
i wish it be safe from any hacker attack .. Cirno_9baka
Do you think this round will be the strongest?
I will try to wake up on time to participate. Now, I have a challenge: For every rating point lost, I will do one pull-up. For every point won I will do three pushups. Everyone is welcome to join the fitness challenge. Write what you'll do if you lose or win rating.
I screwed up badly. This is gonna hurt.
A bus left the Scarlet Devil Mansion; $$$a$$$ people boarded at the start.
At Hakugyokurou, $$$b$$$ people left and $$$\frac{b}2$$$ people boarded. (It is guaranteed that $$$b$$$ is odd.)
At Yakumo-san's house, $$$d$$$ people left, where $$$d$$$ is the imaginary solution to $$$ad^2 + bd + \sin c\pi = 0$$$.
How many passengers remain? Print the answer modulo $$$993\ 244\ 853$$$.
According to the writer's name, I bet this round may include some Touhou-themed problems.
Good luck with your first contest!
I smell math problems O_o
UwU
I hope the round contains some basic graphs problems
I hope this round does not contain strings problems
yeah seriously
Why?
By strings I meant strings related some advanced DS or KMP etc. for a stupid and mean reason because I don't know about them. Though I should not worry about them because even if they are present, they will be in later half of the set.
Btw since you are tester and your reply to this particular comment gives a hint that there will be some sort of strings related problems.
Thanks for the contest :)
Oh, maybe I'll become green after this round.
[Deleted]
i hope statements wiil be without anime
wish short problem not hard code good pretests and high ratings :)
A speed typing test?
Speed Test :/
Was B meant to use OEIS???? How come B is on B? 1000???
PROBLEM B is (2^m-1)^n
I TYPED THIS FOR SO LONG OK SO PLEASE READ https://pastebin.com/Qjr3h8Ui
care to explain ?
The number of ways to include the ith kind of item is the number of ways to pick k boxes out of the m boxes. Also, the number of ways of picking the ith kind of item is independent of the number of ways of picking the jth kind of item.
For each type you need to choose subset of boxes. And subset must be non-empty
I have added explanation sorry it took me long time
The idea es the following: If we only focus on a certain number, we have clearly (2^m)-1 possible options. This is because any box can be either "full" or "not full", this is, with the number on it or without it. We substract 1 because we don´t consider the case in which every box is "not full". Then, as we have n possible numbers, for every number we have (2^m)-1 combinations, resulting in ((2^m)-1)^n.
My answer is (2^m — 1)^n
How did you come up with this solution?
We need to distribute every present to at least one box ie (2^m — 1) (-1 because you remove the case where all boxes dont have this present)
We do this for every present... hence: (2^m — 1)^n
correct, click here for the solution
How to solve F ????????????????????????????????????????????????????????????????
How to solve D?
Seems like the doll's trajectory is a spiral from $$$(1,1)$$$ to the center, therefore the obstacles must only be in the end of the spiral (or form complete rows / columns on the bounds of the grid).
If this is the case, I don't know how to code it neatly and concisely.
The path must be a spiral... somehow. "Simply" check if one can run that way.
Isn't that O(nm) which is 10^10?
You don't actually visit each cell. On each row (or column), you just move to the end of the row, which means finding the first obstacle hit, or the last column not yet hit. This is O(lg k) time (binary search the obstacles on the row). So, each row or column is O(lg k) time, and each row/column is done only once, so total time is (m+n)(lg k).
No. You run from (1,1) to (1,n-1), then to (m-1,n-1), then (m-1, 1)... And so on.
It loops 1e5 * 2 times.
One can use two sorted lists of the obstacles to optimze the search.
Sort one list by colums, one by rows. Ie use vector<pair<int,int>>, onc sorted by first, one sorted by second, then first.
To check if all fields where visited, count them. Fieldcount + k == n*m
How to solve D ?
The first observation would be that if there is a solution, then the path will look like a clockwise spiral. The second observation would be that we don't have to simulate each step. Instead we should simulate all the steps in one direction in one move.
Let's initialize the variables n1 = 1, n2 = n, m1 = 1, m2 = 2 the borders of submatrix we should be able to visit. Also let's keep sets on each line/ column in order to store the obstacles on those lines/ columns.
Now let's say we're at position (i, j) and just changed direction to move to the right. If there is an obstacle in our way at position (i, k), with k from [j + 1, m2]), then we can only ever reach column k — 1. Thus m2 will become k — 1. Moreover, a solution exists only if the submatrix ((i, k), (n2, m2)) is filled with obstacles, else there is no solution. We can easily check this using our COLUMN sets (i.e. if a column k -> m2 has exactly n2 — n1 + 1 elements then it is filled with obstacles, else not). To be able to make correct checks in the future, we will remove all these obstacles found in the said submatrix from their corresponding LINE sets. Now we can update n1 to n1 + 1 (since we will never return to this line), update the doll's position from (i, j) to (i, k — 1) and change the direction to moving downwards. Everything works in a similar way for the other directions.
We know we reached the end if the number of steps taken + the number of elements removed == n * m.
Perfectly imbalanced.
Did you find what is test case 4?
There was a problem in the logic of my solution, and I found that the actual solution will require much heavier implementation, so I couldn't make it in time.
This was perfectly imbalanced round.
I really hope the problem D has some pretty and easy to implement solution.
Yeah I agree; the one I was thinking of was really nasty to implement (lots of if cases and room for error) so i figured it wasn't worth it given how much time I had left. Watch there be some 5 line mathematical solution lol ;P.
Indeed, I've figured the spiral logic, had 140+ lines of code but I was still writing code 5 minutes before the time ended.
Basically we have to check the frame and blocked and one central blocked component.Heavy implementation !!!
If it was so easy then why didn't you submit it? Oh, I understood...
Greedy solution for $$$D$$$:
Keep going in the direction you are facing until you have to change it. When you can't move anymore, see if you covered all squares, if you did, answer is yes otherwise answer is no.
Try to prove this.
Implementation: 62820909
Edit: Why the downvotes?
Correct. But hard to implement, as N, M <= 10^5, which makes it impossible to mimic every step.
I implemented the simulation by C++ upper_bound but I am missing some cases.
Edit: I just realized that I had just forgotten to replace a $$$x$$$ by $$$y$$$ after copy-paste. Got AC now. :(
I also implemented using upper_bound but got TLE on case 4
Cool. It's the first time I've heard of this method... Silly me implemented a sort of binary searches.
It was indeed a pain to implement. But, you don't have to visit every cell. Just determine how far you can travel on that row/column.
I used binary search to find the next obstacle on that row/column, and then just moved that many spaces (or, until I had reached a previously hit row/column). So, total time is just (N+M)lg(K).
Still this was very annoying, and I ended up just copying sets of code 4 times to handle the different directions; not at all elegant.
And you check whether you cover all cells by (N*M — K — cells_visited)?
Nice move! I even write a function to confirm a rect is filled by obstacles and proved the overall complexity is O(klogk)...
problem C feels like "dont know why does it work but gonna send it anyway"
The problem C reminds me of printing snake print of a given matrix.
If n is 3, then insert elements till n**2 (i.e. 9) in spiral order in a 2D matrix:
1 6 7
2 5 8
3 4 9
Finally, print it. As simple as that
Yeah the problem was too wordy so I skipped straight to the example, figured out a weird pattern, coded it up super fast, and watched it get passed pretest with disbelief. I was fully expecting a WA but I got lucky o_o.
So, i can prove it. Let's explore f(X,Y) and f(Y,X). Of course, f(X,Y)+f(Y,X)=n^2. so max value of min(f(X,Y),f(Y,X)) is (n^2)/2. So, (n^2)/2 is our top estimate.
Let's try to reach it. Let's build an example, where min(f(X,Y),f(Y,X))=(n^2)/2. (for any X,Y) This way, I divided n^2 labs at n sequential sectors. Let every sector is a permutation of {1,2,3,4..n}. So we have sequence A, A.size = n^2. This sequence means that lab with index i has group number A[i].
Let's take two random groups X,Y. Understand, that for each sector water can go from A[x] = X to every A[y] = Y where (sector of index y)<(sector of index x). So, f(X,Y)>=n*(n-1)/2 Likewise, f(Y,X)>=n*(n-1)/2. (observe that n*(n-1)/2 + n*(n-1)/2 = n^2-n, that is we lost n pairs).
ok, we didn't explore such A[x]=X, A[y]=Y, where (sector of index y)=(sector of index x) Here is n pairs. And we need to distribute them roughly in half between f(X,Y) and f(Y,X) to maximize min(f(X,Y),f(Y,X)). So, in roughly half sectors $$$x<y$$$ and in other half is $$$x>y$$$. My solution is to make sectors such way: sector1 = {1,2,3,...n}. sector2 = {n,n-1,...,2,1}. sector3 = {1,2,3,...n}. sector4 = {n,n-1,...,2,1}. ...
Easy to see that we reached our purpose: in roughly half sectors $$$x<y$$$ and in other half $$$x>y$$$, for every groups X,Y, where A[x]=X, A[y]=Y. After writing this solution you can see that it will be a number-snake in answer table.
How to solve B? I've used b*(2**a)+1 formula but getting TLE
(2^m-1)^n remember to use fastpow
Can you exaplain how did you reach this equation ?
Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.
for the situation of n=1 obviously the answer is 2^m-1(all have 2^m situations, but the situation of all of m is none is incorrect) So when n is greater than 1, the answer is multiplication of n numbers which is 2^m-1.
It's like suppose there is a ball. Now for every box, I have 2 choices to make whether to put that ball in it or not. So 2^m for m boxes. Now this includes a way where we haven't put that ball in any box. Hence, allowed ways — 2^m — 1. Now,since there are n such balls therefore ( 2^m — 1) ^n
i used the same thing but wrong answer on pretest 3
Maybe your fastpow is error
i changed long to long long and it worked .Can u explain whats the need of long long?
emmm, In fact,long has the same range as int while the answer which mod 1e9+7 may be large（near by 1e9). So your data may overflow in your code of fastpow. Check your code and you will find there will be some multiplication which makes your data overflow
you were close, i also did the same at first but got WA on test case 3.
after that i realize that, for 1 item the probability is 2^m — 1, what about 2 item? just multiply both of it (2^m-1) * (2^m-1). since n = 2^19, iterate it would be TLE.
so the solution is (2^m-1)^n and don't forget to use Modular Exponentiation
Did same thing, still got a WA on pretest 3 https://codeforces.me/contest/1236/submission/62811911
it's on here 8th line mul = ((mul%mod)*(base%mod))%mod
it should be mul= mul*mul not mul = mul*base
I submitted my solution just before the contest ended and I got an idleness limit exceeded. What does this mean? Link 62815630
lol
Turns out the cerr in my code caused it. Weird..... 62821549
How to solve E?
I tried to solve it with DP, but my table dimensions were too big, which was something I couldn't reduce ...
Even though I agree the problems were not really balanced in terms of difficulty, I liked them a lot (especially D and E seem to be very interesting and I'm looking forward to read the editorials).
After a perfectly balanced round, comes a perfectly unbalanced round.
N(balanced)== N(imbalanced) -> perfectly balanced
It took me 15min to undertand statements of Problem E...
Quite amazing I took 25 mins.
It took me 0 minutes to understand E coz I didnt even read it
I think this round is very imbalanced, because tester's team mainly consists of div1 persons
That's why more people solved C than B
Me after solving A,B,C:This round doesn't seem to hard. Promblem D:I'm going to end this man whole carrer.
touhou round so hard q.q
What is test 7 in D?
Really hard :/
D is a debugging nightmare...
It would be worse if pretests is weak..
I submited 4 times to pass the pretests...
Nonetheless, LayCurse managed to pull off 5 hacks in a room of yellows and reds, with only 9 submits for D..
And I just found my submission failed at m = 1, n > 1....
Why is this code getting TLE in problem D? Code I used binary search for the current location and changed the location accordingly.
Do you have an infinite loop for most grids? That's the mistake I made and this looks similar. Try input
5 5 0, for example.Infinite loop for this case :/ Thanks!
Can someone please explain how did you come up with (2^m -1 ) ^ n for B?
Sum of binomial coefficients i.e. nC0 + nC1 + ... + nCn is equal to 2^n. This is a common property of binomial coefficients.
From input explanation you can see that there is 2^m — 1 ways to divide one present to m people. All n presents have the same amount of combinations so from here answer is (2 ^ m — 1) ^ n
consider present type x: you have 2 options for each box to put present in it or not. so in total you have 2^m options but one of the at least should not be empty so 2^m-1.
and each of present types are independent from each other (do same procedure for all types) so (2^m-1)^n.
fot problem E it takes me almost 60 minutes to find the trap it turns out to be the situation that n=1.
didn't like problem c so tried to solve D. tried for 70 mins solved it 5 min after contest was already over smh . should have just sticked to C.
For E is it correct that for any x the pairs (x, y) that satisfy will be such that all the possible y's for that x will be continuous integers ? Like (3, 1), (3, 2), (3, 3) where x is 3 and y belongs to [1,3]?
Yes, since after reaching a position y you can always stay there by moving right if ai = y, and moving back after the last one, stay there for the rest of the cases. However I got stuck on finding maximum and minimum y
Ya, I realised my solution failed on pretest 15 since I didn't consider N = 1 case.
Anyways here's the solution to find the maximum and minimum:
The brute method is to increase/decrease whenever possible.
To optimise this we can create an array of size M that says for each position p if we have a number equal to A[p] at that point what's the max or min I can get at the end. This can be calculated in M log M. We can use the same array to find for each number what's the max/min I can get if i start with it.
Update : Got AC by fixing N = 1 Link
Man I thought an array like so might not be able to transition but after reading your idea I wrote it on paper and yes it can be calculated in M * logM. Thanks.
Disgusting problem D
For everyone waiting for system tests:
there's a new twice mv out now
https://www.youtube.com/watch?v=zQELp93xxfo
Amazing Round .
is this a joke?
Although deriving formula for B is not that hard (just in my opinion), I think it was not appropriate to put such problem in Div2B since it requires fast exponentiation.
correct. B should have been easier than this one. C should be D. D = E.
How about python? Time to learn a new language
python does binexp?? I just wasted 15 minutes debugging my bin exp in python3 X(
pow(a,b,m)returns a^b mod m :DI think the formular is unreachable if one has to figure it out by himself.
I tried to come up with a solution for n=1, and did not found it. After seeing the formular here in the comments it is fairly simple to implement it.
I meet a strange bug when using m2.codeforces.com:
The statement of A says 'The statement is not available'.
So I think there're some technical issues and throw A away...
I didn't realize the problem until I looked at the standings after one hour!
The same here. However, this is a lesson for you to open every problem before solving any of them.
Always have both the main site and a light version open. Main site gets attacked, light site has bugs.
balanced?
However if both happen, it's imbalanced. (I used the light site because I can't get connected to the main site during the contest, at least in the first 5 minutes...
Who else forgot n=1? :)
It is glad to see that the author determined to make the $$$n=1$$$ case in the pretests. Or there will be plenty of FSTs, for example, me.
Totally agree. :) I'm glad that pretest 15 was there to block me early.
(And pretest 14 reminded me to use a long for the answer, lol).
Your D failed in 218 case. Its disgusting
D is Disgusting anyway
WHEN I SAW problem B ![ (https://images.app.goo.gl/H9q9HbBeTSCQTjVS8)]
WHEN I SAW PROBLEM C ![ (https://images.app.goo.gl/P7HnpmTw4LKifK2J8)]
Red coders should stop making Div2 only contest. Their contests are so inbalanced. :(
In my opinion the imbalance matters because solving a harder problem differentiates the people who are skilled and not skilled. For example, tmwilliamlin168 is extremely skilled so he always solves more problems than me. tmw OFZ.
I missed the DDOS attack this round :(
Upvote if you got the solution to C from sample
If I get to 1400 rating I change colour right? OMG I might get there plz
good luck bro :D
test
REEE LETS GO YEEEE MINECRAFT
Deleted
62815596
Can somebody explain (TASK D) why this is not correct?
First I remove full lines with block (right and bottom)
Next I check that all remaining blocks in tail of snake-filled array
for example if left 3x3 array and two blocks, I check that this blocks in 8 and 9?
Is it correct? Or idea was wrong
1 2 3
8 9 4
7 6 5
upd. I think I understand, I need to delete all left vertical lines with all blocks except 1 row...
Aaaaaaaannndddd.... WA218!
WA219!
Congratulations with your first contest! Congratulations with your last contest too!
Поменьше бы таких раундов...
Can you explain your thought process for B?
Like from when you saw the problem
IMO C was easier than B
I tested with examples, noticed that we needed to assign one present to someone for each type and listed out the ways for the rest.
My kinda messy (not the smartest but i guess easy to understand) explanation https://pastebin.com/Qjr3h8Ui
B is quite clearly a math problem (very large input parameters, O(n) fails, reads like combinatorics), so the idea would be to try and derive a formula to solve B.
My solution used inclusion-exclusion and was very messy, but the expression simplifies quite nicely to the simple formula.
Edit: So you count all the ways to distribute the gifts without considering whether every gift is used, to get 2^NM ways, and then you consider the case where at least one gift is not used, and then the case where at least two gifts are not used, et cetera. The result is a well-known expression (binomial theorem), so you can get (2 ^ M — 1) ^ N.
problems are very interesting. I really like it!
Can someone verify if the following logic is correct for D?
If we just consider all obstacles, they're also going to form a spiral path. We can fix one obstacle and break this path down into two spirals: — a clockwise spiral path and an anticlockwise spiral path. So, we start from this obstacle and simulate the moves, the clockwise starting from direction 1, while the anticlockwise starting from direction 3. If we can cover all the K obstacles in either of the 2 (disjoint) spiral paths, it's a valid input.
i do not think anti-clockwise path is a valid one....
No, I think the obstacle doesn't have to form a spiral path always.
Consider the following grid: (1 = Obstacle, 0 = Empty)
0 0 0 0 1
0 0 0 0 1
0 1 0 0 1
0 0 0 0 1
Got it, thanks!
I guess that one Specialist tester wasn't enough.
But I have to say, that I like these problems.
F seems to be interesting.
Why problem creators make such problems as C? there is no any logic just like guess output and get AC. I think at least 95 percent of participants solve it so. I dont like this round for me the tasks were uninteresting and disbalanced.
Sorry for the difficult problem D.
I thought it may be just a simulate problem and may not so hard, but the fact isn't. It contains many details and not so easy to write.
Again I will say sorry. I will try to improve myself on controlling the difficulty of the problems.
I submitted at last minute. So, I am scared of TC218.
UPD: Accepted with 6 TLE attempts..XD
So what is the content of test #218? Is it pre-determined or from hacking?
You will do better next time， keep it up
I believe that the main problem with it was the weak pretests, if test 218 was in the pretests, maybe the percentage of AC would be way more different :/
I think the main issue of this round not problem D. It was pretty hard to implement but doable. But the problem C is not a good problem for such round. I'm pretty sure that 90% of AC on this are just "hm, I consider some pattern in the output, what will happen if I submit it? Oh, AC, great!". Almost nobody proved this solution during the contest and this turned out the problem to finding the pattern faster than others.
Problem C rewarded people who were like "Let's try this non-sense first and then think more" and punished people who were like "Let's think first, if no ideas, try some non-sense".
Exactly my thought. Seemed to be a very Codechef-esque problem (at least for me). Every time in the Div 1 long challenge, they give one of the first 3 problems like this. But, at least, they give 10 days to think. Lol.
My problem with D was that I didn't realise every cell can only be visited once until the clarification came.
Anyone got what pretest 4 is? Please share
How to solve E?
Observe that the reachable points for each starting point form a continous interval.
Say that for each starting point, we want to know the farthest point to the left it can reach, which can be done by each time make one move to the left if possible. We can simulate the process in $$$O(n)$$$ by maintaining the number of starting points at each current position.
Is true, you just need to calculate the most away reachable point to the left and right of each position. But how can you make it in O(n) time. I think about using ST to simulate it, but it turns into a complicated implementation, can you explain me how to solve the problem using your idea?
Process every position in parallel. Each time every position should move to the left except one. This should lead to an $$$O(n)$$$ implementation.
If anyone is curious, I suspect test 218 for problem D is something along the lines of:
3 1 1 3 1
The correct answer is Yes, but many solutions are printing No, because on your first step you can't make any steps to the right. However, that's not an issue here because you can immediately turn right (so you're now facing down) and move down one step. I tested a few WA218 solutions on this case and found that they all printed No here.
Yeah, my solution fails on 218 and fails locally for
5 1 0. :(Edit: resubmitted with a fix for this and got AC.
Yes, it has to be the case where you are expected to take a turn at the starting cell itself.
Yeah. My code also failed this test case. Although they should have added this test in pretests itself.
The person who hacked someone with this test is Thanos of our generation. With one click he killed half of AC solutions on D.
I got hacked with this during the round, so they were someone in my room. Only andrew and neko_nyaaaaaaaaaaaaaaaaa had hacks in my room, so it was one of them :P
Hard code for D and Good test 218
The absent of test case 218 in pretest seems to f**k participants up deliberately, right?
edit/ I didn't get that 218 was hack data. It seems that it was not deliberation, just failure to consider corner case
me too. 0 1 1 1 1 \n 0 1 1 1 1 \n 0 1 1 1 1 \n 1 1 1 1 1 \n 1 1 1 1 1 \n it should be moving from {1, 0}
After the contest ended, I received an e-mail from [email protected] saying that my solution for problem A 'significantly coincides' with a solution from other user. I entered his profile that was on the e-mail and checked his solution. It is quite similar, it uses the same idea, but this is a simple ad-hoc problem, and I'm pretty sure a lot of other people must have made similar solutions.
Anyway, the email said "If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details". Well, there obviously was no source published before the competition, and I just solved it by myself, and considering it was an easy problem I'd not be surprised that many similar solutions exists.
What can I do? I'm from Brazil and that profile is from a random guy in China, and as it was the easiest problem and most people solved it pretty quickly there's no way we would have gotten the same code on purpose.
The e-mail says "Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.". But it wasn't a violation, obviously a problem that occured, what could I do to remove this violation?
The round was quite unbalanced. My friend has got only 72 points more than me, but he's 500 places higher. Guess the author should learn from tourist how to make BaLaNceD contests.
There is no test case against int overflow in D...
Can someone explain problem B pls?
We can take every present into account separately. There are totally 2^m ways to place. Obviously, we can not take the way of "all the box is empty", so there are (2^m-1) reasonable ways. Every present is irrelevant. So we can get the answer : (2^m-1)^n
i solved B using,total ways — invalid ways, i calculated invalid ways using inclusion-exclusion principle, which is sum r=1 to n ( nCr * 2^((n-r)*m) — 1)* (-1)^(r+1) which reduces to (2^(m*n) — (2^m-1)^n — 1) also total ways = 2^(m*n) — 1 .......substracting 1 for empty sequence hence valid ways = total ways — invalid ways = (2^m-1)^n.
Hey, can any of you guys help me with problem C ?
first thing to notice that is highest numbers must be in one column,then as first row gets bigger number then put lowest in it, this is the most optimal way to put numbers.do it column by column.
Java BigInteger became useful for problem B. I used the same formula (2^m-1)^n. Here's my JAVA code: 62824862
"Quick Pow with Mod" may be useful for you.
Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(found a mistake in D after 50 min debugging during the contest and 2 hours after the end)
Прошу прощения за беспокойство. Сегодня (вчера?) на контесте некто coder_aditya скопировал мои решения с открытого (каюсь, сам виноват) исходника в ideone. Так, этот недобросовестный пользователь полностью скопировал мои решения по задаче А (62787915 и 62785873) и по задача С (62803225 и 62803022). По неясной причине он сначала отослал полные копии (зачем???) а затем отредактировал оригинальный код с тривиальными изменениями, получив OK за задачи А (62813924) и C (62814398). К тому же задача B у него также засчитана как решенная, так что не удивлюсь если он и ее у кого-то украл. Прошу принять меры, так как я в итоге остался без рейтинга, а он после редактирования чужих решений поднялся.
Sorry to bother you. Today (yesterday?) At the contest, someone coder_aditya copied my decisions from the open (I confess, it's my fault) source in ideone. So, this unscrupulous user completely copied my decisions on Problem A (62787915 and 62785873) and on Problem C (62803225 and 62803022). For an unclear reason, he first sent out full copies (why ???) and then edited the original code with trivial changes, receiving OK for tasks A (62813924) and C (62814398). In addition, task B was also counted as accomplished from him, so I won’t be surprised if he stole it from someone. I ask you to take action, because in the end I was left without a rating, and after editing other people's decisions he got a little rating.
Finally back to purple!!!
I want to ask a question, why the testcase's answer is no?
It starts from (1,1) and turn right at (1,7).After walking across the big circle, it returns to the original point (1,1). then it goes on and turn right at (1,4) and end at (4,7).
All points has been visited. And at every point it turns right at most once.
Do I misunderstand the problem?
The announcement specifies that you can only visit each cell once.
"The doll should visit all cells without obstacles exactly once"
Thanks for your answer!
But If the problem becomes what I said, what's the answer?
I have an idea, but I don't know whether it works / how to prove it.
Congratulations to you and me both for our first contest.
Great conto
Hello MikeMirzayanov and Cirno_9baka. So my friend dewitast got an issue that her rating was changed when she participated in this contest. You can see that, she is not eligible for div 2 rated contest (she already master when joining this contest, of course you can check it by yourself in the last contest in her profile). She already contacted both of you and she haven't hear any good news from you. Well she is not a vocal person, so I'm here to help her. Thanks :)
I was checking the solution for problem D of some people and I found that one of the accepted solution fails the following input.
Input:
2 2 1
1 2
This input should give an output "No", as I have checked with some other accepted solutions. But the following AC submission gives "Yes" :|