~~The jury solutions will be updated later.~~

The jury solution is updated now.

Idea: waaitg

Tutorial is loading...

**Solution (Imakf)**

Idea: waaitg

Tutorial is loading...

**Solution (waaitg)**

Idea: smg23333

Tutorial is loading...

**Solution (smg23333)**

Idea: waaitg

Tutorial is loading...

**Solution (waaitg)**

Idea: Imakf

Tutorial is loading...

**Solution (Imakf)**

Idea: waaitg, Daniel_yuan, isaf27

Tutorial is loading...

**Solution (Daniel_yuan)**

Idea: Imakf

Tutorial is loading...

**Solution (Imakf)**

Idea: waaitg

Tutorial is loading...

**Solution (waaitg)**

Speedforces.

More number of people would have solved Div2 D/ Div1 B if clear problem statement was made in starting itself .

Absolutely.

for problem 1B if the input is 1 1 10000000 1 shouldn't the answer be 10000001

I got WA in div2 C because i was not using set precision. Why is it so? Please explain!!

ауызынды жапшы сойлей береди екенсин

Such a fast editorial! That's great! :)

Sorry for making the second comment meaningless :(

Second comment:)

Oh no I'm third :(

Looking at my poor contribution, it's a painful lesson for me :(

Well, your comment isn't as meaningful as your handle.

Task C have one max test???? My random solution got AC. So weak...

Hacked. Sorry for weak system test :(

Savage

I believe next time you will make them strong! Wish you luck.

Am I the only one who read

instead of

(Div2D/Div1B)

Same here, That means I had read the wrong question and still my code passed the pretests... :) Very weak pretest for div2 D :(

same with me bro.

Me too, got 4 times WA for this.

Hey, if you don't mind, can you explain what is meant by longest monotone segment? I can't find the explanation of the term anywhere on google.

Longest monotone segment means the longest segment in which all the elements in the segment are increasing or decreasing. but not both. For example:

So the longest monotone segment is the longest of such segment. I don't know if any neighboring element can be the same, but that doesn't matter for the problem since all the elements are guaranteed to be distinct.

But solutions will be exact same except the l%2 condition in the last

me too bro

Same :(

Oh,a sad story.

Interesting as problem 1C is, 1B is really a bad problem. But I do hope the next competition can be better.

losing sleep due to bricking problem a. quite literally

It will be better if the data of div2D/div1B are multi-tests.

Why would it have been better? Is it because that would have allowed to fit more cases in pretests?

Yes. 11 pretests on a YES/NO problem with a lot of casework is very obviously a bad idea but for some reason the authors didn't use multitest.

I felt sad that I ignored the description "Magically, any two empty cells have no common points (neither edges nor corners)." in div1 C.

Yes, now I read the editorial and came to know about that. Can it be solved for sharing corner points? Or even for sharing edges? (initially assuming it is not forming a cycle?)

I got TLE in C just for taking inputs as double in my code. The same code when I just changed the input type from double to long long it got AC. Help!! Thanks in advance. Links to the TLE and AC code is given below and changes are also specified by comment.

Same thing happened to me too. But I couldn't fix it during the contest.

Same. I just got 6 TLE with correct algorithm just for that and lost the points for C.

It takes more time to take input as Double in C++ and even it takes more time to sort it.

I am not sure, but afaik, although both "long long" and "double" are 8 bytes, the processes on double are way slower, and the reason is the precision problem. I don't think you got TLE because of input, but because of the operations. You use "double" typed vectors, you add elements to them, then sort, multiply them, take the square root. These operations may have overwhelmed the computer(server).

I don't know why, but Kotlin doesn't care what to store and what to operate with (Long or Double). That's fun btw, cause c++ working slower with doubles.

With many participants happened this: one of the solutions got TLE, the other one got OK, but they have the same logic (problem Div.2-C).

Why??

i'm think for long double or double sort work very low.

just don't rewrite it in every test case and try to use '\n' instead of endl

can anyone explain to me why the answer in D is only 1 or 0?

The key is that Qingshan has two ways to win. The first is that Qingshan can't move for the both sides of it are greater.In this way, the length of monotone subsequence is important. The second is that Qingshan meets Daniel.It means that Daniel can block Qingshan's way and meet in the middle of a monotone subsequence. Understand that and you will solve it. :)

Can you elaborate more? Why longest monotone is important here?

If there are two longest monotone and they have the same position, the position whose value is greatest in the monotone is available when the length of the longest monotone is odd(Try to imagine when the two meet). Otherwise, Daniel can always choose the position whose value is least in the other longest monotone (If it isn't exist, Daniel will choose the position near by Qingshan chosen to make Qingshan can't move to the longest monotone), and Qingshan will always lose.

I mis read the question 1495B.

Thanks for the contest

We assume that both player plays optimally it includes well choosing the start, if 4 is the number on which is Q, D goes on 3 and no move is possible for Q.\ if 4 is the index D goes on index 1 and either Q move to 3 D move to 2 and Q is stuck either Q goes on the other side and D can walk 3 moves Q too, and Q is stuck, so Q loose if D choose well where it starts

Yes, Thank you for the clarification sir.

In Div_2_C

109615476 : This solution was accepted. 109601607 : This one got me TLE. Can someone please help me understand why did I get tle?

turns out inputting a double is slow as hell in cpp. as the values were integer, you should have input them as integers in a first time.

Thank You! I'll make a note of it.

What happened with the solution of 'BFS Trees'?

What is longest monotone segments?

subarray which is either strictly increasing or strictly decreasing .For example take array 2 4 6 5 3 8 7 4 3 . Here 2 4 6 , 8 7 4 3 are some of the monotone segments . 8 7 4 3 is longest monotone segment.

Can Any One Help Mi That Why I Get TLE On Today's Problem C

Here Is My Submission.109634972

use long long int instead of double for a and b and x and y, double (and long double) are slow to read and to sort

now it's accepted. thank's a lot i learn new thing and i will never forget it

Could you please tell me that why double is slower than int(as sort).

Thanks a lot,even I got to learn a new thing , this thing costed me 3 submissions during the contest as I wasn't aware of this fact

I cant see solution for div1 a (smg2333) not enough rights

Sorry, I'll fix it soon.

Can anyone explain problem Div 2 D? The editorial is kind of overwhelming for me. Thank You in Advance!

Think of the permutation as hills and valleys. Notice that the first player always has to start at the top of a hill, as only top of hills will have both adjacent points smaller than it, otherwise player 2 would pick the smaller adjacent side forcing player 1 to pick larger side, hence losing. Now the first player would want to descend, so he will pick the mountain which has the longest (and equal) descent on both side out of all mountains( if he doesn't, then player 2 can pick a longer ascent, and player 1 will run out of moves before player 2).Also there should only exist one unique mountain with the longest sides, otherwise player 2 can ascend the other mountain and since player 1 plays first, he will be the first one to exhaust all his moves. Both sides should be equal so that player 2 can't intercept us at one side(if only one side is longest, player 2 would be able to choose in way so that player 1 loses). Now the length of this descent should be odd, since whatever side player 2 chooses, we can go in the same direction, and he will be the one running out of moves first. This is the only case player 1 wins Edit: logic was wrong initially

As fast as flash.

It seems that the submission of F is not visible.

Sorry. Now it's fixed.

Another suggestion: Use name Alice for first player and Bob for second player. This time Quishisomething and Daniel where not so bad, but still I had to read severeal times before being able to memoize who is first, who is second. Later one of the player is referred to as "she"...what might be hard to understand depending on cultural background.

Alice and Bob is simply less confusing.

Can someone explain this?

Author's English skill still has space for improvement.

j is the parent node of i in the required tree. It must satisfy the condition given because required tree is a BFS tree of both x and y. Such j might not exists for some i.

Thanks

I am still struggling to understand Div2F's statement, can any one please explain what does "Given a graph, we define f(x,y) to be the number of spanning trees of that graph that are BFS trees rooted at vertices x and y at the same time." mean?

PS. got it

For 1495E.

Why this graph has at least 2 simple paths between 2 empty cells.

Is there anything wrong with the spj?

I guess you might get a single piece of data from multiple sets of data using C++ output, but pay attention to whether or not your code is affected by the fact that multiple sets of data are not cleared, which I do...

Maybe I have the problem. You can see my submission. I can't find anything wrong.

https://codeforces.com/contest/1496/submission/109645526

Oho, isn't that the same mistake?

If you look at the commit record, I just put a clean on your code and it was accepted.

This is your code.

This is my code. (I put a clean on your code)

So it's important to remember to clear out multiple sets of data : )

What a pity!/kk

Sorry, I mean 1496E.

@Imakf Can you show me the spj for the problem or just tell me why I'm wrong?

your graph didnt gurantee any two empty cells have no common points (neither edges nor corners).

This isn't the input case but my answer!

What a pity,maybe it's really his problem

It is clearly a tree. In which submission you hacked the spj?

https://codeforces.com/contest/1496/submission/109646267

I only swapped n and m and I got an accepted.

https://codeforces.com/contest/1496/submission/109647174

What is the difficulty of Div2 C as your opinion?

1300 As per me

Nice guess

Thanks Sir!

For Div2 D /Div 1 B Why This Testcase giving ans=0 while ans should be 1

N= 11

5 6 9 8 1 2 3 11 10 7 4

ans=0 is right. why it should be 1 ? explain. there is no index where we can win.

For index =7 (0 based ) When value is 11

If first player will start at index 7 then second player will start from either index 4 or index 10. then first player can't win. from index 7 if first player choose to go 6 then second player will move 4 to 5.and then first player can't move further.

or if first player move in the right (first player move, second player move) (7->8,4->5) (8->9,5->6) (9->10,6->7) and now first player can't move. So in both situation player first can't win.

Oh sorry my bad I read condition for y wrong

So many were did the same.

In Div.2C, why can we turn any point (x, y) to (|x|, |y|) without changing the answer?

Because distance will still remain same since x^2 = (-x)^2

when i am taking input in long double is giving tle https://codeforces.com/contest/1496/submission/109591967

while long long int gets accepted https://codeforces.com/contest/1496/submission/109594626

is long double making such a huge difference in time? and why it is not getting memory limit exceeded instead of time limit exceeded?

It takes more time to take input as Double in C++ and even it takes more time to sort it.

why is it so?

Sorting a double number requires sort its decimal number which is very big

Correct!

I tried algebra bash for div2 C

I tried implementing DFS for E which failed on some edge cases and now I am wondering, is there actually a solution with DFS?

A problem in Div1A when I use 'printf("%.10Lf", ...)' to print a long double, it seems something wrong with it on the platform, but it does work correctly on my com. So could someone help me on how can I use 'printf' to print a long double ? thx for your help !

transform long double into double to print it

For TASK 3 div 2, i wrote a solution with double as my vector type seems and it gives TLE on TC:- 4 but if i change double type to int it passes with time 124ms can anyone one tell me why it is happening

109668126 Code using double

109668230 Code using int

It takes more time to take input as Double in C++ and even it takes more time to sort it.

I suffered from the same issue due to my carelessness. Float operations are (10-20 times) slow than their integer counterparts. For this problem, the hotspot of time usage is clearly the sorting, which invokes the comparision for O(n log n) times.

Thank you for turning me green again ;)

The pretest for div2.D is too weak!

Can someone explain the sequence of moves in the following test case for Qingshan to win? Thanks!

If Player 1 is at index 1 -> Player 2 can be at index 2

If Player 1 is at index 2 -> Player 2 can be at index 1

If Player 1 is at index 3 -> Any position of player 2 will be loosing position or him. i.e if

1) player 2 decides to be at index 4

player 1 -> index 2

player 2 -> index 3

Player 1 -> index 1

Player 2 cant make move.

2) Player 2 decides to be at index 5

player 1 -> index 4

player 2 cant make move

3) Same in case of index 1 and 2.

If Player 1 is at index 4 -> Player 2 can be at index 5

If Player 1 is at index 5 -> Player 2 can be at index 4

Div2 C. Why my submission 109604661 109606220 failed with setprecision(11) and setprecision(16) with

`double`

. This infrustrates me to the no end and finally passed with setprecision(15)..Does anyone have an explanation for this? I thought a setprecision(11) could meet the requirement.

It's because that for the input array you used

`std::vector<int>`

instead of`std::vector<long long>`

in the previous submissions, nothing to do with precision. More accurately:This will cause an integer overflow, and the result might be a negative number, which you soon called

`sqrt()`

on. And this will return`nan`

, as shown on the judger.Okay , so here is thing, I misread Problem div2(D)/div1(B) and solved some different problem and later realized that I screwed up the problem statement. I thought that whichever index the player steps on becomes his territory. Meaning, the other player can never approach this index ever. Even though, the original problem is different from the one I assume it was, I consider this alternate problem is also fun to solve.

The same happened with me too.

For div1D, consider f(x, y), what if there are multiple shortest paths between x and y? Tutorial skipped this.

In this case, answer is always 0?

Yeah,because if there are multiple shortest paths between x and y, there must be an point i,which doesn't satisfy the condition in the tutorial.

However,you can just consider the situation that an edge in the shortest path is contained in a circle.I think it's better to understand.

Could someone help me with the problem 1C/2E? I get WA on test 3, but I don't know where goes wrong...Thanks in advance. my code

Oh, thanks!!I'm careless:(

Someone kindly elaborate Div2F please!

Can someone tell Div1C / Div2E : Will answer always exist regardless whether initial empty cells share a corner or edge or not? I feel this is true, but cannot prove it. And any ideas on how to solve in that case? Using Disjoint Data structure?

Edit: In general I guess there may or may not exist solution but I cant find example, and in general we may have to use backtracking if constraint in question was not given

No. Consider a chessboard-like input grid.

I think it works for this big chess, does it fail for higher ? Or maybe a different $$$n\times m$$$ grid ?

Wrong image here, refer followup replyThe edges between points (1,1),(1,9),(9,9) and (9,1) in your diagram form a loop, so there may be more than one simple path between two points.

ok if we let (1,1) with the flower, that is not empty the (1,1) cell?

Like this:

ImagePS. nvm

You can have a look at the following picture, it is unable to find out the legal solution, I proved it by counterevidence, but the process is more complicated, so I will not write it in detail, you can also have a try ~

This is nice I was also feeling it might fail for smaller chessboard!

Can anyone expain, why in Div.2 Problem D,

testcase -->

5

1 2 4 3 5

answer is 0.

If first chose position x(x\neq 1), then second chose position x-1. If first chose 1, second can chose any.

How is it obvious that the distance between $$$x$$$ and $$$y$$$ in the tree is $$$dist(x , y)$$$, since $$$dist(x,y)$$$ is number of vertices in the shortest path in the graph(there could be multiple paths)

To make it clear, "the tree" here means "a tree that is both a BFS tree rooted at x and y at the same time". So by definition, the length of the (one and only) path from x to y on that tree must be equal to the length of the shortest path from x to y in the original graph.

Can someone tell why this solution 109616067 is exceeding the time limit?

use scanf instead of cin and you will get ac 109754059

What will be the answer of Div2 D for 1 3 2 input. I think it should be 1.

It's 0 instead. Suppose Qingshan start at x = 2 (He can't start at x = 1 or x = 3 because he wouldn't be able to make the first move)，Then no matter which y Daniel chooses, Qingshan is definetely going to lose.

Just a public personal note that Div1D / Div2F was real "fun" to solve in non-C++, heh.

109775962 is my passing submission. Notes:

`D`

(distance) or`ans`

, or with an array of adjacency lists for the graph. (instead, edges are stored in`U`

and`V`

, sorted by`U`

and using the auxiliary array`P`

to point to the subarrays corresponding to each vertex)`a * b % MOD`

and uses addition and shifts instead, saves about 150ms over an equivalent solution with multiplication.I have an even faster submission: 109763945, but it relies on skipping modular multiplication for factors $$$0$$$ and $$$1$$$, and therefore optimizing on this relies on the fact that factors $$$2$$$ and above are limited in number, which is a heuristic that I couldn't prove.

Upd: even faster: 109780486. Modular addition (no multiplication or

`%`

). Shortcuts if it finds a $$$0$$$ factor, again, I'm unsure whether there is a way to defeat this optimization and make it run like 109775962.Neither edges nor corners need a better explanation.

Em...i think the Div1.E's description has a small problem. On the 4th line of INPUT, it says $$$p_{j-1}<p_j(2\leq j \leq n)$$$ but the truth is $$$(2 \leq j \leq m)$$$.

Now it's fixed. Thanks.

Taking input as a double is slow in c++ (my learning from Div1 A).

Alternate explanation for div2-F/div1-D:

Firstly, for a fixed root node, how many BFS-Trees exist?

Now let us consider the original problem (Common BFS-Trees for two fixed roots $$$s$$$ and $$$t$$$).

Observation: If there exist multiple shortest paths between $$$s$$$ and $$$t$$$. Then there exists no common spanning tree for $$$s$$$ and $$$t$$$.

ProofCan prove by contradiction, but its far easier and quicker to just visualize why this is true. Assume that for fixed roots $$$s$$$ and $$$t$$$ that there exist two shortest paths between them. This means that there exist two distinct nodes $$$p$$$ and $$$q$$$ such that $$$dis[s][p] + dis[p][t] = dis[s][q] + dis[q][t] = dis[s][t]$$$ and $$$dis[s][p] = dis[s][t]$$$.

Assume that there exists some common BFS tree $$$T$$$, This means that in $$$T$$$, both $$$p$$$ and $$$q$$$ are connected to both $$$s$$$ and $$$t$$$, and also $$$dis_{T}[s][p] = dis[s][p] = dis_{T}[s][q] = dis[s][q]$$$ and $$$dis_{T}[t][p] = dis[t][p] = dis_{T}[t][q] = dis[t][q]$$$. But this would imply the existence of a cycle, which is not possible in a tree. $$$\therefore$$$ our assumption is false and there exists no common spanning tree.

So firstly just check that there exists only one shortest path between $$$s$$$ and $$$t$$$. Ok, so now visualize the graph as a DAG rooted at $$$s$$$. We know that there exists only one shortest path between $$$s$$$ and $$$t$$$, and that shortest path

mustbe picked in any common BFS tree of $$$s$$$ and $$$t$$$.What about the other nodes? Other nodes are either children of $$$t$$$ in the DAG, or they are not. Now we can divide these nodes into two disjoint DAG's, and the problem reduces to the original problem (finding number of BFS trees for fixed root). Also, we need to remove edges from one DAG to another, because picking edges from them will result in nodes being farther from $$$t$$$ than the required distance.

Implementation: link