I'll upload my example solutions and will post links to them as soon as it becomes possible.
All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :)
My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments.
I Wanna Be the Guy is an interesting game. I strongly recommend it to you.
The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y.
This problem is not hard. Just iterator over all possible t, and check if the schedule of Little X and Little Z will overlap.
Bonus:
- p, q ≤ 50, l, r ≤ 10^{9}
- p, q, l, r ≤ 10^{5}
Solution 1:
If n ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 9.
If n > 5, we can simply add n - (n - 1) = 1, 24 * 1 = 24 at the end of the solution to the number n - 2.
So we can find the solution of 4, 5 by hand. 1 * 2 * 3 * 4 = 24, (5 - 3) * 4 * (2 + 1) = 24
Solution 2:
We can find the pattern like that n + (n + 3) - (n + 1) - (n + 2) = 0, and find the solution of 4, 5, 6, 7 by hand or brute forces.
Solution 3:
A knapsack-like solution.
Solution 1:
If we have number x and a - x, they should be in the same set. If , it's obvious that . The contraposition of it is , that means if , a - x should in the set B. Same as the number x, b - x.
So we can use Disjoint Set Union to merge the number that should be in the same set.
If a - x doesn't exist, x can not be in the set A. If b - x doesn't exist, b can not be in the set B.
Then check if there are any conflicts among numbers which should be in the same set.
There are many other solutions to solve this problem based on the fact that x, a - x, b - x should be in the same set, like greedy, BFS and 2-SAT.
Solution 2:
If a = b, it's easy to find the solution.
We regards every number as a node. Every number x links to number a - x and number b - x.
The degree of every node is at most 2. So this graph consists of a lot of chains and cycles, and some node may have self loop.
We only need to check if the lengths of all the chains are even or the chain ends with a self loop.
Bonus:
Prove there is no cycle in the graph described in the solution 2.
Divided all the numbers from [0, n - 1] into two sets that have parameters a, b. Can you solved it in O(1)?
Define . , so we should find a pair of number a, b that
Solution 1:
First we choose x randomly. Then we can use binary search to find the minimal d that .
So is very small, between 0 and . If , after choosing x atmost 9 * len + 2 times, we can definitely find a pair that
Solution 2:
We can use binary search to find the minimal d that g(d) ≥ a, g(d) ≥ 2a, ...
This solution is similar to the first one.
Solution 3:
We can use binary search to find the minimal d that g(d) ≥ a. And we use two pointers to maintain an interval [l, r] that until we find .
I can't prove the correctness of this algorithm, but it performs well in practice.
Solution 4:
Thanks ZhouYuChen for his talented idea.
If x < 10^{18}, we can get f(10^{18} + x) = f(x) + 1. That means if we shift the interval [x + 1, x + 10^{18}] by 1, the result will be increase by 1 too. And it also not hard to find that g(10^{ x}) = 45 * x * 10^{ x - 1}. So if , [a - x, a - x + 10^{18} - 1] is the answer.
It's easy to see that upper bound of the answer is a, because of pigeonhole principle (among g(0), g(1), ..., g(a) at least two are equal). So big integer is not required in this problem.
If solution 3 is correct, the upper bound of the answer can be 2 * 10^{16}.
Bonus:
Prove or disprove that solution 3 is correct.
I am sorry that this problem coincides with that one.
d(u, v) = dep _{ u} + dep _{ v} - 2 * dep _{ LCA(u, v)}, so the answer is:
dep _{ i} there means the distance between node i and root.
We choose centroid of tree as root (let's denote it u), so we can make every pair (i, p _{ i}) are in different subtrees, that means dep _{ LCA(i, p i)} = 0.
So the answer is .
The next part of this problem is find the lexicographically smallest solution.
We regards it as finding the lexicographically smallest matching in a bipartite graph.
For a subtree, if the amount of nodes in this subtree in the left part > the amount of nodes not in this subtree in the right part, the perfect matching doesn't exist. So the amount of nodes in this subtree in the left part + the amount of nodes in this subtree in the right part should be no more than the amount of nodes unmatched, while the root is an exception.
We can use a segment tree to maintain it easily. We determined the minimum possible p _{ i} from 1 to n. If there is a subtree that the amount of nodes in this subtree in the left and right part is equal to the amount of nodes unmatched, we must select a node from it, so p _{ i} equal to the node in this subtree with the minimum id. Otherwise, we can choose a node with the minimum id that is not in the same subtree with i.
The permanent can be obtained as follows: for each (e _{1}, e _{2}, ..., e _{ t}) such that x _{1}, x _{ e 2}..., x _{ e t} are distinct and y _{ e 1}, y _{ e 2}, ..., y _{ e t} are distinct, add to the answer.
It can be proved by the formula :
,
where s and t are subsets of the same size of {1, 2, ..., n} and , are their respective complements in that set.
Construct a undirected graph G with 2n vertices v _{1}, v _{2}, ..., v _{2n}, where the edge weight between vertex v _{ i}, v _{ n + j} is A _{ i, j} - 1. We only need to know the sum of weight of all matchings that we choose t edges. The weight of matching is the product of all edge weights in the matching.
We only need to know the sum of the weights that we choose x edges in the each connected components.
The number of nodes in a connected component is s and the number of edges in this connected component is t.
Algorithm 1:
Because it's a bipartite graph, so the number of vertices in one part is at most s / 2. So we can use state compressed dp to calculate the ways to choose x edges in this connected component. The complexity is O(2^{ s / 2} * s ^{2}).
Algorithm 2:
We can choose a spanning tree. The number of edges in spanning tree of these vertices is s - 1, and the number of non-tree edges is t - s + 1. So we can enumerate all the non-tree edge, use tree dp to calculate the ways. The complexity is O(2^{ t - s} * s ^{2}).
Combined with these two algorithm, the complexity is O(min(2^{ s / 2}, 2^{ k - s}) * s ^{2})) = O(2^{ k / 3} * k ^{2}).
468A — 24 Game Solution 3: A knapsack-like solution.
Can someone explain it?
From the link posted in the editorial, this is what I got:
The crux of the solution lies in the equation:
Pos = (Tn + 24)/2
. Pos is the sum of the first k numbers with some number x removed. Tn is the sum of the first N numbers (N is input).This means
2*Pos - Tn = 24
We can reduce this:For example, for test 2, x = 6 and sum(k+1..n) is 0 [k has to be <= n]
For test 3, x = 4 and k+1 = 11 For N = 7, x = 6 (this case was tested twice — so was N = 3, am not sure why?)
Does 468B - Two Sets contain anti-hashtable tests? I'm curious why my submission TLed with
unordered_map
/unordered_set
and passed with regularmap
/set
.No. test cases are randomly generated.
map
/set
has O(log(N)) complexity of[]operator
/find()
.unordered_map
/unordered_set
: O(1) on average, but in worst case O(N).Thank you so much.
Div2 C problem is really good. Hope that the next codeforces round is as good as this one. Thanks for exposing us a lot of good problems.
Thank you :)
"If n ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 6."
A minor error there, the maximal number they can form is 9. 3 * (2+1) = 9
Also, could you please elaborate on the idea for the knapsack-like solution?
sorry, you are right :P
What is worst possible case for div1C-solution 3? I mean test with largest possible L.
Then check if all the number should be in the same set can be in the same set.
Can you rephrase it? I find it difficult to understand what you mean. Possibly there is a comma (,) missing?
After doing the stuff described above it turns that some pairs of elements should be in the same set. So you have to check whether it is possible to divide them between exactly two sets satisfying the condition.
Can someone elaborate all the solutions for problem B Two Sets? (Solution A, B, Greedy, 2 SAT and Hopcroft-Karp)?
I can't understand what's given in the editorial.
Here's what I've collected so far:
Solution 1: How do you do this "Then check if there are any conflicts among numbers which should be in the same set." (which is the essence of the problem I guess) Code from editorial
Solution 2: "So this graph consists of a lots of chains and cycles, and some node may have self loop." Why does there exist no cycle? Chains exist in the following way:
x -> a-x -> b-(a-x) -> a-(b-(a-x)) -> ...
(prove this sequence is finite)Self loops exist when x = a-x or b-x, i.e. 2x = a (or b)
"We only need to check if the lengths of all the chains are even or the chain ends with a self loop." Why is this true?
Code from editorial
O(1) solution: Awaited.
Greedy: Code & Explanation
Hopcroft Karp: Code (Explanation added would be helpful)
2 SAT: Not found anything yet.
I mean editorials are for the people who couldn't solve the problems, right? Some more details in explanations would be useful I feel.
Thank you for your questions.
Ques 1: First you know number x, a-x, b-x should be in the same set, you can use DSU to maintain it. For one set in the DSU, the numbers in this set should be in the same set. If one number x can't be in the set A, it can only be in the set B. If one number y can't be in the set B, it can only be in the set A. So if number x and y should be in the same set, there is no solution.
Ques 2: If the lengths of a chain is odd, two ends must be in the different sets. For example, a=7, b=9, 3-4-5.
Ques 3: Divided all the numbers from [0,n-1] into two sets that have parameters a, b. I don't want to explain it, because this one is definitely a math problem. Don't relate much to the algorithm contest. I hope you can understand. If you want to know the answer to this problem, I think writing a brute force problem and finding the regular pattern is a good way.
Ques 4: I think Hopcroft Karp algorithm and 2-SAT algorithm do the same thing as solution 2. Because this graph is so special.
Thanks :)
according to wiki, "the Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph", but the graph described here isn't always bipartite.
can u tell me a bit more how we check with dsu if 2 number is same sat??
if sta[i]==0 it means that vis[i] was 3? and it means that we can make x,a-x,b-x.is it correct?
If the roots of the elements are the same then there are in same set.
468B - Two Sets
Can anyone please tell me what's wrong with my logic: 62602230
For each element, I checked if there is (a — element) or (b — element) if there is any such then I took it to the appropriate set. then I checked if all the elements have been taken or not i,e, if it's possibe to seperate them in two sets maintaing the conditions.
N.B: root(int) function in my solution is a redundant ignore this.
I used 2SAT to solve this problem, here is the code: 7883574
may someone provide a better explanation for the C-div1 first solution ?
The basic idea is to shirk the search space and using the pigeonhole principle.
First, we chose a random number x, and find the minimum d such that G(x + d) >= a (also know G(x + d -1) < a since G(x) is a monotonic function). Since G(x + d) = G(x + d- 1) + f(x + d) and the biggest possible value of f(x + d) is 9 * ceil(log10(x + d)), G(x + d) % a should be less than 9 * ceil(log10(x + d)). If for all x + d belong to [0, 10^len), then G(x + d) % a must also belong to [0, 9 * len] for different x.
Now, We just fill numbers into this search space for different x, and we must can hit the same value because of pigeonhole principle (at most 9 * len + 2 times).
How can i calculate g(x). I mean the summation digits of numbers from 1 to x...?
"In the solution 4 we can find that the upper bound of the answer is 2 * 10^{18}. So big integer is not required in this problem." (problem C)
Easy to see that upper bound of the answer is a, because of pigeonhole principle (among g(0), g(1), ... g(a) at least two are equal).
OwO you are right.
Was that really necessary to set a up to 10^{18} :(? I came up with the second solution (though, after the contest, because I hate sums of digits problem, but that one turned out to be pretty fun :P), but I was unable to code it properly (I code in C++), because I had to deal with numbers of magnitude approximately 1000*a, I think. And moreover afaik Codeforces is not supporting __int128_t...
I think that it is necessary to set
a
as high as possible.If
a
is around10^10
, the following could pass: Generate10^5
random integers. There should be a pair (l, r) such thatf(l) = f(r) mod a
If
a
is around10^16
, I could modify the above a bit to make it work:Instead of finding
f(l) = f(r)
, find the pair (l, r) such that f(l) is closest to f(r) in mod a. Then use the 2 pointers method as in solution 3.Somebody know how to solve problem B div.1 if we have p _{ i} = p _{ j}, i < > j ?
All p _{ i} are distinct.
I know, but during the contest i don't read part where it was indicated. And now i am interested how to solve this interpretation of the problem.
http://codeforces.com/blog/entry/13836#comment-188500 This works
"If n > 5, we can simply add n - (n - 1) = 1, 24 * 1 = 1 at the end of the solution to the number n - 2."
I think you should give skyvn97 his deserved AC :P http://codeforces.com/blog/entry/13836#comment-188413
UPD: To explain that post — now it is fixed, but earlier there was a typo in editorial, exactly the same which caused skyvn97 to fail that problem.
:P
in problem two sets- when i am first checking for x-a then there is error on test 9 http://codeforces.com/contest/468/submission/7899063 and when i am first checking for x-b then there is error on test 8.. http://codeforces.com/contest/468/submission/7899193 can any one help me??
if (a > b) {
swap(a, b);
}
There is a typo: 24 * 1 = 1
Should be: 24 * 1 = 24.
I have two questions:
-As I am relatively bad at coding so far, forgive me for my stupidity, but I do not understand why this solution does not work for Div 2A: "Collect the arrays of the levels that X and Y can finish, merge them together, and remove the duplicate values. If the number of values in this final array is equal to
n
, then they can pass them all." Is there a problem with this solution?-I am reading the solution linked for problem Div 2B, but I still do not understand why
vis[i-j]=vis[i-j-1]=1
, that is, why vis[i-j-1] should also be set to true.Otherwise, thank you for the editorial, as an amateur coder, these problems helped me learn a lot. For example, I was able to code Div 2C three different ways. :)
In the post, this part for Problem C, Solution 4: "And it also not hard to find that ... is the answer."
Should be:
g(10^{ n}) = n * 45 * 10^{ n - 1} so if g(10^{18}) = x(moda), [a - x, a - x + 10^{18} - 1] is the answer. (if I didn't misunderstood your g(x) function.:D)
fixed now.
I have two questions to 268 C (div 1), solution 1, because it's really unclear to me:
thank you, fixed now.
About problem D, I want to know, why should we choose centroid to minimize ? And what is the definition of "centroid" here? The tree is weighted. upd:maximize
I mean, if we choose centroid as u, why is maximized? And, if we choose u that maximizes , maybe we cannot make every pair i, p _{ i} in different subtrees.
Sorry for my poor English.
I think that g(x) should be instead of in div1.C, or it will not satisfy
Thank you, fixed now.
What is the complexity of solving the problem Div 1 D?
Could somebody please tell me what 'the left part' and 'the right part' respectively mean in Div1.D? I feel it hard to understand. Thanks in advance.
In problem Div2 D ( Two Sets ) , I can't understand how it is possible that splitting Odd number of elements in sets ?! because all of the elements in every set must be pair.
Can somebody help me to understand ? ( Small sample )
Sorry for my poor English.Thanks
a=2, A={1}
I spent several hours to figure out the solution for Div 1 B/Div 2 D, so I wrote a solution with bunch of explanation. Hopefully someone will find it helpful.
7940575
Thank you for the explanation!
very beneficial
I think test case of Div I E is a little weak. in my code, when I choose random edge from list[], and delete the edge, it get TLE in test case 34, but if I choose edge list[0],and delete it get AC 280ms, if I choose edge list[cnt_list-1],and delete it get AC 311ms...test case should be stronger.
For the problem "469B — Chat Online", could you please elaborate on the solution for the problem with the limits as detailed under the "Bonus" section? I can't think of any good way to go about doing it.
Can someone explain me why in Div 1 B/Div 2 D we can't just go through the numbers and for given x that is not already in the set check if there is a-x or b-x not assigned yet and put them in the correct set or if that a-x or b-x doesn't exist print "NO"? Can you give me a small example where this method falls?
More precisely — why this code doesn't work? :) http://codeforces.ru/contest/469/submission/7915436
Edit: It fails on this test: 2 6 10 3 7
Edit2: Now it works on the previous test, but still getting WA. Updated code: http://codeforces.ru/contest/469/submission/8051352
The number of contestants who passed Div1.D & Div1.E is maybe too poor... I think these two problems are too difficult for a CF round. Can anyone explain the tutorial more clearly? Thanks a lot.
There is a brute force approch for Div I E, hope some one can prove it has reasonable time complexity or find a data case to challenge it:
idea is simple, just 2^n brute force search: for every state first check wether the graph in connected,if it is not connect solve every connected part independently and multiply result.
if it is connect, then choose an edge with least number of inner and outer degree(after delete it it is most probably disconnected), delete or choose it. If we delete it just search the remain part of edges.If we choose it, since we must choose the node with inner and outer degree at most one,so we must delete all the edge connected edges with two nodes (inner connected with outer node,and outer connected with inner node). use hash to speed up search.
Problem: Hack it. (Solution 4)
Can someone explain this please...? "That means if we shift the interval [x + 1, x + 10^18] by 1, the result will be increase by 1 too."
Hi 2333333333333,
Div.2 Problem D, regarding the first idea using Disjoint-Set:
In your submission, what are the arrays f, vs, sta, p?
i just want to say : zhangzhishil.
Can we solve div1.B using exgcd ?
I think there is a problem in test case 27 for 469A Div 2
The input is: 3 1 2 2 2 3
which should give the output "I become the guy." according to the problem but the test case says the output should be "Oh, my keyboard!" which is incorrect.
If I am wrong can someone explain this logic to me or can the test case be changed?
You've probably figured it out already, but I'll post an explanation nonetheless, for sake of future generations :)
The first number of the second and third lines isn't the number of level Little X or Little Y can pass, it's the total number of levels Little X or Little Y can pass.
I.e. the number in this test case should be read as follows:
3 — there are 3 levels in the game; 1 2 — Little X can pass 1 level, namely, Level 2; 2 2 3 — Little Y can pass 2 levels, namely, Levels 2 and 3.
I, too, missed the point in the task description and spent quite some time puzzling over this test case :)