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.

Problems were prepared by Psychotic_D and dbtalaviya.

Would like to thank our testers: merlin_, Little_Sheep_Yawn, Dhru008, JUBHAI, _Prince, EndlessDreams

Also we want to thank

**you**for participating in our round. You also can participate as a team.

**The top places will be published after the contest.**

**Discord Group (500+ people)**

**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 |

7 | Adam_GS, Everule, Dominater069 |

8 | kachhuaa, chiki_D, vrintle |

9 | sevlll777 |

10 | vgtcross |

Wow, 11 problemsPsychotic_D worked very hard for the contest, and came up with some really cool problems.

Please participate. I hope you enjoy the round.

Thanks for your support.

OrzAuto comment: topic has been updated by O--O (previous revision, new revision, compare).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.

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

TheForcesand 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.I will give this gym today!!!

Why name is changed from SHA-Forces to ICPC-Forces?

maybe this looks better

Are the problems sorted to the difficulty?

The blog clearly says that

The problems are not sorted by difficultyThanks for good work, can I contribute too ?

`Did you like the contest?`

YES!

How to Solve Problem K — Equal subsequence My Idea was to use prefix sum and suffix sum but getting wrong answer on test 2

Hint:binary search on length

Yep I did with that only.

CodePlease can u help me why my code does not work. https://codeforces.com/gym/433200/submission/197814511

Not accessible!

Now the solution are open I think.

I did by prefixmax and suffixmax array

Can u tell what was your intution

Amazing and a very balanced problemset, loved it. Psychotic_D orz!!

Any hints for B and D ?

Hints For BDynamic Programming. (As n <= 1e3)

How to modify the DP for C?

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

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

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

Thanks, i think the only tricky part is to merge neighbors, i will try to solve.

Hint for D : DSU

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.

Auto comment: topic has been updated by Psychotic_D (previous revision, new revision, compare).Great contest

as usual!As a tester and laxy person, I hope I am not late to ask for upvotes.

The Laxy person from problem G.

Problem F6*n = n+2*n+3*n

The answer is n with size 1 means answer is cout<<n<<" "<<1<<endl; cout<<n<<endl; https://codeforces.com/gym/433200/submission/197864783

Auto comment: topic has been updated by Psychotic_D (previous revision, new revision, compare).problems were really amazing !! enjoyed the contest.

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

Spoiler## include <bits/stdc++.h>

using namespace std;

map<pair<string,int>, int> dp;

int helper(string &s) {

}

int solve(string &s, int index, int k, int n, string &king) {

}

int32_t main() {

int ttt; ttt=1; //cin>>ttt;

while(ttt--){ int n,k; cin>>n>>k;

} return 0; }

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

enjoyable contest

How to solve H??

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

why 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?

How to solve J?

https://codeforces.com/problemset/problem/1006/F

Meet in the middle with pivot on diagonal elements.

Can someone explain problem H please, i couldn't get it !

oh, i get it now

I didn't get it. Can you please explain.

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 ).

Problem C was cool, just upsolved it. AC with 3572ms

Can you please explain your code in detail?

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.

Can You please share your DSU based approach of Problem D?

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.

Ohh makes lot of sense now. Thank you! good problem for learning

Problem I — 104120F - Fence Painting