Skip to content

Instantly share code, notes, and snippets.

@stevenhao
Last active December 18, 2020 03:14
Show Gist options
  • Save stevenhao/b203645f59218ca59aaa4cbd447f8a61 to your computer and use it in GitHub Desktop.
Save stevenhao/b203645f59218ca59aaa4cbd447f8a61 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment