Comment if you're taking! It will be held on January 22nd, 1 PM CT on Kattis. The online mirror will be there too hopefully; my college didn't register (Go Bears -_-) so I'll have to take it on there too.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:11:38
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:11:38
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:23:22 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by vkgainz (previous revision, new revision, compare).
will be taking! our team name is "We are dumb"!
Open mirror link: https://naq21-open.kattis.com/standings
I’m curious: are others planning to take the contest under one-PC or three-PC rules?
We did 3 PCs :0
Goberts
Does B requiring finding minimum distance between a ray and a line segment in 3D? If so, can someone share their code for that?
I used https://github.com/kth-competitive-programming/kactl/blob/main/content/geometry/SegmentDistance.h and ternary search.
Oh that's nice! I was trying to work out the details between endpoints and then doing line-line intersection after accounting for those, but ternary searching on the ray removes the need for that.
Here are the aggregated standings.
:D
Problem F: I tried to come up with a DP but I couldn't. At the end, I was thinking something related with suffix automaton but I think this is not the way.
Do I need to know any special trick or algorithm to solve it? thanks for the help in advance.
I was able to do it using some prefix sum arrays. Let's say for each index $$$i$$$ you can compute the number of pairs of letters using the first $$$i-1$$$ characters that form a vowel-consonant combination (and group them by the vowels+consonants used) for, and then do the same for the last $$$N-i$$$ characters. We can then just combine them using some math.
Any hint on problem F?
for a tuple (A,B,C,D,E), we first compute pre_v[i][c] and suf_v[i][c] as for prefix/suffix i, the number of vowels c. Then we use it to compute pre[i][x][y] and suf[i][x][y] as for prefix/suffix i, the number of pair(vowel x,consonant y).
Then to compute the answer, we do a bit of include-exclude principle. Our answer is #(A!=C,C!=E)-#(A!=C,A==E)+#(A!=C,A==E,B==D)-#(A!=C,C!=E,B==D). Each part can be computed by enumerating two loops of vowels and consonants and suming up with pre and suf.
The total time complexity is O(n*vowel*consonant).
Thank you and I found that adding another loops of vowel still fits in the time limit and it makes the math much easier.
Lol I overkilled problem F with a bitmask dp :D
For problem D, why doesn't this work?
I numbered the variables from 1 to 100 and then I tried making a matrix with each row correlating to an equation. In a row, the jth column would contain the power you raise variable j to such that when you multiply them all together they are 1. Ex the equation $$$b^2c=1/(a^2b)$$$ or $$$a^2b^3c=1$$$ would be translated to the row $$$[2,3,1,0,0,0,...]$$$. I then found the rref of this $$$n \times 100$$$ matrix and checked if it had a row with only one element.
Sounds correct, what field did you use?
Reals?
It's hard to avoid precision issues so I used $$$F_p$$$
You can get a lot of error if your input matrix is very ill conditioned, for example https://en.wikipedia.org/wiki/Hilbert_matrix
Will the tests be publicly available?
Does this sound about right for L?
Basically you can do a sqrt trick and separate the graph into a set of light nodes (degree $$$\leq \sqrt{n}$$$) and heavy nodes (all other nodes). First, for each heavy node you can do a BFS to mark the distance to all other nodes. This will run in $$$O(n \sqrt{n})$$$. Then, you compute for each node $$$u$$$ and each heavy node $$$v$$$, how many neighbors of $$$u$$$ are at distance 2 of $$$v$$$. Store these in a table (I think 1GB memory is good enough).
Now, for each light node, we can use the following strategy: keep track of the "contribution" of each of its neighbors, where the "contribution" is how many nodes are adjacent to the neighbor but not adjacent to me (we can use a set for the queries). We can then use simple counting to find swords that are centered on the node.
We do essentially the same thing for heavy nodes, but we use our precomputed table to find the contributions instead of doing it naively.
Total runtime: $$$O(n \sqrt{n} + n log(n))$$$.
I just used bitsets to solve it in O(n*m/64).
Fixed the middle edge and then used
.count()method to count neighbours, count common neighbours and then some permutations and combinations.Our solution: If you enumerate edge (B,D) and compute the answer, the only part that you need to subtract is when A is the same as C,E,F. In that case, it is a cycle of 3 nodes. We can enumerate all cycles by O(n^1.5), then subtract the contribution to get the answer.
Somehow my teammate’s O(nm) heuristic passed, so I’m suspecting test data wasn’t particularly strong?
Is "enumerate all cycles by O(n^1.5)" standard? How to do it?
I found this useful: https://codeforces.net/blog/entry/96713
It probably should be $$$\mathcal{O}(m^{1.5})$$$, as a complete graph has $$$\mathcal{O}(n^3)$$$ cycles.
Enumerating all cycles in $$$\mathcal{O}(m \sqrt{m} \log n)$$$ is easy. Call a vertex heavy if it has at least $$$\sqrt{m}$$$ neighbours, and light otherwise.
First, loop over light vertices and pairs of their neighbours, and check if those two neighbours are connected. This takes $$$\mathcal{O}(\sum_{i \in L} deg(i)^2 \log n)$$$ time where $$$L$$$ is the set of light vertices. Since $$$deg(i) \leq \sqrt{m}$$$ for $$$i \in L$$$ and $$$\sum deg(i) \leq 2m$$$, this is $$$\mathcal{O}(m \sqrt{m} \log n)$$$.
Now, we have enumerated over all cycles except those with three heavy vertices. Loop over heavy vertices, and for every heavy vertex, loop over all pairs of its heavy neighbours, and check if they are connected. Since there are at most $$$m / \sqrt{m} = \sqrt{m}$$$ heavy vertices, this takes at most $$$\mathcal{O}(\sqrt{m}^3 \log n) = \mathcal{O}(m \sqrt{m} \log n)$$$ time.
This can be done in an even cleaner way by simply doing the following: (for now, assume degrees of every vertex is distinct) For every vertex $$$x$$$, let $$$L$$$ = list of nodes neighbour to $$$x$$$ with degree > $$$deg[x]$$$. Simply iterate over all pairs $$$(p_1, p_2) \in L, p_1 \neq p_2$$$, and check if $$$(x, p_1, p_2)$$$ form a triangle.
Proof is the same as you said — consider two cases, vertices with degree $$$< \sqrt{m}$$$ and degree $$$\geq \sqrt{m}$$$. To handle the cases where degree of multiple nodes can be the same, I just added the index of the vertex as a tiebreaker.
That’s quite cool, thanks!
Another version.
For each vertex $$$u$$$ we're going to count all triangles involving $$$u$$$. We choose the faster of two algorithms:
We can see that the cutoff between the algorithms is $$$\deg u < \sqrt{m}$$$, and because of this, the ratio $$$\displaystyle \frac{\text{work done}}{\deg u} \leq \sqrt{m}$$$.
Here's a nice idea to remove the hash map and vastly improve the constant factor (hash maps have terrible constant factor).
Let's queue up the queries for "is $$$(a, b)$$$ an edge?" instead of answering them right away. Since these queries are $$$(a, b)$$$ pairs, if we have $$$k$$$ queries we can 2-pass radix sort them in $$$O(n + k)$$$. Then we can two-pointer sweep with the real edge list and answer all the queries in $$$O(m + k)$$$.
Now since we would rather not use $$$m^{1.5}$$$ memory, we can instead queue up queries and then process them once we get more than $$$m$$$.
Oh that’s a really cool idea too. Thanks!