When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Errichto's blog

By Errichto, 2 years ago, In English

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://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://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.

  • Vote: I like it
  • +242
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Such streams are much appreciated. Please bring such streams more frequently.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this!

Just a heads up, using an unordered_map TLEs on the 4-SUM problem whereas a map gets AC

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I 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?

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

thanks very much for this educational contest

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
10 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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:

Code

Thanks in advance!

»
10 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

P1: https://cses.fi/paste/d1447ba3a7b8ca245e01a7/

Why does this give TLE? Is it because of the hashmap performance?

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    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