Codeforces Edu Round 100 Notes

A:
Insights
- Every 7 rounds, you do 6 + 3 = 9 damage total (6 rounds of 1 damage each, 7th round you do 3 damage)
- So total number of rounds = Total health divided by 9, must be an integer
- If k = TotalHealth/9, all monsters (a, b, c) must have at least k health
 - Check that this is true: a >= k && b >= k && c >= k

Just check these conditions, print YES if true, NO otherwise


B:
Insight
- You can satisfy a stronger condition: all elements divide/can be divided by all other elements
- i.e. instead of b_i | b_i+1, it's (b_i | b_j or b_j | b_i) for all i,j
- How? Just make everything a power of 2
[1 2 3 4 5] -> [1 2 2 4 4]
[3 4 8 1 2 3] -> [2 4 8 1 2 2]
- This satisfies the condition by moving each element by at most half their original value
- this is because the greatest power of 2 less than x is always at least x/2
- this is because for all x in [2^i, 2^{i+1}), x < 2^{i+1}


Alternative solution (which i didn't come up with):
   - set either all even or all odd indices to 1
     - pick whichever yields a smaller sum. sum(elts chosen) is guaranteed to be less than half the total sum, so sum(elts chosen - 1) is even more guaranteed to be less than half S


C:
Sample 1:
3
1 5 --> at time 1, move to point 5.
  - RECEIVED; at time 1, we were at 0 (robot's current destination)
  - Not a success! we did not reach 5 before time 3!
3 0 --> at time 3, move to point 0.
  - IGNORED; at time 3, robot is still moving towards point 5 (and is at x = 2).
  - Not a success! Never reached 0.
6 4 --> at time 6, move to point 4.
  - RECEIVED; at time 6, robot is at 5 (robot's current destination)
  - a SUCCESS! We eventually hit point 4 (at time 7)


Insight: a robot is either moving or at its destination
--> Simplify the condition for ignoring. Not Moving iff At Destination
  (where destination := the most recent target it was given that wasn't ignored)

## Simulating the robot
  So, just keep track of two things about the robot:
  1) Where is it? (`cur`)
  2) Where is it going? (`nxt`)

  (And keep track of the current time as you iterate over events)
  Maintain these 2 state values over time.

## Producing the answer
  How do you determine if a command was successful?
  A command (t_i, x_i) is successful iff [cur, ncur] includes x_i
  cur := position of robot at t_{i}
  ncur := position of robot at t_{i+1}
  NOTE: This is not the same as [cur, nxt] includes x_i; although the next command m ay be ignored & not affect `nxt`, the condition for success still depends on t_{i+1}



Solution: simulate the robot and record its path: cur = vector<int>(n)
Read x[i], cur[i], cur[i + 1] to answer query i.



D:

Sample 2
5
1 4 5 9 10


XOOXXOOOXX
1234567890

## observations
let's say, x = 0. so always take max of any pair
every time you see an X, it _must_ be the max of some pair; so, pair it with some O that came before it.

-->
X's are )
O's are (
it's possible to solve iff the resulting string is a balanced paren string

now what happens when you do x = 1?
now, one of the pairs (so, 1 X and 1 O) gets flipped; i.e. X must come before O
normal order is O before X
but one special pair will be X before O!

what does this mean for our transformation to a parentheses string?
- greedily flip the first ) in the string and the last (, to be ( and ) respectively.

   - as you increment x, keep flipping the ) and (.


## implementation strategy
- read: 

E:

Come up with a list that satisfies the following two conditions
Condition 1:
- Tree order; no child precedes parent in list
Condition 2:
- Chained nodes: y_i immediately follows x_i in list

Question: Produce such a list, or print 0 if none exists

## Observations
1) Connect chains (a->b, b->c) ==> (a->b->c)
2) BFS, starting with the root.
  - when visiting a node, enqueue all its valid children
  - when popping off a node, visit it and all nodes in its chain
3) a node is valid iff:
  - it's the head of chain
  - all nodes in its chain [incl. itself] are "ready", i.e. parents have been visited before
  - special case: if a node's parent is in the same chain (and earlier), treat it as "visited already"
    - i handled this in a jank way. but i think it doesn't cause issues!

4) At end of bfs, if not everything visited, output 0 [will happen if there's a cycle of dependencies, either within a single chain or involving multiple chains]


F:

Given n, x, y:
find maximum size of set in {1...n} that has no two elements that differ by exactly x or y

## Observations (not all useful)

1) if x, y both odd, you can always pick {1, 3, 5, ...} -> ans is (n + 1) / 2
2) if x, y not both odd, there is no equivalent trick :(
3) answer is upper bounded by O(n/2), because for each 0 <= m < x, you can consider the sequence
m, m + x, m + 2 * x, ....

So you get x sequences, and within each sequence, you can only take at most every other elt
So in total, it's ~ half
4) you can use bitmask dp to solve the problem up to n = ~100 (O(2^{23} * n)


(note: Insight 4 is the only useful one so far)

Insight 5 (the most important one)

Let m be max elt of S. ("elt" is short for "element")
then m + x + y can be added to S
because m +x & m+y already forbidden

so, this strongly hints at the hypothesis that the answer S will be periodic with period x + y.
in other words,
   ***take i iff i + x + y.***

- so this is what i used in my final (accepted) submission, it is probably true, i don't have a proof yet