Hello!
On December 13th, the ICPC Northern Eurasia Finals (previously known as NEERC) will take place. The competition will be held at several venues: St. Petersburg, Novosibirsk, Kutaisi, and Astana. Almost 300 teams will participate in it.
We invite you to join the online mirror of the competition: 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred). It will start at Dec/13/2023 10:35 (Moscow time). We recommend participating in teams, but experienced individual participants will also have fun.
The duration of the competition will be 5 hours. Of course, the round is unrated.
Good luck!
the link of the contest seems to be wrong
Thanks, fixed.
It is not Almaty, it is Astana
Fixed, thanks
omg how F
1vs3 is so tiring.
Upd: I have made a proof here
I upsolved this problem with iteration method 237083785, but I can't prove why its convergence speed is fast enough. Nevertheless, following is my solution.
First, we have the game procedure:
Thief moves to a leaf, cause staying at a non-leaf vertex won't be better than any leaf in it's subtree
Thief stays at the leaf until police reaches a leaf. If thief moves to another leaf during the police move, he could have move there in 1.
Police chooses another leaf and go directly to it, because he knows that thief's best move is waiting on a leaf
After police reaches the leaf, if not caught, all other leaves are accessible to thief. Thief select a vertex based on the leaf police is at and move there, then return to 1.
We can see from the above procedure that non-leaf vertices are irrelevant after the first step, so for the following discussion, vertices are all leaf.
We denote the expected moves that police catches thief starting from leaf $$$u$$$ by $$$E(u)$$$, denote the probability that thief moves to $$$v$$$ if police is at $$$u$$$ by $$$p(u,v)$$$. Then, thief must distribute $$$p(u,v)$$$ in a way that no matter how police changes his strategy, $$$E(u)$$$ will not be larger. In this case, no matter how police chooses, $$$E(u)$$$ stay the same. Thus for $$$u$$$ and every other leaf $$$v_i$$$, we have
$$$E(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$
We try to solve it by iteration method, which means calculate new $$$E'(u)$$$ by $$$E(u)$$$ in the last round, i.e.
$$$ E'(u)=dis(u,v_1)+(1-p(u,v_1))E(v_1)=dis(u,v_2)+(1-p(u,v_2))E(v_2) = \dots$$$
Then, $$$dis(u,v_i)$$$ and $$$E(v_i)$$$ are all constants, the only variable is $$$p(u,v_i)$$$. Hence, we denote $$$x_i$$$ by $$$p(u,v_i)$$$, and the above equation can be rewritten as
Then we have
For the first step where police starts from $$$s$$$, we have the same conclusion that $$$E(s)$$$ stays the same no matter how police moves. Hence, we can calculate $$$E(s)$$$ by the same equation above.
when would we be able to see other's solution or would there be any editorial?
why did the submit button vanish after the contest?
I try to submit and it says contest is over maybe we have to wait for a while.
How to solve G / H?
Use a segment tree to maintain the answer. Noticed that we have to do recursion for one side, so the complexity is $$$O(n\log^2n)$$$
Optimal structures only contain chains and loops. Enumerate components and endpoints, then topo sort.
J is matrix exponentiation?
No. You are required to find the number of solutions to $$$a_1x_1+a_2x_2+a_3x_3=t$$$ where $$$x_i$$$ are given and $$$a_i$$$ are variables. So the key idea is to fix $$$X=a_1 mod x_3$$$ and $$$Y=a_2 mod x_3$$$ and find the number of solutions for this $$$(X,Y)$$$. Suppose $$$Z=(t-Xx_1-Yx_2)/x_3$$$. Then any solution for this $$$(X,Y)$$$ is of the form $$$(X+t_1x_3,Y+t_2x_3,Z-(t_1x_1+t_2x_2))$$$ where $$$t_1,t_2 \geq 0$$$. Now the number of such pairs $$$(t_1,t_2)$$$ for which $$$t_1x_1+t_2x_2 \leq Z$$$ can be found in $$$O(x_2)$$$ by fixing $$$t_1 mod x_2$$$ using some math giving a total complexity of $$$O(x_2x_3^2)$$$.
I see. Thank you.
Yes. Basically we want to find [x^n](1 / ((1 — x^a1) * (1 — x^a2) * (1 — x^a3))) which is f[N] for f[0] = 1, f[x < 0] = 0 and f[N] = sum of -f[N-i] * [x^i]P(x) for i > 0, P(x) being (1 — x^a1) * (1 — x^a2) * (1 — x^a3). This is due to the ties between linear recurrences and generating functions, for functions of this type the denominator being the reverse of the characteristic polynomial of the recurrence.
Will the following approach be correct? Choose some parameter P then compute matrix for every different triple and every power divisible by P. Then for each query solve it with trivial dp for $$$O(t / P)$$$ complexity and you start with precomputed matrix.
I don't see why not simply doing binary exponentiation.
Sorry I didn't understand your approach well. I mean solution where you optimize 3 x t dp with 48 × 48 matrix which seems to be TL
Oh I didn't think about it possibly being TL. Then yeah you possibly could precompute powers of 2 for sums that are too high. By doing that we can simply multiply the matrices by the column matrix, reducing the O(SUM^3) multiplication to O(SUM^2). I solved it by using the "How to calculate k-th term of a linear recurrence?" part from this https://codeforces.net/blog/entry/61306
Actually my first attempt was TL as you said, but I printed the matrix out and find out there is at most 100 non-zero positions in the matrix, so I added break 237013217 and passed.
I forgot to notice that you should pick $$$P$$$ in optimal way(something close to the square root)
how J and when tutorial
ax + by + cz = N as we know, case for K = 1 and K = 2 pretty standard so I won't explain
u can calculate L = LCM(a, b, c)
now I say that I iterate on m = min(x, y, z)
now still m doesn't have very good bounds, but what I can observe is
if u have answer for m, u can calculate answer for m + L, m + 2L, it will come out to be arithmetic progression of a kind, still it will be some casework but this is the outline
so u have to iterate from m = 0 to L — 1 and calculate everything using formulaes
I just handled cases, when x = m, y, z > m, x = m, y = m, z > m and so on
thank you
In Problem D if type can be 1 or 3 (when k is equal i.e. mod==2) then print 3 will get WA on test 3. Rank1 faced exactly the same issue in contest. I wonder if the problem writer of D even didn't write an spj. It is a total mistake.
How to solve C or I or F? qwq
I is simply a matter of doing the math and coding as far as I can see. Do a rotating 2-pointers thing that keeps the edges that will define the height of the water surface while rotating the polygon, then it's a matter of doing whatever integration thing that results from that. There's a part that's integrating cos(x) * a and I hope that the other part isn't that much harder, my intuition says that it might simply be P(x) * cos(x) for a polynomial of low degree P(x).
Open for upsolving please!
Done!
thanks a lot!
Could you also allow viewing others' submissions from the contest?
+
how can i subit my code after the contest?
We came up with strange matrix exponentiation solution for problem J.
Start with naive DP solution: $$$dp[i][j]$$$ is the answer for $$$j$$$ limbs considering only first $$$i$$$ species.
$$$dp[0][0] = 1$$$
$$$dp[i][j] = dp[i-1][j] + dp[i][j - L_i]$$$
$$$dp[s][t]$$$ is the answer
In order to calculate $$$dp[i][j]$$$ we only need to keep track of $$$dp[0:3][j-L_i:j]$$$. Encode this 2d $$$dp$$$ slice as a vector and build the transition matrix $$$T$$$ that shifts $$$j$$$ by $$$+1$$$. Solution is then classic matrix exponentiation optimization: $$$v_0 \times T^t$$$.
The problem is: matrix max size is $$$48 \times 48$$$ $$$(3 \cdot 16)$$$, which is too large. In order reduce it's size let's optimize the first layer $$$dp[1][:]$$$, it has simple periodic pattern $$$dp[1][j] = 1$$$ if $$$j \,\%\,L_1$$$ otherwise $$$0$$$
Computing second layer $$$dp[2][:]$$$ is similar to the first, but also requires periodically add $$$1$$$ from the first layer. So instead of calculating the first layer, let's add source of ones to the vector and rearrage matrix transitions to add ones when needed.
We will now have two transition matrices $$$T_0$$$ and $$$T_1$$$. $$$T_0$$$ is used when $$$dp[0][j] = 0$$$, $$$T_1$$$ is used when $$$dp[0][j] = 1$$$. We will have to apply this transition $$$t$$$ times, so the final formula will look like
$$$v_0 \times (T_0^{L_1-1} \times T_1)^{\lfloor t / L_0 \rfloor} \times T_0^{t \,\%\, L_0}$$$
Max matrix size is now $$$33 \times 33$$$ $$$(16+16+1)$$$ which is good enough to get about $$$h \cdot 33^3 \cdot \log t \approx 9 \cdot 10^8$$$ operations for $$$3$$$ sec TL. My solution with straightforward matrix implementation uses $$$\approx 900$$$ ms with
Ofast,unroll-loops
andtarget avx2
(or $$$\approx 3900$$$ ms without them).Submission: 237096800
how A? I have no idea with it.
Tutorial, if anyone is looking for it
Does anyone have any formal proof or intuition for problem D's solution?
why checking for b^k modulo n works?
Powers of b modulo n work in one of 3 ways:
There's some positive k such that b^k = 1 modulo n. This happens when gcd(b, n) == 1
There's some positive k such that b^k = 0 modulo n. This happens when b is divisible by all primes that divide n.
All other cases, which means that b is divisible by some prime that divides n but not all of them.
For case 2 it's simply what happens when we use a "divisibility test" for 2, 5, 10 and so on in base 10.
For case 1, we must divide the digits of the number in such a way that the coefficient of the digits are the congruent to their own coefficient without the division. What I mean is that a number can be written as sum d[i] * b^i and we must choose the division according to the problem in such a way that c[i] * d[i] = b^i * d[i] modulo n, c[i] being what we end up multiplying the i-th digit with after dividing the number under some rule of the problem. From here I think it'd be good for you to think about how to explain it splitting into two cases: the alternating one and the non-alternating one. But I think it's not hard to see how it works from here. The reason why "we must divide the digits[...]" is because it's trivial to create a counter-example if that doesn't happen and if it does happen it's easy to see that it works.
For case 3, if we divide the number under some rule of the problem then there's an arbitrarily large number x such that c[x] = 1, but that can't happen since c[x] * d[x] = b^x * d[x] modulo n must be true and the only non-negative x that makes b^x = 1 modulo n is 0. So this case is impossible to solve.
I hope everyone get positive rating after this contest
dude
when the contest rating
why so cringe?
Radewoosh could you explain why your code (237099844) is not a random 20 lines, but a solution to the problem please?)
If the problem is to solve $$$a_1 x_1 + a_2 x_2 + ... = b$$$ then you just iterate over parity of $$$x_1, x_2, ...$$$ and then reduce the problem to one where each $$$a_i$$$ is doubled.
We’re looking for a few values (how many Pokémon of each species there is). So let me guess the parity of each of these numbers ($$$2^n$$$ options). Knowing the parity of some $$$x$$$ means writing it as either $$$2x’+0$$$ or $$$2x’+1$$$. I subtract what these 0s and 1s give me and from now I need to set each number of species even. But it’s the same as without parity restriction but with the sum two times smaller. Add memorization cause the number of different sums will be small.
Can anyone explain the solution to problem K?