pranet's blog

Thought process while solving problems in contest
By pranet, history, 6 years ago, In English

Hi,

Can people who quickly solved todays Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) please share their thought process? It would be great to know how you reduced those problems to standard stuff so quickly. (Particularly for Div-1 B and Div-1 C, but other questions are welcome too).

Thanks

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

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

For problem C, it was something like:

1) How do I know for sure that no point belongs to all segments?
2) Seems like the only way I could know is if I see that a segment started after the end of another segment.
3) How do I know for sure that a segment has ended and another has started after that?
4) Seems like the only way I could know is if F(i) > F(i + 1) and F(i + 1) < F(i + 2), where F(k) is the number of segments point k belongs to. took a few moments to make sure this is the only way, turned out to be trivial to see and prove
5) This means that I should take as many points as possible so that for no three consecutive taken points i, j and k, the inequalities F(i) > F(j) and F(j) < F(k) hold.
6) How does such sequence of points look like? Well, it should be non-decreasing at first and after it reaches some peak point, it starts being non-increasing till the end.
7) Let's fix that peak point and find LIS and LDS.

→ Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I couldn't do the contest but when i looked at C(And got logic pretty fast) , this was my thought process mostly:
1. Need to trick player into thinking that the (xi, cnti) sequence given looks like one where there is a point contained in every set.
2.Thats only possible if such that , hence the sequence (xi, cnti) , if sorted according to xi is first nondecreasing and then nonincreasing (The cnti sequence).
3.Just use dp to find this sequence.

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it
  1. We only care about the array cnt, so let's build it.
  2. How do we check if an element exists in all points, using the array cnt?
  3. It makes sense that we should simply use the biggest interval possible until .
  4. Obviously, at any point during step 3, the positive integers in cnti should form a contiguous subarray. If this does not hold, there is no point that belongs to all intervals.
  5. That means that if we remove the minimum value from cnt (excluding zeroes) from all elements (excluding zeroes again) every time (which is equivalent to creating minValue intervals, that are as long as possible), there should only be zeroes at the beginning or the end of the array.
  6. That means that if cnt is seen as a discrete function, it should be concave, which means we should have a non-decreasing part at the beginning, a maximum, and then a non-increasing part.
  7. Let's assume that element i is the maximum. How many elements do we need to change to make the prefix [0, i] non-decreasing? This is equal to i minus the length of the LIS from 0 to i.
  8. Also, how many elements do we need to change to make the suffix [i, n - 1] non-increasing? This is equal to n - i + 1 minus the length of the LIS of the suffix when reversed.
  9. Let's precalculate these values. Then, the answer is simply m minus the minimum possible sum of the length of the two LISs minus 1.
→ Reply
»
6 years ago, # |
  Vote: I like it +35 Vote: I do not like it

My thought process on A:

  1. Can't we just simulate this with a DFS?
  2. At each node I need to know at which time the apples arrive. Most convinient would be a set with the times.
  3. How to make merging and returning of sets efficient?
  4. DSU on trees!
  5. [15 minutes implementing the solution]
  6. Yay, pretests passed.
  7. Hmmm, this was way too complicated for an A.
  8. [realizing one of the much easier solutions]
  9. Oh no, why did I waste so much time on this?
→ Reply
»
6 years ago, # |
  Vote: I like it -26 Vote: I do not like it

For problem C, it was something like:

1) Need to trick player into thinking that the (xi, cnti) sequence given looks like one where there is a point contained in every set. 2) Please don't downvote me 3) Seems like the only way I could know is if F(i) > F(i + 1) and F(i + 1) < F(i + 2), where F(k) is the number of segments point k belongs to. took a few moments to make sure this is the only way, turned out to be trivial to see and prove

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the truth is it's just english skill + luck. English because half the thinking time is spent understanding the problem, and luck because of the other half. (Also luck because it took me 30 minutes to solve A)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Russian skill also helps. Especially when problems are translated word-for-word, and the phrasing becomes awkward. (Also, inflorescences? Whaaaaaaat)

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thought process on Div 1-B, since no one's written it yet.

  1. Okay, we need to uniquely identify some rotation of the given string. We're given the first character, then have to pick an index and get the second character. (This is the hardest part — parsing the problem).
  2. Can we brute force it? Let's try every starting character and sum up the best choice then
  3. The score of a choice is the probability the character at that position is unique
  4. Keep track of the distribution of characters for each starting character and each distance. This takes O(n2) to prepopulate.
  5. Take the max score for each character and sum them up. This takes O(262n).
  6. AC
→ Reply