I'm currently live discussing the problems.
I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or if you have more questions.
VOD: Twitch and YouTube
2065A - Skibidus and Amog'u
IdeaFind the length n of the string, and then print first n-2 chars and then i.
My submission — 305152340
2065B - Skibidus and Ohio
Hint 1Let n be the length of the string.
Answer is either 1 or n
Hint 2If there exists adjacent 2 equal chars, we can reduce the string to length 1.
The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent equal chars.
My submission — 305156370
2065C2 - Skibidus and Fanum Tax (hard version)
Hint 1Greedy.
For each i, try to find a minimum value of ai which we can get and it is still sorted.
Hint 2If K is the minimum possible value of a_{i-1} we can get such that the array is still sorted.
Hint 3If we do not do any operation the value remains ai. This is possible only if K <= ai
If we do an operation then bj — ai >= K, this imples aj+K <= bj.
So chose the minimum bj >= aj+K, and do an operation using it.
My submission — 305170276
2065D - Skibidus and Sigma
Hint 1Score of an array is sum of prefix sum of the array.
For an index idx = i*m+j, S_{idx} = sum of first i-1 arrays + sum of first j elements of ith array.
Try to find both of these values separately.
Hint 2Contribution due to part 2 is sum of score of all arrays.
Hint 3Let C = [sum(a1),sum(a2),sum(a3),...,sum(an)]
Let S = maximum score we can get after rearranging C.
Then contribution due to part 1 is m*S
My submission — 305178675
2065E - Skibidus and Rizz
Hint 1max(x-y,y-x) is equal to abs(x-y)
First try to find trivial -1 cases.
Hint 2Look at the complete string first. The score is abs(n-m).
If this is more than K, then maximum balance among all substring is more than K.
Hint 3If n<k and m<k, then balance can never be equal K.
Hint 4Otherwise the following string works for N=10, M = 11, and K = 3
111 000 111 000 111 000 11 0
My submission — 305190528
2065F - Skibidus and Slay
Hint 1If an array has a majority element, then there must exist a subarray with length 2 or 3 with that element being majority.
Hint 2The problem reduces to checking length 2 and 3 paths.
Hint 3Length 2 paths are just edges.
Hint 4For length 3, you can fix a middle element and check if 2 adjacent elements contain same value.
My submission — 305198612
2065G - Skibidus and Capping
Hint 1There arent many cases when lcm is semi prime.
Hint 2If p and q are different prime nos, then their lcm p*q is semi prime.
Hint 3Otherwise, one of the element must be semi prime, and other one must be its factor.
My submission — 305231777
2065H - Bro Thinks He's Him
Hint 1f(t) can also be written as 1 + no of adjacent different chars.
Hint 2Lets look contribution due to si and sj being adjacent.
If si==sj, they add 0 to score.
If si!=sj, then they add 1 to score.
No of subsequences that contain si and sj adjacent are pow(2,i-1)*pow(2,n-j), basically,
- For char before i, we have 2 choices we can take them or ignore them.
- For char after j, we have 2 choices we can take them or ignore them.
- We must take i and j
- We must not take chars between i and j
Hint 3Now, the hard part, how to do it with changing chars?
Use Segment tree.
Hint 4For each node representing s[i...j], we can maintain -
- Sum of pow(2,i-1) when si = 0
- Sum of pow(2,i-1) when si = 1
- Sum of pow(2,n-j) when sj = 0
- Sum of pow(2,n-j) when sj = 1
- Contribution due to pairs inside this segment
My submission — 305220025
what is wrong with my solution? https://codeforces.net/contest/2065/problem/G
I did count for distinct primes + squares + p*q with dist p,q
You should do (n+1)C2 instead of +n As we can also select the elements like (6,6),(4,4)
Not sure why you are receiving down votes, but thanks for this. Many hazy ideas from the rush of the contest feel more concrete after reading this (along with new things learned ofc.)
I can help anyone who wants to understand problem G solution.