awoo's blog

Educational Codeforces Round 53 Editorial
By awoo, history, 6 years ago, translation, In English

1073A - Diverse Substring

Tutorial
Solution (PikMike)

1073B - Vasya and Books

Tutorial
Solution (Ajosteen)

1073C - Vasya and Robot

Tutorial
Solution (Ajosteen)

1073D - Berland Fair

Tutorial
Solution (PikMike)

1073E - Segment Sum

Tutorial
Solution (Vovuh)

1073F - Choosing Two Paths

Tutorial
Solution (Vovuh)

1073G - Yet Another LCP Problem

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +92
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem E, did you mean to write dig=1...9 (or 0...9)?

we cannot place a digit 10

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

    I'm sorry, this is a mistake. Hope it fixed now!

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

The solution of problem F is: use greedy thoughts to find the longest path in the tree. So, we will look for the first point of the common part as root, then dfs () from that root to find the other end

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    "we will look for the first point of the common part as root", how to look for the first point of the common part as root? Which is the first point of the common part as root, is the center of the origin tree?

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

Why do we have to keep iterating until T becomes smaller than the minimum priced sweet in Problem D. What I am thinking is when we do T=T mod C , we will be having money only for a single round of circle. Please correct me If I am wrong. Thank you.

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

    Your assumption in second line i.e. " When we do T=Tmodc.... ...single round of circle. " is wrong.

    give it another thought. it's easy you will get it.

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

    Your thinking is wrong. The following testcase can hack you:

    6 999999998
1 999999999 1 999999999 1 999999999

    After T%C, The number of round of circle is multiple, instead of single.

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

      Won't C = 3 after the first circle and 999999998 % 3 = 2 which can be covered in another round of the circle?

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

    Yes! I got the error. Thank you!

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

Can someone please explain the logic used in problem C?

Thanks.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 10   Vote: I like it +2 Vote: I do not like it

    In C we apply binary search on the length of string to find whether it is possible or not to reach the desired position from the position reached by applying all the operations measured in non effective range and changing the operations in substring of given length(lets say len) and we would do that for all substrings of length len.

    Eg: You have a string RRRUUL and you want to check if you could reach position (-4,2). So we apply binary search and lets say mid = 3. Then you would check for indices 0 to 2 to see if by changing the instructions in this range can I reach my desired position. Now you have to apply the rest of operations(which are not affected in the range selected, here positions 3 to 5 in the string) anyhow, so to check the validity we make our initial position to be the one that is obtained by applying the operations in non effective range(here UUL position 3 to 5 in original string). So now your initial position is (-1,2). Now from this position you check whether I can reach to (-4,2) by changing the at most 3 instructions in given range(position 0 to 2 in string). In this case you can(change RRR to LLL) and so call to ok(3) would return true. Like this the binary sear occurs and at the end you would have the minimum value of length.

    I hope this helps

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

awoo In C problem why is value of l initialized with -1 and not 0 which is the minimum value if answer is possible(and it is, as we already checked it by ok(n)). Also how to determine the loop condition to be r - l > 1 and not the standard r > l?

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

    There are two ways to write a binary search: on segment [l, r] or on interval [l, r) or (l, r]. This is the (l, r] case, so we should be sure that ok(l) = false and ok(r) = true. In case of invervals, (l, r] is a degenerate case .

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

Can someone explain me solution to problem E?

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

    Not sure what the editorial does exactly, but one way to solve it with DP is two store two values.

    DP1[pos][less?][mask] stores the amount of ways to make number from position pos, whether previous number makes subsequence numbers less than already, and mask to store which digits have been used from 0-9 DP2[pos][less?][mask] stores the sum of the numbers, same parameters of DP1

    We can calculate DP1 somewhat straightforwardly, and for DP2 we use values of DP1 to calculate (for adding the number '5' onto for example, we might add 5 * DP1[pos][less?][mask] to out DP2 value)

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

I saw a solution with segment tree for problem D. Anyone to explain the method?

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

    I have solved it using two segment trees so it may be similar solution. Both were for suming on interval and changing in 1 point. The first one was for suming cost of candies, the latter for suming candies. We are skipping whole circles as long as we can so ater that we will have some T < C. Then we can binary search how far can we go by checking sum of cost candies using segment tree. The we can add to result sum from the second tree on the same interval, change cost of candie to 0 and change value of candie to 0 (because we will never buy it again). Then we move our starting point just after the last fair we have binary searched for, remove fairs on which we will never buy candies, and repeat whole process again. In each loop we are decreaing number of fairs by at least 1 and cost of every loop is O(log^2 N) for segment tree and binary search so total complexity should be O(Nlog^2 N). In my solution it was handy to be only on fairs on which we can still buy candies so i kept set of indices of those.

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Alright, I've just found a stunningly beautiful solution to E. No more ugly, confusing DP. Say hello to this beast:

https://mirror.codeforces.com/contest/1073/submission/45154557

It's so simple, it's perfect. All you do is loop over the bitmasks of sets of digits. Then, for each one, binary search on the largest string that's not greater than our boundaries. Then just subtract the total sum of all possible numbers generated by our digit set up to the right boundary from the total sum from the left boundary to find its contribution to the answer!

Of course, you have some handling with things like overcounting, leading zeroes, and such, but it turns out with this algorithm those are all gone with a wave of the hand.

BOOM! Now this is the kind of thing competitive programming is about.

UPD: I've been smiling so hard my face hurts

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

Please put this into Contest materials of the Round . Thanks.

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

What's the meaning of $$$dp[i][mask][0].x$$$ and $$$dp[i][mask][0].y$$$ in problem E?

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

I think it is easier to use two pointers instead of binary search in C. Also, it will give O(n) instead of O(n*log(n)) solution.

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

I solved G with divide and conquer in $$$O(n \log n + (\sum k_i + \sum l_i)\log n)$$$: 119421806.

The idea is to sort the points $$$a_i$$$ and $$$b_i$$$ by their position in the suffix array. We do divide and conquer on this sorted list. Without loss of generality, say we want the answer for all $$$a_i\le b_i$$$. To find the answer for all pairs with $$$a_i$$$ in the first half and $$$b_i$$$ in the second half, we can maintain two pointers going from the middle outwards. We always advance the pointer that gives the higher range minimum.

→ Reply