We invite you to participate in CodeChef’s June Long Challenge, this Friday, 4th June, 3 PM IST onwards.
The contest is open for 10 days, i.e, from 4 — 14 June. Please note, this month’s long challenge will be rated only for Div 3 coders.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Joining us on the problem setting panel are:
Setters: Daanish Mahajan, Md Sabbir upobir Rahman, Vivek Mishra, Souradeep Paul, Srikkanth srikkanthr R, Akash Whiplash99 Bhalotia
Statement Verifier: Riley Monogon Borgard
Editorialist: Taranpreet taran_1407 Singh
Head Admin: Alex Um_nik Danilyuk
Contest Admin: Daanish Mahajan
Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla, Shivam Bohra, Radoslav radoslav11 Dimitrov, Aryan Agarwala, Meet myth_gemphir Singh Gambhir
Mandarin Translator: Huang Ying
Russian Translator: Fedor Mediocrity Korobeinikov
Bengali Translator: Sakib SakibAbrar Abrar
Vietnamese Translator: Team VNOI
Prizes:
The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Important Update
Did you create multiple usernames with CodeChef in the past? If yes, here's an update. We now have a portal where you get to see all your usernames so that you can delete all and keep the best one for you.
Hope to see you participating.
Good Luck!
Is so many cheaters in div1?
There were some pretty interesting problems in this contest.
I managed to solve them all except for Maximum Frequent Subarray Sum (MFSS), for which I only achieved a partial score. In the course of attempting to solve this problem I exposed a major weakness of my own: Suffix Arrays and Trees.
I established that the correct way to solve the problem was likely to construct a Suffix Tree using Suffix Links in order to reduce the construction time and memory requirements, and then to perform DFS on this, adding the sum products of sums and frequencies while traversing and taking the max of all of them.
Where I fell down was the implementation. Lots of resources lent themselves to small alphabets. Skiena recommended a number of links to different implementations, without really discussing himself how they worked. Some of the links were broken in any case. The Edu section on Codeforces does not seem to go into the required levels of detail (or I have failed to make the correct extensions). adamant wrote a great article of Ukkonen's algorithm, but I was unable to extend it to this problem and perform the required DFS.
My question to the community (and I'm especially keen to hear from anyone who solved it) is what resources you used to construct your successful implementations of suffix trees without tight restrictions on the alphabet size, and your traversals as well (how the DFS works with edges versus links, for instance). Whether your implementations were constructed specifically for this problem or already existed and simply required some manipulation, I'm still interested to hear and to improve my own understanding of this pretty difficult topic.
Didn't had the time to workout all problems and I can't anyway, but, atleast to me, SUBTRCOV was also pretty nice
Yes that was a good problem. I suspect my solution (using priority queues and sparse tables) was sub-optimal, as I see some people achieved much faster execution times, but it was enough to pass.
Interesting, I did a greedy starting my construction from one of the farthest ends(diameter nodes), where at each move, I sorta take the node which lead to the highest depth(sorta helps me converge to the leaf nodes). Anything similar in short?
The idea sounds similar. My main idea was that the largest number of nodes that could be 'covered' by a 2-subset was the diameter of the tree. Thereafter, until I had achieved k nodes I looked to add one more path at a time to the furthest remaining node from those already used.
In order to establish the furthest nodes, I maintained a priority queue of depths from an initial DFS (starting at one end of the diameter), and then when popping off nodes, I checked first whether their depth hadn't changed by finding (via sparse table) their deepest ancestor already covered (re-adding them to the PQ if necessary).
this comment is the most British thing on Codeforces.
Ha. Well I suppose there could be a fairly simple explanation for that :)
I'd say the problem is very similar to "find the substring which maximizes (number of occurences) * (length)" which is very well-known. Took me about 20 minutes to implement it with suffix automaton + segment tree (#47836604) and I have no idea how the size of the alphabet even matters here.
Well that wasn’t what I said. What I said was that in lots of the online material I had found, the size of the alphabet was assumed to be small.
Your implementation is impressive but the purpose of my comment was to seek understanding, rather than simply code. I am able to locate the successful submissions myself. What I was unable to do in-contest was to relate the structure of your post to the required DFS traversal, which is also what I asked in my comment.
You don't really need DFS in this problem. You need to maintain number of occurences and first occurence position for every node. If we're talking about suffix automaton, first occurences can be calculated within construction (see fpos array in my code for suffix automaton) and occurence counts can be calculated in the following way (assuming suffix tree):
Start with $$$cnt_v=1$$$ for $$$v$$$ corresponding to suffixes of the string. Then sum them up for every node over the tree. It corresponds to the number of ways to extend the string in the node until it hits the end of the string. This can be done by both dfs or by iterating nodes in descending order of their lengths and adding their counters to their parents'.
As for English resources I would recommend Wikipedia article on suffix automaton (it should be ok, I wrote it) and translated E-maxx article (I learned suffix automaton from its Russian original and it has lots of example).
To construct it without restrictions on alphabet size I just use map instead of static array to store transitions. Sorry, I know you asked about suffix trees but I really think that a proper way to deal with string problems is through suffix automaton, as it gives you the suffix tree in its suffix link tree so you may use it as bot suffix automaton and suffix tree of the reversed string.
Thanks a lot — this is really useful. I didn’t find anything about suffix automaton in all of my searching previously.
It can also be done without segment tree. We only need the maximum sum path ending at each state which is just the classic DP of longest path on DAG.
True. I haven't worked with suffix automaton as an actual DAG for a while, huh. Mostly with its suffix link tree.