### awoo's blog

By awoo, history, 3 years ago, translation, 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  Comments (38)
 » for problem E, did you mean to write dig=1...9 (or 0...9)?we cannot place a digit 10
•  » » I'm sorry, this is a mistake. Hope it fixed now!
 » 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
•  » » 3 years ago, # ^ | ← Rev. 2 →   "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?
 » 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.
•  » » 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.
•  » » 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.
•  » » » Won't C = 3 after the first circle and 999999998 % 3 = 2 which can be covered in another round of the circle?
•  » » Yes! I got the error. Thank you!
 » Can someone please explain the logic used in problem C? Thanks.
•  » » 3 years ago, # ^ | ← Rev. 10 →   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
•  » » » Thanks a lot. Understood why we used binary search in this problem. :)
•  » » » » Happy to help ^^
•  » » » In the condition of (do<=len) , should not also there be condition that (len-do)%2==0 ? Since odd difference would go wrong in some testcases as well.
•  » » » what's that 2 pointer method?
•  » » I thought this was my comment lol.
 » 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?
•  » » 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 .
 » Can someone explain me solution to problem E?
•  » » 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 DP1We 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)
 » I saw a solution with segment tree for problem D. Anyone to explain the method?
•  » » 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.
 » •  » » Every time I see 998244353 , I think of NTT :)
 » 3 years ago, # | ← Rev. 2 →   Alright, I've just found a stunningly beautiful solution to E. No more ugly, confusing DP. Say hello to this beast:https://codeforces.com/contest/1073/submission/45154557It'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
 » 3 years ago, # | ← Rev. 2 →   Please put this into Contest materials of the Round . Thanks.
 » can anyone ecxplain me first question
•  » » 3 years ago, # ^ | ← Rev. 2 →   For any string "abcdef..." you can get n-1 substrings with len=2: "ab", "bc", ... If string contains at least 2 different symbols (a and b, e.g.), it contains substring "ab" or "ba", both of them are "YES" answers. So, only strings that are built from one symbol are "NO" strings.
 » 3 years ago, # | ← Rev. 2 →   question d: why time limit is exceeded in my solution ?how author solution is better please help link of my solution
 » Hi, I am solving problem C, I am stuck trying to understand why ** If there is at least one position of the beginning of the segment for which d0≤len, then we can change the segment ** anyone could explain me why, please?
»

//Why my solution is getting TLE #FOR vasya and books

# include

using namespace std; long long a[(int)2e5 +9]; int main() { long long n; cin >> n; for (int i = 0; i <n; ++i) { int x; cin >> x; a[x] = i+1; } long long mx = 0; for (int i = 0;i< n; ++i) { int y; cin >> y; if (a[y] > mx) { cout << a[y] — mx << endl; mx = a[y]; } else cout << 0 << endl; } }

 » 3 years ago, # | ← Rev. 2 →   gotchaa
 » What's the meaning of $dp[i][mask].x$ and $dp[i][mask].y$ in problem E?
 » 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.
•  » » how to do it using that ?
•  » » » Here is my solution using two pointers .https://codeforces.com/contest/1073/submission/112896136
 » awoo, How everyone knew that in problem B they should use scanf, printf?
 » 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.