Thanks for the participation!
1323A - Even Subset Sum Problem was authored and prepared by vintage_Vlad_Makeev
1323B - Count Subrectangles was authored and prepared by vintage_Vlad_Makeev
1322A - Unusual Competitions was authored by vintage_Vlad_Makeev and prepared by DebNatkh
1322B - Present was authored by meshanya and prepared by wrg0ababd
1322C - Instant Noodles was authored by vintage_Vlad_Makeev and prepared by ch_egor
1322D - Reality Show was authored by voidmax and prepared by okwedook
1322E - Median Mountain Range was authored by Sender and prepared by grphil
1322F - Assigning Fares was authored by mingaleg, vintage_Vlad_Makeev and prepared by KiKoS
Tutorial is loading...
Tutorial is loading...
c++ code by gritukan
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Why editorial for D1C in Russian?
fixed
How is it written 2weeks ago?
Just look at the announcement;)
Div1.D reminds me 2048.
By 2048, what do you mean?
google 2048, game
can anyone explain div2 D problem
How can I split the vertices with same neighboring set in div1 C? I tired hashing with mod 1000000009 and add vertices with same hash values, but got WA at main test 88 :(
With hashing you need two modulos to avoid conflicts
trying not well-known modulos(or return pair of integer with different modulos as hash value) might help.
I highly dissuade hashing (multi)sets modulo a prime. Instead: assign random 64bit integer for each element, and use xor/sum of all elements as hash of the whole set (xor if we are guaranteed there are no repetitions, or we do want repetitions to cancel out, sum if we're hashing a multiset). To get those values of each element I use following function:
And value used for x is mix(x), or in case of rounds with hacking mix(x ^ salt), where salt is value returned by chrono::steady_clock::now().time_since_epoch().count() at the beginning of runtime. This is way faster than anything using modulo, uses all 2^64 possible hash values, so avoids any birthday paradox issues, also avoids any overflows/issues with and requires way less code than using more than one modulo.
Moreover this technique can be used for hashing other objects than sets, e.g. sequences, which can be represented as set of pairs $$$(i, a_i)$$$, the only difference is that now we need random value for each pair, but this can be easily done e.g. by
And finally: using well-known modulos is not an issue, as long as you use random number as base (guaranteed by Schwartz–Zippel lemma).
really appreciate it! thanks :D
Hashing sequences modulo two highly non-random primes has always worked for me. Your method seems better, but the critical part is avoiding outright bad hashes and the second is avoiding easy hacks, the rest is finetuning.
thanks a lot!!
Hey, would it possible for you to give a little insight on its applications and also could you give some links to your own codes using this methodology so that I can study them.
Using a map passes in a little bit less than 1s 72663606. Memory is easy to analyze here since total number of elements in all vectors in the map will be equal to $$$E$$$ (where $$$E$$$ is the total number of edges). But I'm not sure how to analyze the time complexity of this solution.
Insertion:
comparing two vectors a,b takes $$$min(a.size(),b.size())$$$. In balanced BST like map comparison occurs $$$O(log(n))$$$ times (n -> size of map before insertion). So when inserting vector of size s, time is $$$O(s*log(n))$$$. So inserting multiple vectors with combined size $$$m$$$ is $$$O(s_1*log(n))+O(s_2*log(n))+ \ldots = O(m*log(n))$$$
Retrieval : similar to above analysis.
Got it. Thank you!
You can just keep a map<vector< int>,long long>, where the key (vector< int>) is the list of all connected vertices and the value is the sum. This passes in about 800ms.
How to analyze the time complexity of this solution? How to calculate the upper bound on the total number of comparisons made in the map?
Good question, I'm not at all sure. Maybe someone can hack our solutions. But if i had to guess, I would say that it can not be hacked and maybe someone can show that the complexity is something better than $$$O(n^2 log~n)$$$.
Well, the number of comparisons is $$$O(\log m)$$$ and each comparison takes $$$O(size)$$$. Since you search every vector in map only once and the sum of all sizes is $$$m$$$, the complexity is $$$O(m \log m)$$$
Your text to link here... I was calculating equivalence classes of vertices on the right (v ~ u iff N(v) = N(u)), adding vertices to the left part. The complexity this procedure should be around $$$O(V\log{V} + E)$$$.
Is the time limit of Div1B set according to $$$O(n \log n \log C)$$$ solution? My submission 72640450 runs 2979ms, which is very close to get TLE.
Yes, it's pretty tight, but the first thing I wrote runs in 2 seconds and it's easy to optimise — e.g. by handling small bits more easily because everything is small when we discard larger bits.
I will try to provide some intuition to the solution of Div1 C.
Look at the image below, each node in the left half of the graph is drawn as a cricle (denoting a set, not the problem's defined set, but a new set we're going to define). The numbers in the rectangles are the ID's of the nodes and the characters are the elements included in the node's set. These set elements (the characters) represent sum of node values of the right half of the graph.
For example, if $$$S = \{ 0 \}$$$ then $$$F(S) = a + b + c + d$$$. if $$$S = \{0, 2\}$$$ then $$$F(S) = a + b + c + d + f + g$$$. Note that each character in picture may denote more than one node in the right half of the original graph.
Now assume you've computed the gcd of all intersections of sets like the editorial have mentioned in the first paragraph. In the image below this will mean you've computed $$$gcd(a, g, e, d + c, b + c, c + f, c) = m$$$
You will observe that if you union any number of sets now, the summation will (hopefully) be multiple of $$$m$$$. For example if $$$S = \{0, 1\}$$$ then $$$F(S) = a + b + c + d + e + f$$$, or if $$$S = \{0, 1, 2\}$$$ then $$$F(S) = a + b + c + d + e + f + g$$$. You will find that each term in the summation is a multiple of $$$m$$$.
I'm not sure how to prove this formally (if someone can formalize all this trash, it would be appreciated!), but I wanted to show some intuition on how one would approach such problem.
The text of the editorial for problem Div1C (D1C) is not ideal.
For further clarity, I think the author had something like the following in mind. For example for the instance: LeftSide={a,b,c,d,e}; RightSide={X(11),A(7),B(8),Y(10)} and edges {a,b}-->{A,X}, {d,e}-->{B,Y} and c-->{A,B}, by what I understand for the editorial solution, the partition would be something like this:
Set1 = {A,X} with value sum(11+9) = 18. Set2 = {B,Y} with value sum(8+10) = 18. Set3 = {A,B} with value sum(7+8) = 15.
Clearly any non-empty subset of the LeftSide elements will have as sum a linear combination of values from the resulting sets Set1..Set3 above. Including the one with a single 1 and all 0s. As such, clearly the solution is the CMMDC of the values of these sets.
The tricky part however stirs from the fact a single right hand side element (A or B in the above example) can belong to several partitions. I am not sure the author covered the part about constructing such partitions (and proving there cannot be too many of them) properly (detailed enough).
My own approach (did not have time to finish implementing it during the contest), relied on the following observations: the sum of any subset is of the form
Sum(Right(a1))+..+Sum(Right(ak)) - Sum(Intersect(Right(a1),Right(a2)) - ... - Sum(Interesect(Right(a[k-1]),Right(ak)))
. Thus all we need is the CMMDC of all singleton sets to be further reduced to common multiples to Sums of each pairwise intersection of right-hand sides of all singleton sets.An exercise in formalization for readers: think of how 908E - New Year and Entity Enumeration and this are related, and what properties of the GCD function we use.
It's my code:https://codeforces.net/contest/1323/submission/72668413
I just use the loop. esay,but of course TLE.So, I have some trouble.
I do not really understand the editorial.
And, what should I do to improve my code.
please help me, thanks!
Your code runs in O(n^2). Your solution is a straight forward brute force. However, you should find an another solution in many problems due to time limit.
If the intended solution was O(nlognlog(1e7)) for div 1 B, where can I reduce the constant factor in my code. I am not very experienced in optimizations so any help is appreciated.
Completely different solution to D1E:
Not everything in here is sound, but it's possible to write down and analyze all formulas and find out everything should be OK with this solution.
Total runtime is $$$O(n + \text{RMQBuild} + n \cdot \text{RMQQuery})$$$. When RMQ is implemented using a sparse table or a segment tree, we end up with a very fast $$$O(n \log n)$$$ solution: 72662345. Using the optimal RMQ, we can solve the problem in $$$O(n)$$$ time.
Can someone walk me through the complexity of D2 B of the editorial. I thought it will led to TLE but it didn't.
So, final complexity is O(sqrt(k)*(n+m)).
What was the intended complexity of div2B? I can see so many solutions running in about sqrt(k)*(n+m). Shouldn't that TLE?
I had come up with something similar too early in the contest but didn't submit because I thought it will TLE :/. Ended up submitting an optimisation of the same, which runs in somewhat similar complexity.
Well, complexity sqrt(k) * (n + m) will have TLE. This sqrt(k) comes from finding all divisors of k. You don't need to do that. You only need to find divisors d such that either (d <= n and k / d <= m) or (d <= m and k / d <= n), others are just too big. And that will be fast enough.
Yeah, agreed. What I meant to ask was, why are submissions like these [LINK] getting accepted ? Isn't this exactly sqrt(k)*(n + m) complexity, which is of the order 10^9 as per the given constraints ?
I'm also not sure why submissions like that are accepted. In my solution, I did loop sqrt(k) times, but in my precomputation I only stored the maximal consecutive lengths and put them in a map. With some basic math you find that the number of entries in the maps are bounded by sqrt(n) and sqrt(m), so my solution ran in sqrt(k)*(sqrt(n)+sqrt(m)).
Yeah I did the same during the contest. But after the contest ended I saw so many solutions being accepted without using map and traversing over the entire array. Wasted a lot of time in this unfortunately :/
it's not sqrt(k)*(n+m), it's d*(n+m) where d is number of k's divisors. i think d can't be more than 1000, that's why this solution fits in 1s.
Oh yes you're right! Thanks! I need to learn how to correctly analyse the complexity xD
The upperbound of number of divisor of a number N is considered n^(1/3). So it's not sqrt(k)*(n+m), but it's (k^(1/3))*(n+m)
But this should get TLE too. In worst case k = 16e10 and (n + m) = 8e5
==> (k^(1/3))*(n + m) = 5e3 * 8e5 = 4e9, then how is this running within a second?
I solved this question by preprocessing both arrays to store count of contiguous 1s only (as mentioned in previous comments).
Look at the constraints again, n,m<=4e4 not 4e5. So n+m<8e4 and k<=16e8. Hence (k^(1/3))*(n+m)=1e3*8e4=8e7
Okay got it. My bad
There's also a nlogn solution. Link
In D you can also be an idiot, not reverse the sequence, and barely pass in 1980ms like this: 72679047. The complexity is $$$\mathcal{O}(nm \log m)$$$, were you trying to cut solutions like this?
I didn't quite get the editorial of Div.1A, can someone please explain it to me?
Can someone please explain their intuition and code behind Div2D/Div1B? The tutorial doesn't help me much.
For Div2D / Div1B, I think people counted in a different way as editorial, the number of pairs which have k'th bit set in their sum. Can someone share a better approach?
hey could u please explain the logic behind div 2 D problem(present).. i did not get much from the editorial ..thanks in advance
Sure.
Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also. 2e7 is contained in roughly 25 bits. We check for each bit of ans whether it will be turned on or off.
For kth bit of ans, we see in all the pair-sums ( $$$a_i + a_j$$$ for all i and j), the kth bit of them. So if the number of pairs having kth bit set are even then for the kth bit, their xor is zero, else one. So kth bit of the answer = xor of all the kth bits of the pair-sums.
To find the count of pair-sums having kth bit set, we notice that we can mod all $$$a_i$$$ by $$$2^{k+1}$$$.
Because say X and Y belong to input array and S = X + Y. Then X + Y can add up to have their kth bit set which means $$$S >= 2^{k}$$$ .But also notice that they can have a carry over from addition which makes numbers in range $$$[2^{k+1}, 2^{k+1} + 2^{k})$$$ have their k'th bit not set. So we only care about the kth and (k+1) th bit of all the numbers to check the xor of kth bit.
After modding we say that for a sum to have kth bit set, it can take values from $$$[2^{k}, 2^{k+1}) \ \cup \ [2^{k+1} + 2^{k},$$$ Max-Value-Sum-Can-Take $$$]$$$ (Check the why spoiler to know why)
To find the numbers in the proposed ranges, we simply make another array $$$B$$$ of modded $$$a_i$$$'s and sort them. Then we can assume sum, $$$S = B_i + B_j$$$ . Iterate over $$$i$$$ in $$$B$$$, find maximum bound of $$$j$$$ using binary search (built-in lower_bound or upper_bound functions in C++). For example if we want to find $$$B_i + B_j <= P$$$ then $$$B_j <= P - B_i$$$. So fix $$$i$$$ and since array is sorted we find the last $$$j$$$ that satisfies the given condition and all the numbers in the range of indices can be added to the count to check the xor.
Code : 72719677
Let me know if I missed something or made a mistake.
Got it...thanks a lot brother ...i realy appreciate your efforts ..keep on helping like this ..thanks a lot once again i wish i could give more than one upvote to you ..
Hi, thanks for the detailed solution.
I understood the core part.
However, I didn't understand the following:
Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also
$$$1e7$$$ actually is a notation for $$$10^7$$$. Max value of $$$A_i + A_j$$$ is $$$1e7 + 1e7 = 2e7$$$. Now all the pair-sums can have value $$$2e7$$$ and we are xor'ing them. And we know that for two integers, $$$P\ xor\ Q <= P + Q$$$
Why? Because $$$P + Q = (P xor Q) + 2 * (P & Q)$$$
Thanks a lot!
And, thanks for quick reply!
Keep helping others!
thx vro
Is this solution (72639972) to div2B hackable? It's $$$O(n \cdot numDivisors(k))$$$, which might be a bit slow with standard Java HashMaps
Largest possible highly composite value for $$$k$$$ is $$$1396755360$$$ (source)
Maps $$$Ar$$$ and $$$Br$$$ are bounded by $$$O(\sqrt n)$$$ distinct lengths.
Update: This is my hack attempt generator: https://pastebin.com/2wyjDVMB . Local testing seems to indicate that my solution should still pass with it though (about 70ms, excluding input and startup overhead). Maybe excluding out-of-bounds divisor pairs sped it up enough to be unnoticeable with these input constraints, or even improve the big-O bound.
Update 2: Yep, was unsuccessful. Thanks anyway
My solution was also $$$O(n * numDivisors(k))$$$. What is the upper bound of this complexity that it passed in the time-limit?
Big-O estimates are by nature an inexact science, but the literal formula evaluates to about $$$6 \cdot 10^7$$$, which could be on the edge of 1 second if the constant factor is large enough. I thought using HashMaps might push me over the limit, but I think I might have overestimated the runtime complexity of my solution, considering how fast my thought-to-be-adversarial case ran.
I believe that the intended solution is meant to be $$$O(n^{1.5})$$$.
Thank you for the response. I am interested in knowing what is the literal formula you're talking about that you calculated it to be $$$6e7$$$ ? Are you approximating the maximum number of divisors with some approximation?
I did link to a source with a list of highly composite numbers and their corresponding number of divisors, but it was hidden under the spoiler: https://gist.github.com/dario2994/fb4713f252ca86c1254d
I see. Thanks :)
For div1 B,you can use two pointers and radix sort,then the time complexity will be n log C.
Could you explain the solution more clearly? thanks.
It is same as the editorial.
But for the sorting,use radix sort($$$O(n)$$$) instead of quick sort($$$O(n\log n)$$$).For the search,use two pointers($$$O(n)$$$) instead of binary search($$$O(n\log n)$$$).
OK, thanks for your explaination.
Can you please further break it down? I'm struggling to follow the explanation in the editorial
You can refer to this
Thanks. I'm having trouble understanding how did we calculate the ranges? Will you be able to elaborate on how your binary search is working in the same context please?
We exploit the fact that B is sorted.
Let $$$B = [2, 3, 5, 6, 9]$$$ and suppose you have to find $$$B_i + B_j <= 11$$$ . Now to solve this we iterate over $$$i$$$ from range 1 to N (size of B, which is 5 here and B is 1 based indexing).
For i = 1, we can take j = 2, 3, 4, 5
For i = 2, we can take j = 3, 4
And so on..
Now to find the last value of $$$j$$$, we perform a binary search in range $$$[i+1, N]$$$ which finds the greatest index $$$j$$$ that satisfies $$$B_j <= 11 - B_i$$$ . Google the working of lower_bound and upper_bound to understand how to implement such a binary search.
After finding the last $$$j$$$, we conclude that all indices from $$$i+1$$$ to $$$j$$$ can pair with $$$i$$$ to satisfy the problem in hand. So we add $$$(j-i+1)$$$ to the answer.
Before asking questions, you should first google your problems to check if this kind of question is popular enough that people have answered it already. For example here, googling about upper_bound and lower_bound on geeksforgeeks or even C++ documentation, would have helped you :)
After modding we say that for a sum to have kth bit set, it can take values from [2k,2k+1) ∪ [2k+1+2k, Max-Value-Sum-Can-Take ]
I'm not sure how these values came about ^
If the most significant bit of a binary number is (k+1), then for a number to have kth bit set, it is necessary to be >= $$$2^k$$$. All the numbers from there to the max val of the binary numbers with (k+1) MSB, except numbers from $$$2^{k+1}$$$ to $$$(2^{k+1} + 2^{k} - 1)$$$, will have kth bit on. Please take k = 2 and draw binary representation of each number to find out why. (I have already explained in the why spoiler in my original comment — it is because of the carry over in addition of binary numbers). If you still have doubts, please personal-message me.
Could you please explain, how to use two pointers instead of binary search?
I think the time limit for Div2D is quite tight, I had a O(nlogc*logc) solution using Fenwick Tree but got a TLE
Can someone explain div1D because I can't get much of what the editorial is saying?
why 1323 B , gb[k/i] is not giving runtime , i applied same logic but got runtime at tc 5 ... Please someone clarify
It is probably because k/i goes up to 10^9, which is beyond the size of the array declared. You only need those factors of k which are less than n and m. Basically i <= n and k/i <= m. It should work if you handle this case.
thanks ,i just added this condition and solution got accepted...
72713269
for question B, Count subrectangles : plz can somebody tell me why following code in giving wrong answer in test case 7??
include <bits/stdc++.h>
define int long long int
using namespace std;
int max(int a,int b) { return a>b?a:b; }
signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //cout<<"I must do it...Yeahhh";
}
Thanks in advance
Bonus of 1322B:
Use
std::stable_partition
as the replacement of $$$O(n \log n)$$$ sorting.Before solving the k-th bit of the answer, partition $$${a_i}$$$ according to the k-th bit, too. Then, incrementally, $$${a_i}$$$ is sorted modulo $$$2^{k+1}$$$.
What's the $$$O(n)$$$ solution for E?
It's quite complicated. Let's call mountain high if $$$a_{i -1} \le a_i \ge a_{i + 1}$$$ and low if $$$a_{i - 1} \ge a_i \le a_{i + 1}$$$. As we know, changes will happen to consecutive segments of mountains, where for each odd $$$i$$$ $$$i$$$-th mountain is high and for even $$$i$$$ $$$i$$$-th mountain is low, or vice versa.
Now let's assume that all heights are different. Then let's look for each low height $$$a_i$$$ and find, on which positions at some time there was mountain of height $$$a_i$$$. It can be noticed that there is a contiguous segment of such positions, and to find it's left border we should look at first low mountain on the left (on position $$$x$$$) which is higher than $$$a_i$$$ and first high mountain on the left (on position $$$y$$$) which is lower than $$$a_i$$$, and the left border is middle position between $$$i$$$ and $$$max(x, y)$$$. The same with right border and for high mountains. Then we can look at 4 different variants of $$$max(x, y)$$$ on the left and on the right and using only this information we can find on which positions the height $$$a_i$$$ will be in the end. For more details you can look at my code for this problem,
Where's your code?
Here is it: https://codeforces.net/problemset/submission/1322/72965891
For Div1 B, 72638208 doesn't check the sum to fall in two ranges and just uses one pass instead of four passes. Anybody know why?
Can anyone explain Div1D. I have no idea what the editorial is saying.
After reshuffling 2 segments of total length 8, we can get a right bracketed sequence:()()((()())
it isn't right bracketed.
Can anybody explain how to use two pointers method in Div2 D?
Is editorial's proof of Div1C(Instant Noodles) correct on this test?
I have been trying to understand the editorial for Div.1 D for a whole day, but I still can't get it.
Now I have a question about the problem description:
"The show host reviewes applications of all candidates from $$$i=1$$$ to $$$i=n$$$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $$$i$$$ is strictly higher than that of any already accepted candidates, then the candidate $$$i$$$ will definitely be rejected."
Does it mean we should first choose the set of participants to accept which $$$l_i$$$ is non-ascending then let them do the show and fight against each other? If a participant was defeated, is it still regarded as "already accepted"?
In the tag of div2 B problem, it is showing binary search as a tag, but there is no use of it in problem, why it is so?
I wrote a more detailed editorial of 1332E — Instant Noodles I wanted to write it down so that I could understand it more.
https://gist.github.com/mightymercado/9f281177bcb9d39b7d55ff4a9ab29f4d
why does this tle for count rectangles submission, i have basically the exact same thing as editorial said
I took part in the competition in Moscow and now I wanna ask you — is there a place where I can read tutorial like this here but about the other two problems (“Double palindrome” and “Latin Square”), that weren’t included here in this Codeforces round. It’ll be great if I can also practice them somewhere. I’ll be very grateful if somebody helps me :).
nobody used stack for div1 A 1322A - Unusual Competitions ?
Implementation of ques C-Unusual Competition using Stack, storing position of unbalanced braces. https://codeforces.net/contest/1323/submission/97906786
why count subsequences problem have binary search tag??