Hello, Codeforces!
We are happy to invite you to TheForces Round #8 (ICPC-Forces), which will take place on [contest_time:433200]
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, Khonshu08, 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 | AhmetKaan, qwexd, early-morning-dreams |
| 5 | cuiaoxiang |
| 6 | achvanov |
| 7 | Adam_GS, Everule, Dominater069 |
| 8 | kachhuaa, chiki_D, vrintle |
| 9 | sevlll777 |
| 10 | vgtcross |
Wow, 11 problems
Psychotic_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. Orz
Auto 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.
Khonshu08 — 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.
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 difficulty
Thanks 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
binary search on length
Yep I did with that only.
Please can u help me why my code does not work. https://mirror.codeforces.com/gym/433200/submission/197814511
Not accessible!
Now the solution are open I think.
Amazing and a very balanced problemset, loved it. Psychotic_D orz!!
Any hints for B and D ?
Dynamic 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
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.
6*n = n+2*n+3*n
Auto comment: topic has been updated by Psychotic_D (previous revision, new revision, compare).
problems were really amazing !! enjoyed the contest.
enjoyable contest
How to solve H??
https://mirror.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://mirror.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.
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.
Problem I — 104120F - Fence Painting