dfsof's blog

CF618F, CF1836E, and the Beijing College Entrance Exam
By dfsof, history, 17 months ago, In English

These three problems are almost the same.

CF618F [Double Knapsack]: https://codeforces.me/problemset/problem/618/F

CF1836E [Twin Cluster]: https://codeforces.me/contest/1836/problem/E

Beijing College Entrance Exam:

Given two positive integer arrays $$$A$$$ and $$$B$$$, such that:

$$$len(A) = len(B) = n$$$

and

$$$\forall 1 \leq i \leq n$$$, $$$1 \leq a_i, b_i \leq n$$$.

Prove there are subsegments $$$[x, y] \subseteq [1, n]$$$, $$$[z, w] \subseteq [1, n]$$$ such that $$$\sum\limits_{i=x}^y A[i] = \sum\limits_{j=z}^w B[j]$$$. For example, $$$n=4, A=[1,2,3,4], B=[4,4,4,4]$$$, then $$$x=4, y=4, z=1, w=1$$$ is a solution.

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think twin cluster is pretty different, unless you consider every problem that considers pigeon hole principle the same (it is all same mindset but setup and realization is different).

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But twin cluster is also prefix sum + pigeon hole?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So is half other pigeonhole problems.

      → Reply
»
17 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I agree that Twin Cluster should not be grouped with the others. Anyway, see Putnam 1993 A4 as well.

→ Reply