PikMike's blog

By PikMike, history, 3 weeks 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  

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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

  • »
    »
    3 weeks 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?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes! I got the error. Thank you!

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain the logic used in problem C?

Thanks.

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought this was my comment lol.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks 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 .

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain me solution to problem E?

  • »
    »
    3 weeks 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)

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Every time I see 998244353 , I think of NTT :)

»
3 weeks 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://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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone ecxplain me first question

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

question d: why time limit is exceeded in my solution ?how author solution is better please help link of my solution

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

include

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

»
23 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

gotchaa