But you are not thinking about singles who would have received negative delta.

hackers are testers :D

statements :)

Can you please shift to YouTube, you'll certainly get a larger watch base over there. Who watches coding videos on twitch anyways?

Can we expect strong pretests? It wouldn't be very pleasant to see FSTforces. :) (FSTforces makes +136 for me) forgive my poor English:)

A Valentine's Day date with codeforces. :)

1379A - Acacius and String is rated $$$1500$$$.

You want negative delta?

Is it (not true) that the round is Rated? => Is it false that the round is Rated? => is this contest unrated? This is what we expect from div2. A problem.

welcome and good luck

huh

for DP check this out

you can solve problems at https://cses.fi/

I think starting from E they look nice to me

Face reality: "Educational" means "to boring to be used in standard contest".

2*n-1 not 2*n+1 :)

it is (sqrt(2*n-1)+1)/2-1

And easier than C as well ...

I just searched it on Wolfram Alpha

Yeah for me D was easier than B and far easier than C. How did you guys solved C?

I misread the statement of problem B :( And stuck on it for an hour...

From the two formulas it follows that $$$c=b+1.$$$ Moreover, difference between $$$c$$$ and $$$c-1$$$ must be a square

• `It involves a bit of mathematics. So you have 2 equations

1) a^2 + b^2 = c^2

2) c = a^2 - b

• From equation 2, find the value of a^2, which is c + b and then substitute it in equation 1. From there, you will a relation of the form c * (c-1) = b * (b+1). On careful observation, you will see that this can be true only when b = c-1. So, the problem reduces to counting the number of pythogorean triplets having the length of the hypotenuse and the longest leg differing by 1.

• As it turns out, such a triplet has the form (2n + 1, 2n^2 + 2n, 2n^2 + 2n +1). Here is the hypotenuse is of the form 2n^2 + 2n + 1 and hence you can easily loop until you reach the limit.

• Link to my submission: https://mirror.codeforces.com/contest/1487/submission/107441210

Pythagorus theorem -> a*a+b*b=c*c , a<=b<=c

and eqn in question -> c=a*a-b

solving both equation we will get c = b+1

so let b = m then c = m+1 and a = sqrt(2*m+1)

since c<=n

so m+1<=n => m<=n-1 => 2*m<=2*n-2 => 2*m+1<=2*n-1

sqrt(2*m+1) <= sqrt(2*n-1)

so our ans is number of odds(since 2*m+1 is of odd form) less than or equal to sqrt(2*n-1)

but we have to subract one from our ans since sqrt(2*m+1) cannot be 1(if it is 1 then m = 0, which is not possible).

Hope it helps.

c=a2-b

a2=c+b

3*3=9=4+5

5*5=25=11+12

7*7=49=24+25

9*9=81=41+40

Wrong answer on test 1 doesn't give penalty

You don't need a segment tree, just a set that contains the previous dp values. For each dish, remove the dp value of dishes that don't go well with it and insert them back afterwards.

We can see that m_i is less than 2000000, so we just sort the DP value of the last course. Then we just select the minimum DP value (and skip the DP value if they can't get well with each other) for each current course and generate a new DP value.

We can solve E with brute force. For each vertice i from 2 to 0 brute the minimum valid vertice (i + 1). And it work O((n + m) * log2(m))

Does this really constitute searchable? Its literally just substituting and expanding the equation.

Exactly :(

Well, the main reason is that, on 3 dishes, you can iterate on the second one and take the cheapest first and third option that goes well with it.

How do you know that pretests are strong?

How you solve E if you can tell the idea

Yet another round like [some]forces

It teaches you "educational rounds are not educational" XD

Educational contests teach you to hack other's codes. This is useful for debugging own code

I wasn't able to code completely but i think following would have worked :

Consider a,b,c,d as arrays consisting of cost of first course, a second course, a drink, and a dessert.

Now in array b , for each index we can add minimum cost in array a.

Similarly for each index in c we can add minimum cost in array d .

In both above we need to consider only those pairs which are not connected . It can be done with multiset .

Now for each index in b find minimum cost in c and take the minimum.

You can use multiset to get the minimum value. While looking at the i'th element delete the values of the food which doesn't go with i'th element. Now get the minimum value in multiset. At last of i'th step add those deleted values back into multiset.

wait, your solution's time complexity is O(t * sqrt(n)), and in the worst case it has to do ~3*10^8 , how can it pass?

I've submitted your solution and here is the result:

• GNU C++11(or C++14): >2000ms

• GNU C++17: 1965ms (surprised face)

Probably some slight difference in the compilation process based on the chosen standard that leads to a small difference in runtimes, or just normal run to run variability, since you are very close to the limit.

Success in E today depended on how fast you solve A,B,C,D. It was bit lengthy implementation due to large inputs.

Write macros/functions so that you can input common data formats without much typing.

C and E where less complecated than B, but all 3 of them index fiddling.

same here bro b ruined it

I used this https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

The pythagorean formula, $$$a^2 + b^2 = c^2$$$, and the given formula in the problem, $$$c = a^2 - b$$$, are enough.

Pythagorean Theorem: $$$a^2 + b^2 = c^2$$$. Then you couple that with $$$c = a^2 - b$$$ to solve for bounds on the variables. I thought it was strange they didn't include that in the problem statement, but I guess problemsetters deemed the theorem fundamental enough, since most people learn it in primary or secondary school.

c^2 = a^2 + b^2
c^2 = a^4 + b^2 — 2*a^2*b
a^4 — 2*a^2*b = a^2
a^2 (a^2 — 2*b — 1) = 0
b = (a^2 — 1)/2

So the maximum value of n was 1e9 so the max value of a would-be sqrt(2*n + 1) would be the order of 1e5(let us call this N). We will maintain 2 arrays, pref[N] and num[N].

Loop a from 1 to N and calculate b and c. If b and c are integers and c <= 1e9, put num[a] = c and pref[a]=pref[a-1] + 1. Otherwise num[a] = num[a-1] and pref[a]=pref[a-1].

For each test case binary search on num and get the index ind such that num[ind] <= n and answer would be pref[ind]. I am leaving the edge cases to you.

The answer is just (int(sqrt(2*n-1))-1)/2

You don't need a formula besides the ones provided. Just need to know how to substitute one equation into another and do some algebra.

i used dijkstra for E and got MLE as well.

min function takes two arguments of same type and returns the minimum value of them. It uses "less than" operator to find the minimum. Here if v is a vector then "less than" operator is defined for vector iterator. So it works.

Same here...haha

It's leet written in leet the langage where you change letters to other character in order search for words doesn't work

Lol, Last 19sec saved you from much damage. Kudos for getting AC at 1:59:41.

The entire state space your Dijkstra routine is exploring is of size $$$O((\log n)^2)$$$. Consider the number $$$x = 9*\mathrm{curr}$$$, written with no leading zero. Then your two operations on $$$\mathrm{curr}$$$, viewed as operations on $$$x$$$, are:

1. invert every digit in $$$x$$$, or
2. subtract 1 from the leading digit of $$$x$$$, then add 1 to $$$x$$$.

Then it should be easy to see that from a given value of $$$x$$$, there are at most $$$2 \times 10$$$ values of $$$x$$$ that can be reached with the same number of digits, and at most $$$2$$$ values of $$$x$$$ with one digit less. These $$$2$$$ values will (up to inversion of digits) differ by either $$$9$$$ or $$$10$$$. Extending this idea, up to inversion of digits, the ways to remove the first $$$k$$$ leading digits of $$$x$$$ fit within a range of size $$$10k$$$. This leads to there being at most $$$20k+1$$$ of them, which leads to the $$$O((\log n)^2)$$$ bound I claimed.

EDIT: I made a dumb oversight initially, but the idea of this comment should still more or less work. I expect the constant factor is in practice better than what my revised argument suggests, by about a factor of 5.

We have 2 equations. 1) c^2 = a^2 + b^2 2) c = a^2 — b

If we substitute the value of c from 2nd eqn. to first eqn. we get,

a^4 + b^2 — 2*a^2*b = a^2 + b^2 ==> a^4 — a^2 = 2*a^2*b (By rearranging terms) ==> b = (a^2-1)/2 ==> c = (a^2+1)/2 (By substituting the value of b into eqn.2)

We can see that c>=b>=a. For c to be less than or equal to n, a<=sqrt(2*n-1). Also for b and c to be integers a should be an odd number != 1.

So the answer is number of odd numbers from 3 to sqrt(2*n-1)

Yes...use the same function to precompute the all the pairs till 10^9 and store a,b,c in different arrays let's say A,B,C..now for each n..check how many elements in C are <= n as because C will be holding the max element of each triplet of a,b,c. This is not the best method to solve this question but yes this approach works for given constraints.

The main idea is we can put the teams on a circle. Then if $$$n$$$ is odd team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-1}{2}$$$(with cylic shift). And if $$$n$$$ is even team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-2}{2}$$$ and tie with team $$$i+\frac{n}{2}$$$.

code

Solution. You can fill adjacency matrix with checkerboard pattern (if $$$n$$$ is odd), mirrored by main diagonal. Then every line and every row has the same sum. In case $$$n$$$ is even -- every team must play one game in a tie. Simplest way to put 'tie values' on adjacency matrix such that any two 'tie values' are on the same row/column -- put them on second diagonal by checking the sum of indexes $$$row + col == n$$$. Bus you also need to mirror values by second diagonal (only in case of $$$n$$$ is even).

  X -1  1  0
  1  X  0 -1
 -1  0  X  1
  0  1 -1  X
---
-1 1 0 0 -1 1
---------------
  X -1  1 -1  1
  1  X -1  1 -1
 -1  1  X -1  1
  1 -1  1  X -1
 -1  1 -1  1  X
---
-1 1 -1 1 -1 1 -1 -1 1 -1

You can solve C by induction.

XWLWL
LXWLW
WLXWL
LWLXW
WLWLX