## 1725A. Accumulation of Dominoes

Author: Pyqe

Developer: nandonathaniel

Editorialist: Pyqe

**Tutorial**

## 1725B. Basketball Together

Author: FerdiHS

Developer: muhammadhasan01

Editorialist: Pyqe

**Tutorial**

## 1725C. Circular Mirror

Author: Pyqe

Developer: steven.novaryo

Editorialist: steven.novaryo

**Tutorial**

## 1725D. Deducing Sortability

Author: Pyqe

Developer: TakeMe, Pyqe

Editorialist: Pyqe

**Tutorial**

## 1725E. Electrical Efficiency

Author: steven.novaryo

Developer: steven.novaryo

Editorialist: rama_pang

**Tutorial**

## 1725F. Field Photography

Author: Pyqe

Developer: Pyqe

Editorialist: Pyqe

**Tutorial**

## 1725G. Garage

Author: Nyse

Developer: Nyse

Editorialist: Pyqe

**Tutorial**

## 1725H. Hot Black Hot White

Author: Pyqe

Developer: steven.novaryo

Editorialist: steven.novaryo

**Tutorial**

## 1725I. Imitating the Key Tree

Author: Pyqe

Developer: Pyqe

Editorialist: Pyqe

**Tutorial**

## 1725J. Journey

Author: gansixeneh

Developer: gansixeneh, steven.novaryo

Editorialist: rama_pang

**Tutorial**

## 1725K. Kingdom of Criticism

Author: Pyqe

Developer: Pyqe

Editorialist: rama_pang

**Tutorial**

## 1725L. Lemper Cooking Competition

Author: Pyqe

Developer: steven.novaryo

Editorialist: rama_pang

**Tutorial**

## 1725M. Moving Both Hands

Author: Pyqe

Developer: Pyqe

Editorialist: rama_pang

**Tutorial**

Fast tutorial. Thanks. Btw there is two pointers solution in B. Adding two pointers tag would be great I guess.

How can you get 4 + (n * 4 — 3) / 3 just by 4 + 4a?

i did'nt got solution for problem m anyone pls help

Run shortest path algorithm.

Change the direction of all edges.

Run shortest path algorithm.

more detailed? pls

You wanna find a point x that has min minway(1, x) + minway(p, x). Also, we change the direction of all edges, so now, minway(1, x) + minway(p, x) = minway(1, x) + minway(x, p'), where p' is a new point for p, that shows, that p' is p in graph with reversed edges. We can see, that every point on the shortest way from 1 to p' has min sum of that 2 ways.

I don't know where my code is wrong. Can you help me find out the details? thank you 171057638

My submission is pretty similar to yours, maybe it can help.

Submission

minway(1, x) + minway(p, x) = minway(1, x) + minway(x, p') how it is equal i am not getting. can u please explain

p' is a point in graph with reversed edges, so, we can not to go from p to x, we can go from x to x' and it costs 0, and then you can go from x' to p' with reversed egdes with new nodes

For E, what's the intended way to build the auxiliary tree? We used small to large merging but that was

`O(n*log(n)*log(A)*map)`

which seems susIt is actually possible to build all sparse trees simultaneously using small-to-large, but the time complexity is worse. The intended solution uses an algorithm that runs in $$$O(|S| \log N)$$$ for each set $$$S$$$. The algorithm is as follows:

You can optimise it further to make the total time complexity $$$O(N(\log N + \log \max(A)))$$$. But the time limit is not that tight that even the small-to-large solution is able to pass.

Ah thanks, that's really cool. Haven't really seen many problems with this "auxiliary tree" idea, so its nice to learn good techniques for it.

On the third task O() calculates in wrong way, min(Cntpair, m) = O(n), so O(n logn), or wthether we check case, where min(CntPair, m) = m, so in that way it'll be better if we say that it's O((n + min(n, m)) * logN) or something like that

L had weak testcases, we submitted L very late and only realized after the contest we forgot to check whether every element of the prefix sum was non negative and it passed

the submission 170883681

Problem: 1725B - Basketball Together

Solution: 170864702

In this block of code:

when I set n = 1, D = 10^9, and a[i] = 1; in theory it should run in 10^9 steps, which will give a TLE verdict. But when I use "Custom Invocation" to test it, I found that it only ran in 500ms, which is way below the time limit. Why did it happen? Is it because of the codeforces judging machines, or is there something that I'm missing?

It probably just runs that fast. The hot path only includes an add, a compare, and a conditional jump, which is < 3 cycles with branch prediction. Computers run at a few GHZ, so 500ms sounds right.

The $$$10^8$$$ things/second heuristic is just a heuristic for usualish groups of operations, you can do better if u have a fast loop body (especially if the compiler avx-ifies, which might be happening here).

To see exactly what is happening u can try putting it in https://godbolt.org/ with the correct compiler version/flags.

Our team enjoy solving this problemset. Especially for Problem L. We didn't think it could be done using prefix sum. Very nice problem

why 1 and 4 cannot be expressed as $$$(b^2−a^2)$$$

we can write (b^2-a^2) as(b-a)*(b+a)

// proof for 1 can not be expressed in terms of b^2-a^2so the min positive value of a we can take is 1 and for b its 2 as (b>a) as stated in the problem so, (b-a)=1; (b+a)=3; and their multiplication would give us 3 as the min value which can be expressed in terms of b^2-a^2; and one more conclusion can be drawn is that after three all odd numbers can be expressed in the form of b^2-a^2(because we can express every odd number (lets say a)as 1*a;and a can always be represented as a sum of 2 consecutive numbers which are always odd****lest take a=4 ,b=5;b-a=1;b+a=9;9*1=9;that is odd)// proof for 4 cannot be expressed in terms of b^2-a^2to make equation even we have to make (b-a) even first so in order to make that even min value of a we can take is 1 and for b is 3 so, (b-a)=2; (b+a)=4; and their multiplication will give us 8 that is the minimum even value we can achieve and from here we can draw one more conclusion that all the even values will be multiples of 4 as no matter what we take values of a and b whenever (b-a) is even (b+a) would also be even(because to make the diffrence of 2 numbers even their parity should be same and if we add same parity numbers then result is even)so that would make the result divisble by 4Thank U

For those curious about the $$$O(1)$$$ formula for problem G (Garage):

SpoilerOne could verify the $$$N > 1$$$ case by noting that values $$$N = 3k + [ 0, 1, 2 ]$$$ map to the correct values $$$f(N) = 4k + [ 3, 4, 5 ]$$$ respectively.

I could come up with this result by building a sequence,

I added the difference between b^2 and a^2 in the sequence as follows:

4 — 1, 9 — 4, 16 — 9, 9 — 1, 25 — 16 ..

by listing the "difference between squares" in nondecreasing order,

I got the sequence:

3, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, ,27, 28, 29, 31..

I noticed that the first number "3" doesn't follow the pattern, so I assumed it was a special case,

but the remaining numbers follow a consistent pattern that I came to figure out as:

"3 + 4 * (N // 3) + N % 3"

thanks a lot . i was struck int this problem from last 4 hrs. your comment helped me to solve the problem. Can you tell how you get the INTUITION about such a complex pattern?

It is given in the problem that a, b and x are all integers.

we know that a^2 + x = b^2 (because x is the area of the square and it's the side squared)

so x = b^2 — a^2

and as I said in the beginning, a and b are integers

so

b^2 and a^2 must be numbers that have an integer square root(squares).all what is left is that we

look at the pairs of numbers that have integer roots (the squares of integers) and find the difference for every pair,sort them in a non-decreasing order, then we find the Nth number that is x.I hope that this was a clear illustration, forgive me for my bad English.

Thanks a lot..btw ur English is better than mine

Isn't F's TL too tight?

I think problem J has insufficient tests. In particular, I found solutions (including mine) that get AC, but give an incorrect answer to the following simple test:

As far as I understand, the correct answer here should be 106.

I try to solve this problem M. Moving Both Hands ,but it always gives me WA , please anyone help me,

i'am stuck in this problem about 2 weeksand can't figure out why my code is wrong?Here is mycode,I used dijkstra twice for each direction of the graph.

You need to make sure

queis a heap before running dijkstra for the second time. 173757547great thanks to you, I really ashamed from myself to stuck in this problem for long time becasue of this trivial coding line

`heapify(que)`

can you please explain your approach?

node 1to every node to calculate the distances from the first hand.directionof every edge in the graph to make the graph ready for the other hand.except 1to get the min distance.AC https://codeforces.com/problemset/submission/1725/184436818 Thankyou