CCC '20 S3 - Searching for Strings - DMOJ: Modern Online Judge

CCC '20 S3 - Searching for Strings

Points: 12 (partial)

Time limit: 0.5s

Memory limit: 512M

Author:

Problem types

Canadian Computing Competition: 2020 Stage 1, Senior #3

You're given a string $N$ ~N~, called the needle, and a string $H$ ~H~, called the haystack, both of which contain only lowercase letters a…z.

Write a program to count the number of distinct permutations of $N$ ~N~ which appear as a substring of $H$ ~H~ at least once. Note that $N$ ~N~ can have anywhere between $1$ ~1~ and $|N|!$ ~|N|!~ distinct permutations in total – for example, the string aab has $3$ ~3~ distinct permutations (aab, aba, and baa).

Input Specification

The first line contains $N$ ~N~ $(1 \le |N| \le 200\,000)$ ~(1 \le |N| \le 200\,000)~, the needle string.

The second line contains $H$ ~H~ $(1 \le |H| \le 200\,000)$ ~(1 \le |H| \le 200\,000)~, the haystack string.

For $3$ ~3~ of the $15$ ~15~ available marks, $|N| \le 8$ ~|N| \le 8~ and $|H| \le 200$ ~|H| \le 200~.

For an additional $2$ ~2~ of the $15$ ~15~ available marks, $|N| \le 200$ ~|N| \le 200~ and $|H| \le 200$ ~|H| \le 200~.

For an additional $2$ ~2~ of the $15$ ~15~ available marks, $|N| \le 2\,000$ ~|N| \le 2\,000~ and $|H| \le 2\,000$ ~|H| \le 2\,000~.

Because the original test data were weak, an additional subtask worth $5$ ~5~ marks has been added.

Output Specification

Output consists of one integer, the number of distinct permutations of $N$ ~N~ which appear as a substring of $H$ ~H~.

Sample Input

aab
abacabaa

Output for Sample Input

Explanation of Output for Sample Input

The permutations aba and baa each appear as substrings of $H$ ~H~ (the former appears twice), while the permutation aab does not appear.

Comments

7

leoliu93233 commented on July 4, 2024, 12:10 a.m.

this question is harder than finding a needle in a haystack

2

RAMJET_7 commented on Feb. 13, 2022, 12:16 a.m. ← edited →

Is it guaranteed that $|N|\leq|H|$ ~|N|\leq|H|~? I assume so because $N$ ~N~ is a substring of $H$ ~H~. Still I think a restriction that states this would be beneficial.

6

uselessleaf commented on Feb. 13, 2022, 1:22 a.m.

It is NOT guaranteed that $|N|\leq|H|$ ~|N|\leq|H|~.

6

31501357 commented on Jan. 25, 2021, 4:28 a.m.

I officially hate this problem, despite being able to solve it on the CCC.

-13

31501357 commented on March 20, 2020, 3:11 a.m.

This question was super weird and involved a very strange technique to solve.

This comment is hidden due to too much negative feedback. Show it anyway.

91

DiscoverMeme commented on March 23, 2020, 9:17 p.m. ← edited →

CCC has become terrible in recent years, thanks to Dr. Troy Vasiga and his team. Lots of server issues and crashes on the main CCC site since at least 2016. Some of them were blamed on the public. This doesn't happen in other programming contests but they got away with it because they didn't provide proper data to back their claims. It is easier to blame your server crashes on the users, your team, or the wind blowing than learn a bit about load balancing to prevent overloading your servers.

This must have emboldened them to make the 2019 and 2020 Senior contests a disaster. Take for example Problem S3 in 2020 - Searching for Strings. It has efficient solutions that involve string algorithms. However, these algorithms are not in the Canadian high school curricula, let alone computer studies.

In fact, string algorithms are SPECIFICALLY EXCLUDED from the IOI syllabus and have been so for many years. See here, on page 13: https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf

String algorithms and data structures: there is evidence that the inter-reducibility between KMP, Rabin-Karp hash-ing, suffix arrays/tree, suffix automaton, and Aho-Corasick makes them diffcult to separate.

Maybe there are other ways to solve it but they'd be extremely contorted. String algorithms provide a decisive advantage. Unsuspecting kids who attempt to circumvent or reinvent string algorithms will burn out their entire contest time and more. As page 4 of the IOI syllabus makes clear:

The tasks will be set with the goal that knowledge of Excluded topics should not help in obtaining simpler solutions / solutions worth more points.

The other problems in 2020 CCC Senior are equally out of whack. Either a strikingly similiar problem to one from 2019 Reprechage, bad data full of whitespace that leaves you wondering why your program crashes, waiting minutes for S3 solutions to judge, or endless constant optimization in S2. No fun graphs or trees which make up the majority of the IOI syllabus.

Since the organizers clearly didn't design this contest for a good IOI selection, nor to encourage the participants, they look like a bunch of one-trick-ponies who have ruined the contest on purpose. They get to look like geniuses to the corporate sponsors. You know, they get to show they are much smarter than the kids who couldn't invent on the spot all the string algorithms that some of the organizers learned in university.

Considering that CCC participants will soon compete with the CCC organizers for jobs and grants, botching the contest in 2016-2020 was a clever strategy for the organizers. They also got to make their favorites win by knocking down everyone else with unfair subject matter and server issues. Or maybe not?

We'll see if the team is willing to fix the 2020 CCC botch. They need to get someone more responsible to redo the contest and properly select the IOI team. This contest used to run smoothly before Troy Vasiga took over and wasted it year after year after year. CCC is a tremendous asset for Canadian education, it is important for thousands and thousands of students each year, and it deserves honest and competent leadership.

https://dmoj.ca/post/158-ccc-19-problems-posted#comment-9190

61
2fecta commented on March 24, 2020, 1:54 a.m. ← edit 11 →
https://dmoj.ca/problem/ccc20s5#comment-11869

The CCC this year was far too computer science-y. Olympiad students like xiaowuc2 and wieung_bvg really need to stop setting problems. It's all just people who learned the same data structures and algorithms and put it on the CCC.

The failed CCC of 2020 is a clear demonstration of how during the months prior, as students across Canada were working hard in preparation for the competition, the contest organizers definitely were not. Despite the fast grader, which allowed sub-optimal solutions to achieve optimal scores, the website crashed several times and participants were often forced to wait in long queues in order to receive feedback for their submission. Supporters of this queue may attempt to justify the wait as an inevitable consequence of the scale of the competition; however, to this I point out the more popular USA Computing Olympiad. Not only does the USACO frequently serve over 6000 users, but it is also hosted over a 4 day period, allowing participants to view and discuss the problems and improve soon after they compete. Even after the frustratingly long CCC window of over 30 days was over, CCC organizers were slow to publicize the problems. Unlike the February 2020 USACO, which was hosted at a later date, CCC 2020 results are still unavailable to this day, and I could not locate an editorial or test data anywhere on the official website. I also couldn't locate a single word of gratitude towards Mike "MikeMirzayanov" Mirzayanov for his great Polygon and Codeforces systems.

Incompetence is also shown in the CCC problems, whether it be in the unsorted input of S1, unclear constraints of S2, mundane debugging of S3, or mathematical thinking (!) of problems S4 and S5. It is easy to see the bias in these problem topics due to the problemsetters' shared knowledge perspective from their classes at Olympiads.

After moving to Canada, an IOI gold medalist graduated early without participating in this excuse of a contest. But you don't need to be 300iq to know that the CCC isn't the "fun challenge for secondary school students" it claims to be. As a result, the Canadian Computer Community has devolved into a more or less homogeneous population of CS nerds who don't have a gf, leading to a decline in birth rates significantly impacting economic growth. Moreover, this group typically places their individual needs of "[getting] into cco because iT lOoKs GoOd oN [mY] rEsUmE" over the glorious needs of the party. If CCC organizer "Troy Vasiga" has any respect for the advancement of the human race, he will rename the CCC to the Союз Советских Социалистов and purge all the setters who keep putting algorithms in their problems.

Edit: On a more serious note, it does seem like insufficient preparation has gone into the recent years of CCC. The test data has been, on many occasions, too weak or simply wrong. The constraints should be set so that solutions with incorrect complexities do not pass, while solutions with correct complexities do not require too much constant optimization. The grader and website could be better made to not crash and show the verdict to a submission in a timely manner. For these reasons the score and ranking of many participants deviate from their usual performance on other contests such as DMOJ contests or USACO and are often a poor representation of their programming ability. This is a concern considering CCC scores are used to select the Canadian IOI team. It is also unfair towards students who have spent a lot of time practicing competitive programming and wish to apply to the University of Waterloo.

Some competitions with (usually, in my opinion) relatively good problems:

DMOPC and similar DMOJ contests

USACO/COCI/APIO/most other OIs

1

planT_444 commented on Feb. 15, 2022, 9:41 p.m.

Do you think ccc '21 was an improvement or no just curious

1

Mad_Milk commented on Jan. 7, 2021, 3:20 a.m. ← edited →

(￣ω￣)

-33

John commented on Oct. 29, 2020, 2:19 p.m.

Can I just point out that this is a lot coming from someone who's only solved two problems?

This comment is hidden due to too much negative feedback. Show it anyway.

47

300iq commented on May 21, 2020, 8:53 p.m.

Hello, hello.

Well, I've not moved to Canada. I don't even have my study permit yet...

24

magicalsoup commented on March 20, 2020, 3:58 p.m.

Not really.

-12

Plasmatic commented on March 20, 2020, 8:58 p.m.

In fact, the same technique showed up on yesterday's codeforces round

This comment is hidden due to too much negative feedback. Show it anyway.

-12

31501357 commented on March 21, 2020, 2:48 a.m.

I don't know it seems to me that the rolling hash algorithm isn't really used in the CCC.

This comment is hidden due to too much negative feedback. Show it anyway.

29

aeternalis1 commented on March 21, 2020, 2:53 a.m.

It would be pretty ridiculous if they just tested the same things year after year. Each algorithm already seen had its "first time" in the CCC at some point, and it just so happens this was the year for rolling hash.

-3

31501357 commented on March 21, 2020, 2:59 p.m.

Good point, guess we have to prepare for new stuff in the future.

-23

Dan13llljws commented on March 21, 2020, 12:44 a.m.

D was rlly ez

This comment is hidden due to too much negative feedback. Show it anyway.

3

Plasmatic commented on March 21, 2020, 3:57 a.m.

Hashing has its difficulties :)