Codeforces Round 918 div4

 

Codeforces Round 918 (div 4)

 

Problem A

Use the frequency to determine the element that appears once.

 

Problem B

Have a set for each row and column with "ABC" and remove characters in specific (r, c) pairs. And there will remain a single set with just one character. 

 

Problem C

Determine if the sum is a squared integer.  Can use math.sqrt to determine this.

 

Problem D

1. Create string of C and V for identifying the consonants and vowels.
2. create a deque to store the locations of dots.
3. Iterate over the CV string, and anytime you find CC, that means it must be CVC was the prior syllable.  Cause you found a CVCCXXX,  The other pattern that can appear is if XCVCVX,  if you see VCV, that means there must be a CVCVX,  You know there was a CV pattern before the CV of most recent.  Which the most recent could be a CVC, you don't know what X is yet.  But you know for the CV of prior.  Another observation is that you are looking for double CC, cause that will always indicate a CVC syllable.  Then it is just determining what would indicate a CV syllable. 
4. The dots are sorted in the deque, so now iterate over the original string and whenever the front element in deque matches the index that is a location for a dot so append to list
5. Convert list back to string.

 

Problem E

This solution fails, because the set solution was hacked.  But it is fast on average, but it can have worst case O(n) time.

 

1. Track the even and odd prefix sum for the array.
2. Iterate over the array in order and determine if the current element should be added to even or odd prefix sum.
3. Compute the difference between the prefix sum
4. Check if this same difference has been found earlier in the loop.  Cause if it was you can imagine that is the start of your current contiguous subarray where even sum = odd sum.  And the end of current contiguous subarray is current location.  It makes sense because if even was greater by 2 earlier and is greater than 2 now.  You can realize the skew is the same so it cancels out.

This proof shows that the even and odd prefix sum are equivalent when the even sum has the same difference from odd sum at two points in time.

 

I didn't think of this, but you could use one prefix sum, and just set even integers to be negative, and you would then be looking for when there is a contiguous subarray with sum = 0.

 

So we just need to check if there is a subarray with sum 0. This is a standard problem with prefix sums: if two prefix sums are equal, then the subarray between them has sum 0; otherwise, no subarray has sum 0.

 

From <https://codeforces.com/blog/entry/123952>

 

The AC solution is below

1. Convert all of the odd index elements to negative, so you will have a0 - a1 + a2 - a3 + a4 + ...
2. Then you can calculate prefix sum from this, and if it ever equals 0 for instance that means the positive even and negative odd index cancel each other out and also means they are equal.  But it isn't always going to be the case you see 0, if you see any repeated value in the prefix sum that represents a subarray sum equal to 0.  Cause 2 - 2 = 0 for example, if you had 0, 2, -1, 3, 2 => this subarray from 2 to 2 is actually 0. Which is the goal.
3. So you can just sort the prefix sum array and find when two adjacent elements are equivalent.

 

Problem F

1. Sort the points (a, b) and also store the end points b in their own list.
2. Loop through the end points in sorted (ascending order) and create an index_map for them as well.  That is map each b to an index.  This will be used for coordinate compression
3. Create a fenwick tree
4. Iterate over the a, b points, And count how many prior a points had end points b that were after the current b.  So you just need to query the range [index_map[b], n].  To get all the count after.
5. Then take the current b and add it to the fenwick tree.

 

Problem G

1. Observe you have a weighted undirected graph and it is a connected graph and the problem is asking for a shortest path to get from a source to target.
2. This is enough to know that a dijkstra algorithm will work.
3. The only catch is you need to track (u, s) for the visited states, instead of just the node.  You want to know that this is the best visit of node u when you have current slowness factor of s.
4. This matters because s affects the future costs of traversing edges.
5. So you are minimizing dp(u, s) with dijkstra.

 

Github Repository with the code: https://github.com/algosand/archive-cp/blob/master/codeforces/div4/round_918.md