t.me/umnik_team Contest on Timus

6 years ago, # |

+47

Friendly warning that one of problems from this contest appeared on Prime New Year Contest, but I guess it's not like results of some mirror of Petrozavodsk contest are very important, so I wouldn't say that this exclude anybody from participating if he just pretends this problem doesn't exist.

→ Reply

6 years ago, # ^ |

Absolutely correct, thanks, I half-forgot that this problem was there, probably because it is not that hard :)

→ Reply

Radewoosh

6 years ago, # ^ |

Which one was that?

→ Reply

6 years ago, # ^ |

+10

Don't look if you didn't participate in Prime New Year Contest and going to participate in the mirror.

Spoiler

→ Reply

6 years ago, # ^ |

+10

By this point I can assure you that you know something like half of problems from this contest, no point in you participating there :p

→ Reply

6 years ago, # ^ |

Really? I don't think that this contest was published anywhere, and if I remember correctly, there were no teams from Warsaw in that camp.

→ Reply

6 years ago, # ^ |

On University of Warsaw we usually use problems from Summer Petrozavodsk camps for internal competitions. In particular we used two of your problems yesterday :p

→ Reply

6 years ago, # ^ |

How do you get access to them?

→ Reply

6 years ago, # ^ |

+10

By the courtesy of snark :)

→ Reply

6 years ago, # ^ |

+18

Weird stuff, this contest is not even on opentrains :)

→ Reply

6 years ago, # ^ |

Being absent or being added with a two years delay on opentrains is not that uncommon ;p

→ Reply

6 years ago, # ^ |

+80

I mean, weird that you have access to the contest and it's not even on opentrains. So Snark have time to send the contest to you, but don't have time to upload it to opentrains.

→ Reply

Radewoosh

6 years ago, # ^ |

Makes sense, thanks.

→ Reply

6 years ago, # |

Is there problems pdf?

→ Reply

6 years ago, # ^ |

You can see the statement by clicking on the problem.

Or do you want to print it out? I can send you some version, since we changed limits in 2 problems.

→ Reply

mango_lassi

6 years ago, # |

+24

Really hard problems QAQ

I'm surprised so few people did G, to me it was trivial, just a lot of work. Initially my code was way too slow, then I swapped binary search in baby-step giant-step to the gnu_pbds hashmap and suddenly random instances took like 1.5s. Pretty odd, I thought that binary search could never be beaten.

In C the weight of the tree is just $$$\sum_{i = 1}^{n} deg(i) \cdot i \cdot n - i \cdot (n-1)$$$ so you only need $$$E[deg(i)]$$$ for all $$$i$$$, but that seems to be pretty hard to get. Apparently sampling trees uniformly at random given degrees of nodes isn't easy, so how is counting solutions possible?

How to solve D?

→ Reply

Tutis

6 years ago, # ^ |

← Rev. 3 →

+19

For D the answer is 4*a-1/3. With the power of WolframAlpha.

First attempt


/*input
2
*/
#include <bits/stdc++.h>
typedef long double ld;
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	ld a;
	cin >> a;
	ld x1 = (sqrtl(4 * a + 1) - 1);
	x1 *= x1;
	x1 /= 4;
	ld x2 = (sqrtl(4 * a - 3) + 1);
	x2 *= x2;
	x2 /= 4;
	ld x3 = (sqrtl(4 * a + 1) + 1);
	x3 *= x3;
	x3 /= 4;
	ld S = ((1 + 2 * a) * sqrtl(1 + 4 * a)) / 2;
	S += (1 - sqrtl(1 + 4 * a) + a * (-6 + sqrtl(-3 + 4 * a) - sqrtl(1 + 4 * a))) / 6;
	S += 2.0 * powl(x2, 1.5) / 3.0 - a * x2;
	S -= 2.0 * powl(x1, 1.5) / 3.0 - a * x1;
	S *= 2;
	cout << fixed << setprecision(10) << S << "\n";
}

→ Reply

6 years ago, # ^ |

$$$ans=4a-\frac 1 3$$$ for $$$a \ge 2$$$

→ Reply

6 years ago, # ^ |

+17

Did you get accepted on G? My solution does not involve computing discrete logarithms.

→ Reply

mango_lassi

6 years ago, # ^ |

← Rev. 2 →

Yeah. I don't know any better way to get the size of the generated subgroup than to take $$$(p-1) / gcd(p-1, a_{1}, \dots, a_{k})$$$ where the values in the interval are $$$g^{a_{1}}, \dots, g^{a_{k}}$$$ for some generator $$$g$$$.

So I used discrete logarithm to turn the input values into exponents of the generator, and multiplication into addition. Then I used the standard technique of interval GCD segment tree with addition to get the result.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+16

It shouldn’t be fast enough though... at least if p is 10^12 I don’t think this approach can pass.

To find order of subgroup, it’s just the lcm of all order of elements as the multiplicative group is cyclic. It’s easy to maintain if you consider ratios of consecutive elements.

EDIT: I see what you mean now, the complexity is like sqrt(p(n+q)) I guess. Still, it can be done without polynomial dependence on p.

→ Reply

mango_lassi

6 years ago, # ^ |

$$$p$$$ was at most $$$10^{9}$$$ in the problem

→ Reply

6 years ago, # ^ |

+24

When I came up with this problem, I didn't know that you can solve (add on segment, gcd on segment) with segment tree. Then I_love_Tanya_Romanova solved it with this approach during testing. Our implementation of this works about 6.5 seconds which was enough in original contest, but not in this version. Though I didn't try to optimize it, looks like very fast hashtable is the key.

My original solution had complexity $$$O((n+q) (\log n + \log p) \log p$$$, and it works around the same time. To get lower times I did some insane optimizations, main one is this: I needed to calculate $$$O(\log p)$$$ powers of the same number in one query, and instead of doing $$$O(\log p)$$$ binary exponentiations, I did 5 or 6 layers of sqrt-decomposition-like thing, getting $$$O(k(\sqrt[k]{p} + \log p))$$$ (where $$$k=6$$$), which is 2-3 times faster.

→ Reply

6 years ago, # ^ |

+10

You know degree for all not_-1 vertices, and all other vertices are the same, so they have equal $$$E[deg(v)]$$$. Sum of all deg is $$$2n-2$$$, so you know $$$E[deg(v)]$$$ for all $$$v$$$.

→ Reply

ko_osaga

6 years ago, # ^ |

Maybe G is hard because people like me don't know what group means in mathematics?

→ Reply

6 years ago, # ^ |

+24

There were the definitions, right?

→ Reply

ko_osaga

6 years ago, # ^ |

+26

I saw the sample and didn't scroll beyond. Sorry.

→ Reply

6 years ago, # ^ |

+10

It's not like you are already familiar with a concept right after reading definitions.

→ Reply

6 years ago, # ^ |

This is true. But this problem is about the multiplicative group modulo prime number, with which participants are mostly familiar, things like existence of primitive root are known. So even if you didn't know what is group, I think you could read the definitions and understand that you are dealing with object you know.

→ Reply

6 years ago, # |

+14

Help, how to solve B?

→ Reply

6 years ago, # ^ |

+34

let $$$A = {a_1,a_2,\cdots,a_k} $$$ (sorted by dfn)

$$$f(x)$$$ = the sum of the weight from root to x.

$$$ans = f(a_1) + f(a_2) + \cdots + f(a_k) - f(lca(a_1,a_2)) - f(lca(a_2,a_3)) - \cdots - f(lca(a_k,a_1))$$$

→ Reply

eight_eight

5 years ago, # ^ |

← Rev. 2 →

How to prove it ?

→ Reply

6 years ago, # |

+25

How to solve A & E?

→ Reply

chenjb

6 years ago, # ^ |

+19

A: First of all, we consider that whether a single 0 or 1 occur in the rule. Obviously, only one of 0 or 1 occur in the rule, Otherwise the answer is N or -1. Suppose there exists 0 but not 1, because it is a prefix-free system, a fact is that if W can be decoded, only if 0^k+W can be decoded. For any S, if we consider restrciting a suffix cannot be decoded, we only have to think about how to divide the prefix part. Because 0 can be decoded, and each part we devided at least contains a 1, so we can only divide into p(the number of 1s) parts. We can only create this way by connecting every 1 with the continuous 0s. Now the problem becomes finding the shortest prefix that cannot be decoded and the answer should be added by the number of 1s. We can easily find it by reversing those strings and building an AC-Automaton.

Well, I think it is a quite good problem and also a nice contest. Many thanks to Umnik~

PS: I actually translate this solution from my solution in Chinese written in August,2018. Maybe I miss some important details or have some mistakes.

→ Reply

6 years ago, # ^ |

Thanks you :)

→ Reply

noxe

6 years ago, # ^ |

+10

For E, $$$O(n^3)$$$ is obvious but got TLE. I guess some methods like FFT/NTT would be used to optimize it (since 40961 is a modulus of NTT). But I have no clue.

→ Reply

6 years ago, # ^ |

+30

E: We need to compute $$$\sum((s[i] == 0) \times C(i, x)\times C(n - i - 1, y)$$$ for each $$$x, y$$$. Fix $$$y$$$, it turns out to use FFT/NTT.

→ Reply

Thisbe

6 years ago, # ^ |

← Rev. 3 →

Sorry, I don't understand. Fix y, then how to change it to a convolution?

→ Reply

sheaf

5 years ago, # ^ |

← Rev. 2 →

Could you be so kind and elaborate a bit more on how to reduce this sum to convolution? I tried to calculate $$$f(l, r)$$$ — the number of subsequences of length $$$l + r + 1$$$ with $$$(l + 1)$$$'th element being $$$0$$$. I.e. I tried to preprocess some sums and the answer for length $$$k$$$ would be calculating $$$a_l = f(l - 1, k - l)$$$ and outputting $$$\sum_{i=1}^k a_i \cdot (C(n, k) - a_i)$$$. I computed $$$f$$$ using divide and conquer and NTT that is in $$$\mathcal{O}(N^2 \log^2 n)$$$ which is too slow. Could you hint further how can one achieve $$$\mathcal{O}(N^2 \log n)$$$ if that is the intended complexity?

→ Reply

konstantanter

8 months ago, # ^ |

-21

Good afternoon, could you please send the solution to problem 2122 with acm.timus.ru I would be very grateful to you https://acm.timus.ru/problem.aspx?space=1&num=2122&locale=en

→ Reply

6 years ago, # |

+10

Scoreboard of original contest, if anyone interested.

→ Reply

244mhq

6 years ago, # |

+25

How to solve I & F?

→ Reply

gop2024

6 years ago, # ^ |

+10

I`ve passed F with just bruteforce from a highest weight (but I have nothing to prove it).

→ Reply

6 years ago, # ^ |

Hmm. I did the same thing except memorizing, so it gave TLE. I was thinking that but didn't implement.

→ Reply

6 years ago, # ^ |

← Rev. 3 →

+13

Notice that there are at most two transitions for each state. ($$$W_i \ge \sum_{j<i} W_j$$$) And another upper bound is $$$w_i$$$.

The time complexity is $$$O\left(\sum_{i=1}^{n} \min (2^{n-i},w / 2^{n-i})\right)= O(\sqrt w)$$$.

→ Reply

6 years ago, # ^ |

+16

I: Lucas's theorem. We need to compute $$$\sum{C(n, i)\times C(n - i, i)}$$$. Represent $$$n$$$ as $$$(a_1a_2...a_k)_p$$$. So we concern only $$$i$$$ such that its $$$p-base$$$ representation $$$(b_1b_2...b_k)_p$$$, $$$2b_i \le a_i$$$.

→ Reply