Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Разбор задач Codeforces Round 580 (Div. 2)
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 09:19:11 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Отличный раунд получился. Больше всего понравилась задача Div 2E.
My last hour of yellow name :(
wow thank you for the fast editorial :D
F can be solved in $$$O(n^4)$$$. And I guess it can be solved in $$$O(n^2)$$$ per test case.
If $$$(a,b)$$$, then $$$(a+k-1, b+k)$$$ with $$$k\geq 4$$$ or $$$(a+k-1, b+k*(k+1)/2)$$$ with $$$k\geq 2$$$.
There is a tree structure about the permutation, which is called 析合树 in Chinese, named or invented by CommonAnts. We can derive this result directly from the tree structure. You can see these two 1 2 in Chinese for details.
And there are some similar problems with this combinatorial structure of the permutation, like NEERC 2018 I, and China Final 2018 B.
The Chinese have a Data structure for everything.
Nobody:
Chinese people: Let's make a Data Structure based on this problem.
I think it is PQ-tree?
no you can do it by segment tree
No, I think they look similar. PQ-tree tries to find a valid permutation with some given consecutive subsets, but “析合树” is to describe all consecutive subsegments of a permutation. The tree structure has two types of nodes, which are similar to Q-node and "P-node which is not Q-node" respectively. I mean, values of all sons of a first-type node (“合点”) are monotonic, and those of a second-type node (“析点”) form a simple permutation.
I introduced the tree and an $$$O(n)$$$ algorithm to construct it for a given $$$n$$$-permutation on RAM (with linear RMQ). So that many such problems could be solved in linear time. For example, CF997E.
In fact, this problem F could be solved in $$$O(n)$$$ time. We can make a valid permutation with at most $$$n$$$ items at first with greedy. After that, replace a leaf with remain items as a simple permutation. It's $$$O(n)$$$ by adjusting those conflicts of constant size (including corner cases of greedy, the extra one consecutive subsegment for the simple permutation and inexistence of a simple permutation of length $$$3$$$).
Another similar structure I've ever seen is "separation tree for permutations". It only cares about the second-type nodes, and are for problems about simple permutations.
A simple permutation is a permutation without consecutive subsegments.
If a PQ-tree successfully constructs a permutation, it can be regarded as a virtual tree for a subset of nodes in the permutation's “析合树”, each Q-node is a first-type node “合点”, and each P-node can be either type, “析点” or “合点”, depending on which permutation you choose in construction.
Problem setter & tester be like
I also solved it with $$$O(n^4)$$$ preprocessing with $$$O(n^2)$$$ per test case — I know how to improve this to $$$O(n)$$$ but I didn't bother. This is my idea, I have no idea why but it seems to work:
If there is a solution for some $$$n,k$$$ then there is also a solution such that you start from some "disorderly" permutation of length $$$m \leq n$$$, and then in $$$n-m$$$ steps you either append a new maximum element to the permutation or append the new minimum to the permutation. A permutation of length $$$m$$$ is "disorderly" if its beauty is exactly $$$m+1$$$. I used dynamic programming to track the longest "increasing subsegment" suffix of the permutation, this tells me how many new good subsegments are added when the new maximum is appended. Code: 59129441
So my mans created his own data structure now
Fastest Editorial I have seen in a while! Thanks :)
So fastest that it was pulished 2 days ago!
I was able to solve Div2: C with some example that I wrote in the paper. I was trying to understand the derivation of editorial, but I am not able to understand it. Can someone please elaborate it more like why n even always has no answer?
Consider taking some array from the circle. Then take next value and remove last value, on the same circle. The sum cannot stay the same, because that means what we removed and what we added is equal, and we cannot do that. So it either goes up or down by 1.
Imagine sum increases by 1. We can write +1 near that number. After that, with same logic, next move has to decrease sum by 1, because increasing number twice gives us three numbers on blackboard: sum, sum + 1, sum + 2. So we can write -1 near that number.
Now consider a circle with +1 and -1 instead of numbers. If it is odd, it starts and ends with same value — easy to see. And if it is even, is ends with different value and we are back at the sum. No two consecutive numbers (+1 or -1) must stay the same, as it is easy to see.
I didn't quite get the last paragraph of your answer, about the circle of -1 and +1. Can you elaborate a bit please? thanks in advance.
Let's create second circle of the same size, but with +1 or -1 inside, instead of numbers we put in. If it has length of n, we can label its nodes from 1 to n inclusive. Even ones have same sign, and all odd — labeled ones have different sign. The only place when it could go wrong is connection of n'th node to the first one. If they are both odd, they will have the same value, and we don't want that, as we showed. So 1 is odd and n has to be even
but the question asked to check in 1 to 2n. it doesn't matter if n is even or odd the last node and first will have a different sign. please explain why the n even is not possible??
Yes, the borders work well since the circle is of even length. But there is another problem with even n.
Consider doing one step around the circle I mentioned. Let's denote sum of all numbers on the circle S, and previous sum in our chosen interval A. The sum of elements we have not chosen will be B = S — A. If we get +1 as result, new sum is A + 1. What happens to B then? Since S stays constant, new B = B — 1. If we choose the second interval as initial one, we would have to write -1 on the next node.
So if we have +1 on one side, then we need to have -1 on opposite side (and vice versa). If n is even, we get two sequences (+1 -1 +1 -1 ...) (+1 -1 +1 -1 ...) of length n each. Their first elements will have the same sign, which is contradictory
Iv got a simple proof for that.If input is n we have 2n numbers to arrange .the sum of these 2n nos is s=2n*(2n+1)/2 =n*(2n+1).since 2n+1 is always odd,s depends on n.now if n is even ,s can be divided in two equal parts(eg 18+18 for n=4) which we dont want as sum of no two consecutive n nos can not be equal.so n is odd.
Is the answer to the bonus of Div1.A yes when k is odd
yes
no. consider k=1
When k=1,it is impossible to find such an answer
When $$$k=1, n=2$$$ it is possible
You are right.I didn't think very carefully
Автокомментарий: текст был обновлен пользователем antontrygubO_o (предыдущая версия, новая версия, сравнить).
can someone please help me with my code. There is something strange.
Why downvote? I post it because I am not able to understand why it is not printing all the $$$n$$$ strings. I had run the last for loop n times. But in the output it is printing only 3 rows. If someone can help then Please help!
probably your code print something other than 0/1 (-1 or something)
Somebody pls check and tell what's wrong with my code for Div 2 problem B !! code
input :
3
-1 0 1
output: 1
yours: 3
Currently, you are ALWAYS making 0 go to 1. However, 0 can also go to -1 for the same cost (1).
Can anyone explain how to solve problem Div2 D?? I am not able to understand the editorial...
I did it this way- The maximum number in the input is 10^18 which can be represented in 64 bits. The minimum possible cycle can be of length 3. If we have the xth bit set in any 3 numbers, then we are done! (all 3 will be mutually connected because of non zero "and") There are at max 64 bits. => If we have more than 128 non zero numbers (By PHP) in the array, then we will get a cycle of length 3.
Now for <= 128 non zero numbers. We can check by actually making a graph. It will take O(m^2), which will be well within the bounds.
How do you come up with the "128 non-zero numbers" logic?
10^18 fits well inside 64 bits. We need a minimum of 3 set bits at any common position. By Pigeon Hole Principle if we have more than 64*2 = 128 numbers (non zero because zero has none of the bits set) then at least one of the position will have 3 set bits. (The bound of 128 can be made stricter if you calculate the exact number of bits needed to represent 10^18)
Thanks
how does having >128 numbers guarantee that there will be at least 3 numbers having set bit at the same position? (I'm not saying the answer is wrong, i wanted to know how php is used here)
in this problem Max(Ai) = 10^18 which has 60 bits, and as they said > 128 numbers guarantee that there will be at least 3 numbers having set bit at the same position.
what if i change Max(Ai) = 7 then it only has 3 bits and > 7 numbers guarantee that there will be at least 3 numbers having set bit at the same position. how can it happen?
here is the example N = 7
4 4 2 2 1 1 4
and then i convert all of them to Binary Form
100
100
010
010
001
001
100
sum of column: 3 2 2
as you can see, at the last input, no matter what number you add (as long it <= 7), the sum of column will be >= 3
i had already figured it out but thanks!
For the problem, Shortest Cycle ,in the test case with n=10^5 and large numbers, making an adjacency list is causing Memory Limit Exceeded Error. How to prevent this?
Edit: Just note if too many edges (thus giving memory limit exceeded) then there is a triangle.
div1 a. i noticed a beautiful pattern by connecting numbers on circle sequentially. my solution was 0 3 4 7 8..., i.e., +3 +1 under modulo 2*n,now join 0->1,1->2..2*n-1->1and so on it makes flower like pattern on paper.really amazed after seeing that.
Thank you for your challenging problems and educative tutorials! But I was caught with some trouble at problem D... 59056716 I tested this submission with test 15 both on my local Windows machine and codeforces custom invocation. Both are resulted in 3. But every attempt to submit turned out to be Wrong answer on test 15...
OH I thought I have made some mistakes...
Maybe I pasted some other test data by mistake... Finally I found out my fault, then I formed a bfs tree, to judge the size of rings by LCA！[submission:59058541]
For 1206 D, 1205 B Another way, If the no. of non-zero elements > 120 ( 2*log2(10^18) ) then we must surely have a 3-cycle. Otherwise, for all vertices v, do BFS traversal to find length of shortest cycle through v and take minimum. This will be in O(V*(V+E)) time and O(V+E)(max O(V*V)) memory. Not much efficient though.
My solution 59056716 is very close to that, but I strangely recieved a WA on test 15, while I surely got the correct answer in codeforces custom invocation...
Custom Invocation gives 5!=3.
Awwww I see... I'm going to keep debugging...
Thank you! Finally I formed a bfs tree and judge the size of rings by LCA！[submission:59058541]
Why am I getting WA on test 5 59056925 in problem D ? I think I misunderstood the problem. Can someone show me how the answer for test 5 is 4 ?
Your massive a is int, but should be ll.
Thanks. It worked.
In Div-2D, can someone explain why using set as Adjacency list gives AC int the following code 59059506 whereas using Vector as Adjacency list gives WA in this code 59057776
Given that you are getting WA on TC 14, it is probably because two values can share more than one bit, so the vector representation would have multiple edges going between the same two nodes, which would allow a cycle of length two.
Yeah, got it. Thanks.!!
Finally I left div2.. Nice problems, but solving them from smartphone is incredible as usual :(
For div2,D If the number of non_zero numbers is more than or equal to 119 ,we can just output 3.（Pigeonhole Principle,think of each bit as a pigeonhole,and think of each non_zero number as a pigeon） If it is less than 119,we can just use Floyd algorithm,we can solve it in O(n^3).
This might be a little bit easier to understand.
I tried to implement Floyd in the contest but failed coz I discover a problem: say there's an edge u -> v, Floyd will find a cycle path of "u -> v -> u" coz this is an undirected graph. And I don't know how to counter this problem. Do you know if there's any tweak I can do to make Floyd work?
http://codeforces.me/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
Thanks for the reply, is it ok for you explain these two lines of code?
It's not quite easy to explain. It's just a way to avoid the situation you said above.
Kindly explain the above lines if you have understood them!
This loop is essentially enumerating all the pairs that satisfies 0 <= i,j < k. The shortest path between any pair can only include Vertex 1 ... Vertex k — 1 according to the property of Floyd algo. So here we can enumerate all the cycles that contains Vertex 1 ... Vertex k. When k iterate from Vertex 0 to Vertex n, we basically covers all the possible cycles in the graph.
Can you please explain how to use Floyd's algorithm for finding the shortest path? (I read somewhere it couldn't be used for undirected graphs). It would be of great help. Thank You.
http://codeforces.me/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
What is the logic behind (mincircle = min(mincircle,d[i][j] + e[j][k] + e[k][i]) this line? and Thank You for your help.
Can someone explain me the proof of div2 C,i basically did some cases and realized that if the number is even there is no solution, but i cant prove it.
"Now, if n is even, we get a contradiction, since ai+n−ai=−(a(i+n)+n−ai+n)ai+n−ai=−(a(i+n)+n−ai+n), but due to the alternating they must be equal."
Problem B.Div2 is interesting.59065083 :D
Hi could someone tell me why this is failing for "Make Product Equal One" https://codeforces.me/contest/1206/submission/59025115 locally I'm getting correct answer for the same input, is it some IO issue with Golang?
int -> long long ??
In Problem D, I first checked for the 3 length cycle case as given in editorial and then I'm finding the minimum length cycle for the other case by taking each vertex as root and seeing if it is in the cycle or not, cases with some non-zero inputs and n = 100000 are passing but the case with all zero inputs and n = 100000 is giving TLE. I'm unable to understand why in case of all zeros it is giving TLE.
Submission — 59060203
Instead of declaring vis and par vectors of size n every time in the loop, declare map of vis and par and for each iteration of loop, clear both the maps. Hope this helps.!
Yeah it helped, thanks. But yet I'm unable to understand why previous thing didn't worked.
Can someone explain the first approach of div1C in more depth? Apart from the dp part. Thanks in advance.
Div1 D solution doesn't seem natural I think.
В конце "1205C — Палиндромные пути" написано алгоритм такой: выбрать любой путь между (1,1) и (4,4). Имелось в виду, видимо, между (1,1) и (n,n).
How can solve 1D in $$$O(n)$$$? I think "divide the subtrees of the childs into two groups" need $$$O(n\log n)$$$...
Oh, I know...
can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)
Many of you can't solve Div2 C. When you need to construct an array to solve a promblem,just construct it boldly. Don't be afraid.
For this problem, let v be some number of the array(a[i]),let v' be the number opposite v(a[i+n]). Then the circle was cut into halves.let s1 = a[i+1] + ... + a[i+n-1],s2 = a[i+n+1] + a[i+n+2] + ... + a[i-1]. if n is an even number,it means that 2 is a divisor of the sum of all numbers,let it be 2k. The sum of any n consecutive numbers must be k.So,v + s1 = k,v' + s1 =k.v = v'!It's impossible.
if n is an odd number,it means that the sum of all numbers can be written as 2k+1. Then |(v + s1) — (v' + s1)| must be 1.It means v — v' = 1 or -1. Just construct it boldly.I said to my self when I was trying solving this. What we want is for any i,s1 = k or k+1.Now we have n groups:(1,2)(3,4)...
Why not let s1 for v = 1 1 + 4 + 5 + 8 + 9 + 12 + 13 + ... ? (We choose the first one in the first group,second one in the second group,first one in the third group...)It can be proved right.
I won't write down the proof.(I didn't prove the algorithm at all when I was participating the contest,but luckily my thought was corret. :D )The proof was already given in the editorial.
(I'm a Chinese student,there might be some grammar mistakes.Please forgive me for this and upvote for me.Thanks.)
Div1 Problem E can be solved in the time complexity of O(n log n) with Möbius inversion formula : let define that
try to enumerate i1,j1 , whose gcd is d , and simplify the formula it with Möbius inversion now we have
using the inversion:
we can derive that
let $\ i\ ,\ j$ take the place of $$$\frac{i_1}{pd}\ ,\ \frac{j_1}{pd}$$$ we have
then we can enumerate$T=i+j$ the latter formula turns into some "calculate the sum of geometric progression" questions
the former two $$$\sum$$$ can be enumerated in $$$O(n \log n)$$$ the latter formula can be calculated in $$$O(1)$$$ with $$$O(n \log n)$$$ pretreatment
Can anyone pls prove this in Div1E?
The case of i1+j1≤n is obvious: in this case, by subtracting and adding i1,j1 we can show that the string has period gcd(i1,j1), in this case comps=gcd(i1,j1). We now consider the case when i1+j1>n.Can someone help me figure out the complexity of D problem. There could be at max 60 edges and for each edge we perform a BFS to find the shortest distance between its end points. And there are n vertices, so total complexity of performing repeated bfs would be 60^2*(n+60). And in order to construct the graph the work would be n*(log10^18) so overall — n*(log10^18) + 60^2*(n+60). Could someone tell me if my analysis is correct. Thanks in advance.
No!! There are at most 60 edges in a graph and removing each edge and doing bfs would cost me at most 60 operations . so overall our complexity would be (60)^2. You could have also used bellman ford for this but there time complexity would have been (60)^3 in worst case.
60 edges can connect at most 120 vertices. So rest of the vertices have zero degree, you don't have to do BFS on them. For example, you can do BFS on the connected component of source only. So my guess is, depending on the implementation the complexity may vary.
Can anyone please explain to me how to find the shortest cycle using the Floyd Warshall's algorithm??
Define $$$dp[i][j][k]$$$ as the shortest path from $$$i$$$ to $$$j$$$ using upto prefix $$$k$$$ of vertices, then shortest cycle length is $$$dp[i][i][n]$$$.
So basically you find the shortest path from vertex $$$i$$$ to $$$i$$$ itself. Make sure during initialization you set, $$$dp[i][i][k] = \infty, \forall k \in [0, n]$$$ and during transitions, avoid going from $$$i$$$ to $$$i$$$ through $$$i$$$(Well, actually this happens automatically if you set $$$dp[i][i][0] = \infty$$$).(Prerequisite: Basic version of Floyd Warshall)
Setting $$$dp[i][i][0] = \infty$$$ is mathematical way of saying that there is no path from vertex $$$i$$$ to $$$i$$$ without going through any vertex.
EDIT: This only works for Directed graphs, in undirected graphs, this won't work(Since each edge of Undirected Graph == 2-length cycle of Directed Graph), see explanation here, https://qr.ae/TWreWj
I did not understand what did you mean by "upto prefix k of vertices", could you please explain that part in detail?. It would be of much help. Thank You.
Prefix $$$k$$$ of vertices, means possibly using vertices from set {$$$\,1, 2, 3,..., k$$$}.
Read more details from Wikipedia, https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm
How does the checker work fast enough to determine whether there exists a palindromic path if I query distant points in Div.1 problem C?
I come up with an idea look at this :
if dp[i][j][k][l]=1 means there is a Palindromic Paths from (i,j) to (k,l),0 otherwise.
update: dp[i][j][i][j]=1,dp[i][j][i+1][j]=(a[i][j]==a[i+1][j]),dp[i][j][i][j+1]=(a[i][j]==a[i][j+1])
if(a[i][j]=a[k][l])
dp[i][j][k][l]=dp[i+1][j][k-1][l]|dp[i+1][j][k][l-1]|dp[i][j+1][k-1][l]|dp[i][j+1][k][l-1];
else
dp[i][j][k][l]=0;
Do you think it's right?
And complete is O(n^4),it's fast enough
Could anyone please explain the second solution of Div.1 C more clearly?
"Thus, the algorithm is as follows: choose any path between $$$(1,1)$$$ and $$$(4,4)$$$, find on it four cells with a xor of numbers equal to $$$0$$$, and ask a question about it."
Why does there exist a path from $$$(1,1)$$$ to $$$(4,4)$$$ such that the xor is equal to $$$0$$$?
I'm wonderig the same thing rn
for B wouldnt the answer always be 2 since if a[i] & a[j] != 0, then in the graph there will be an edge of weight 1 from i to j. since a[j] & a[i] != 0 as well. we will get an edge from j to i, which is a back edge of weight 1. this would mean the shortest cycle is of weight 2 always?
In the announcement they mentioned this :
Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices.
Useful for 1206C/1205A
Cool.
For div1.B, why does this TLE give TLE for input with 1e5 0s, which forms an empty graph, while this gives AC.
Could anyone prove an upper-bound of the answer to Div1D? Is $$$\frac{2}{9}n^2+O(n)$$$ optimal?
I did div2-E in the dp way, but I can't understand how there will always exist a path from (1, 1) to (4, 4) such that xor sum of 4 consecutive elements is 0. For example in the following matrix, there exists no such path from (1, 1) to (4, 4):
antontrygubO_o hate to ping you, but could you please clear this doubt.
$$$n$$$ is odd.
Oh I see, you have made a small typo in the last line of the editorial, you have written (4, 4) instead of (n, n). I was trying to prove that there doesn't necessarily exist such path from (1, 1) to (4, 4) xd.