### PikMike's blog

By PikMike, history, 6 months 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

•
• +92
•

 » 6 months ago, # |   0 for problem E, did you mean to write dig=1...9 (or 0...9)?we cannot place a digit 10
•  » » 6 months ago, # ^ |   0 I'm sorry, this is a mistake. Hope it fixed now!
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 "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?
 » 6 months ago, # |   +3 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.
•  » » 6 months ago, # ^ |   +3 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.
•  » » 6 months ago, # ^ |   +3 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.
•  » » 6 months ago, # ^ |   +3 Yes! I got the error. Thank you!
 » 6 months ago, # |   +6 Can someone please explain the logic used in problem C? Thanks.
•  » » 6 months ago, # ^ | ← Rev. 10 →   +2 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
•  » » » 6 months ago, # ^ |   0 Thanks a lot. Understood why we used binary search in this problem. :)
•  » » » » 6 months ago, # ^ |   0 Happy to help ^^
•  » » » 4 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   0 I thought this was my comment lol.
 » 6 months ago, # |   0 PikMike 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?
•  » » 6 months ago, # ^ |   0 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 .
 » 6 months ago, # |   +4 Can someone explain me solution to problem E?
•  » » 6 months ago, # ^ |   0 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)
 » 6 months ago, # |   0 I saw a solution with segment tree for problem D. Anyone to explain the method?
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +69
•  » » 6 months ago, # ^ |   0 Every time I see 998244353 , I think of NTT :)
 » 6 months ago, # | ← Rev. 2 →   -22 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
 » 6 months ago, # | ← Rev. 2 →   0 Please put this into Contest materials of the Round . Thanks.
 » 6 months ago, # |   0 can anyone ecxplain me first question
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
 » 6 months ago, # | ← Rev. 2 →   0 question d: why time limit is exceeded in my solution ?how author solution is better please help link of my solution
 » 6 months ago, # |   0 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?
»
5 months ago, # |
0

//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; } }

 » 5 months ago, # | ← Rev. 2 →   0 gotchaa