### O--O's blog

By O--O, history, 11 days ago,

Hello, Codeforces!

We are happy to invite you to TheForces Round #8 (ICPC-Forces), which will take place on Mar/17/2023 18:10 (Moscow time)

As it's an Indian ICPC week we tried to prepare one good team-based contest which can help you for ICPC preliminary round.

You will have 3 hours to solve 11 problems. The problems are not sorted by difficulty.

The top places will be published after the contest.

Discord Group (500+ people)

Contests' archive

Did you like the contest?

UPD: Rejudged every submission.

UPD: TOP PERFORMERS ---

Rank Name
1 satyam343
2 simiao1986
3 K-423, acfinity, megurine
4 ExpertHunter, mister, Xaxixin
5 cuiaoxiang
6 achvanov
8 kachhuaa, chiki_D, vrintle
9 sevlll777
10 vgtcross

• +109

 » 11 days ago, # |   +15 Wow, 11 problems
 » 11 days ago, # |   +41 Psychotic_D worked very hard for the contest, and came up with some really cool problems. Please participate. I hope you enjoy the round.
•  » » 11 days ago, # ^ |   +34 Thanks for your support. Orz
 » 11 days ago, # |   +11 Auto comment: topic has been updated by O--O (previous revision, new revision, compare).
 » 11 days ago, # |   +24 I only tested Psychotic_D's question, his question has educational significance and short statements. The style is close to Codechef, and there is no heavily implementation.I think it's fun to think about how to optimize complexity as much as possible for each of his problems.
 » 11 days ago, # | ← Rev. 3 →   +54 Few Things I want to add as problem setter,I would like to say thanks to the problem setter and testers. dbtalaviya — For really cool problem ideas and python testing for some of the problems. merlin_ — Tried his very best as a tester and be a JAVA tester. I have no words to appreciate him properly. JUBHAI — testing some of the problems in python and a very first tester. Dhru008 — Discussing some other problems with me and testing. _Prince — Testing problems and for proposing some ideas. EndlessDreams — For special testing. Little_Sheep_Yawn — for testing almost full contest in python. O--O — For the community TheForces and background support. Lastly, I hope you people will enjoy the contest as a team. I would love to hear any type of feedback after the contest. We tried to make it a good practice type contest.UPD: Thanks for making the contest wonderful by taking part in it. I hope you guys enjoyed the problems. You can give me any kind of feedback for future improvements.
 » 11 days ago, # |   +33 I will give this gym today!!!
 » 11 days ago, # |   +9 Why name is changed from SHA-Forces to ICPC-Forces?
•  » » 11 days ago, # ^ |   +29 maybe this looks better
 » 10 days ago, # |   +1 Are the problems sorted to the difficulty?
•  » » 10 days ago, # ^ |   +10 The blog clearly says thatThe problems are not sorted by difficulty
 » 10 days ago, # |   +27 Thanks for good work, can I contribute too ?
 » 10 days ago, # |   +11 Did you like the contest?YES!
 » 10 days ago, # |   0 How to Solve Problem K — Equal subsequence My Idea was to use prefix sum and suffix sum but getting wrong answer on test 2
•  » » 10 days ago, # ^ |   0 Hint:binary search on length
•  » » 10 days ago, # ^ |   +5 Yep I did with that only. Codevoid solve(){ int n; cin >> n; vi pre(n), suf(n), a(n); cin >> a; mii mp; rep(i, 0, n){ ++mp[a[i]]; pre[i] = mp[a[i]]; if (i) amax(pre[i], pre[i - 1]); } mp.clear(); bck(i, n, 0){ ++mp[a[i]]; suf[i] = mp[a[i]]; if (i != n - 1) amax(suf[i], suf[i + 1]); } int ans = pre[n - 1] / 2; rep(i, 0, n - 1) amax(ans, min(pre[i], suf[i + 1])); cout << 2 * ans << endl; } 
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 Please can u help me why my code does not work. https://codeforces.com/gym/433200/submission/197814511
•  » » » » 10 days ago, # ^ |   +5 Not accessible!
•  » » » » » 10 days ago, # ^ |   +5 Now the solution are open I think.
•  » » » » » » 10 days ago, # ^ |   0 I did by prefixmax and suffixmax array
•  » » » » » » » 10 days ago, # ^ |   0 Your code here... int ans = 0; //prefixmax , suffixmax holds frequency till that index. for(int i = 0;i
•  » » » » » » » 10 days ago, # ^ |   0 Can u tell what was your intution
 » 10 days ago, # |   +11 Amazing and a very balanced problemset, loved it. Psychotic_D orz!!
 » 10 days ago, # |   +3 Any hints for B and D ?
•  » » 10 days ago, # ^ |   +5 Hints For BDynamic Programming. (As n <= 1e3)
•  » » » 10 days ago, # ^ |   0 How to modify the DP for C?
•  » » » » 10 days ago, # ^ |   +1 You can notice that type of DP you are able to easily maintain in segment tree. So you can calculate minimal answer for any substring in $O(\log n)$. Now you can solve it with two pointers or binary search
•  » » » » » 10 days ago, # ^ |   0 i did $dp[i][remOp][last_digit]$ to calculate states in B. where i is the current index remOp is remaining operations and last_digit is the previous digit in the string but i just don't know how to maintain the states in a segment tree.can you explain in detail please
•  » » » » » » 10 days ago, # ^ |   +1 Let's change our dp a little bit and make number of changes $remOp$ what we calculate, not a dimension. $dp[l][r][x][y]$ will be minimal number of changes to make substring $s[l \ldots r]$ good with digit $x$ at the front and $y$ in the back. We can merge neighbour segments in $O(1)$ and segment tree only needs $O(n)$ such segments to store
•  » » » » » » » 9 days ago, # ^ |   0 Thanks, i think the only tricky part is to merge neighbors, i will try to solve.
•  » » 10 days ago, # ^ |   +15 Hint for D : DSU
•  » » 10 days ago, # ^ |   +4 You can also use binary search on the length of substring that can be the answer and check for all possible substrings of that length. To check whether a given substring can be a good substring, (Longest non-decreasing subsequence)+k >= length of substring.PS : You can calculate Longest non-decreasing subsequence using segment tree in O(logn) with O(n) preprocessing as there are maximum 4 unique characters.
 » 10 days ago, # |   0 Auto comment: topic has been updated by Psychotic_D (previous revision, new revision, compare).
 » 10 days ago, # |   +3 Great contest as usual !
 » 10 days ago, # |   +10 As a tester and laxy person, I hope I am not late to ask for upvotes.
•  » » 10 days ago, # ^ |   +13 The Laxy person from problem G.
 » 10 days ago, # | ← Rev. 2 →   +4 Problem F6*n = n+2*n+3*n
•  » » 10 days ago, # ^ |   0 The answer is n with size 1 means answer is cout<
 » 10 days ago, # |   0 Auto comment: topic has been updated by Psychotic_D (previous revision, new revision, compare).
 » 10 days ago, # |   0 problems were really amazing !! enjoyed the contest.
»
10 days ago, # |
Rev. 8   0

Can someone put down why this dp solution is TLE for prob B.?

Spoiler

https://codeforces.com/gym/433200/submission/197795319

 » 10 days ago, # |   +1 enjoyable contest
 » 10 days ago, # |   +1 How to solve H??
 » 10 days ago, # |   0 https://codeforces.com/gym/433200/submission/197820770why this is giving Memory limit exceeded using queue whereas other datastructures similar to queue such as priority queue are passing the same test case can someone help?
 » 10 days ago, # |   +6 How to solve J?
•  » » 10 days ago, # ^ |   +1
•  » » 10 days ago, # ^ |   +26 Meet in the middle with pivot on diagonal elements.
 » 10 days ago, # |   0 Can someone explain problem H please, i couldn't get it !
•  » » 10 days ago, # ^ |   0 oh, i get it now
•  » » » 10 days ago, # ^ |   0 I didn't get it. Can you please explain.
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 Think of that problem as solving a math equation. Let's say the number equals "a" which we want to add in order to make our equation satisfy , so (p / q) = (y + a) / (x + a) now solve this equation for a, we get (px — qy) / (q — p). Few edge cases we need to handle like when denominator gets 0 ( that gives us division by zero error) and when this value is negative (we can only add positive values ).
 » 10 days ago, # |   +1 Problem C was cool, just upsolved it. AC with 3572ms
•  » » 10 days ago, # ^ |   0 Can you please explain your code in detail?
•  » » » 10 days ago, # ^ |   0 If you know segment tree then it's a just a variant. First like problem B (easy version), assign some numbers to each character (i.e. '7' to 0, '4' to 1, '8' to 2 and '5' to 3).You need to create a node of segtree which will have the information about the cost of change of all combinations of endpoints possible of a good string (start number <= end number).Just merge each two node by their possible intermediates.Do a BS to find the max possible length starting from i which has cost less or equal to k for each starting i.Take max over all possible i and output it.
•  » » » » 10 days ago, # ^ |   0 Can You please share your DSU based approach of Problem D?
•  » » » » » 10 days ago, # ^ |   +5 Sure! so we need to connect the adjacent one by one in increasing order of numbers and by DSU we can easily find no of connected components (initially n * m). As two components concatenates one count decreases so we can simply check if we have connected all the cells which has number less ore equal to x has exactly n * m — x + 1 components or not.
•  » » » » 10 days ago, # ^ |   0 Ohh makes lot of sense now. Thank you! good problem for learning
 » 10 days ago, # |   +20 Problem I — 104120F - Fence Painting