Meet in the Middle lecture & problem-solving starts in an hour https://www.twitch.tv/errichto. See the problem list below. I will later update this blog with codes and written explanations.
UPD, video recording: https://youtu.be/18sJ3mK173s, some codes from the stream: https://ideone.com/1uScID
P1. Knapsack with $$$n \leq 40$$$ and values up to $$$10^9$$$ https://cses.fi/problemset/task/1628
P2. Given a sequence $$$a_1, a_2, \ldots, a_n$$$ ($$$n \leq 2000$$$), count increasing subsequences of length 3.
P3. 4-SUM, find four values that sum up to the target value https://cses.fi/problemset/task/1642
P4. Find a string with the standard polynomial hash equal to the target value $$$X$$$ modulo $$$10^9+7$$$. The hash is computed by converting characters a-z into 0-25 and multiplying every character by the next power of 26. Find a solution without just converting $$$X$$$ to base $$$26$$$.
P5. You're given a graph: $$$n \leq 300$$$, $$$m \leq n\cdot(n-1)/2$$$. Count paths made of 5 nodes. Nodes and edges can be repeated.
Bonus 1: Count simple paths only. No repetitions allowed.
Bonus 2: $$$n, m \leq 2000$$$
Similar problem: https://mirror.codeforces.com/blog/entry/94003
P6. You're given a sequence $$$n \leq 10^6, 0 \leq a_i < M = 10^9$$$. Find two subsequences with equal sums modulo $$$M$$$. https://quera.ir/problemset/olympiad/34090. The two subsequences can have common elements.
P7. Number Clicker https://mirror.codeforces.com/contest/995/problem/E. You start with the number $$$a$$$ and want to get $$$b$$$ in at most 200 moves. You can increment, decrement or change the current number into its modular inverse, all modulo prime $$$p$$$. Find any valid sequence of moves.
Such streams are much appreciated. Please bring such streams more frequently.
Once a week or once every two weeks is fine I guess. He does problem solving streams also for both divisions, so it's the right balance in my opinion. There have been other such educational streams in the past (in case you didn't know) which you can find at his other youtube channel.
Thanks for this!
Just a heads up, using an
unordered_map
TLEs on the 4-SUM problem whereas amap
gets ACI only knew about the version of birthday paradox where sampling O(sqrt(M)) values from [0, M) will have a high chance of finding two numbers that are equal. In the stream, the version of birthday paradox you used (for both p4 and p6) was that you will have a high chance of finding two numbers such that (x+y)%M == C for some target number C. I can see why the second version is true too (still trying to hit M possibilities out of M*M, using sqrt(M)*sqrt(M) samples) but it doesn't seem derivable from the regular form of the birthday paradox.
Was that second version just a well known fact? Or is there a stronger form of the birthday paradox that you're using that can make such variations "obvious" to see? Are there any other variations of the birthday paradox that you've seen in problems besides x==y and x+y%M==C?
thanks very much for this educational contest
today i found a problem related to this blog(Kickstart2021 Round G 3rd problem). problem link is below. (https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b44ef) below is the link to my solution. (https://pastebin.com/2Svgwwen)
What is the solution to P6? I tried to random shuffle the input, then generate all subset sum of the first 19 elements and the last 19 elements but it failed on around 7 tests. Here is my code:
Thanks in advance!
My solution failed on tests 74 -> 78, I'm wondering if you've found a solution that passes all tests?
P1: https://cses.fi/paste/d1447ba3a7b8ca245e01a7/
Why does this give TLE? Is it because of the hashmap performance?
Yes, but I used a regular map and faced the same problem.
Pushing in vectors, sorting and using 2 pointers, is much faster there, but I think it doesn't matter on other platforms.
Time limit of this problem is quite tight, so you need to use the fastest ever technique. For me there are two that worked: storing subset sums in a vector, sort that vector and for any x find the complement y such that x + y = target. This can be done through Binary Search (upper_bound — lower_bound) ==> Accepted
Now unordered map seems to be a good idea, and indeed it is, except the fact that unordered_map suffers from collision with big numbers, then it returns from O(1) to O(N). So you have to use a custom hash function that is non-deterministic to avoid this collision problem. You can find the solution for collision here
888E - Maximum Subsequence Relevant Problem