CCC '22 S3 - Good Samples - Olympiads Online Judge

CCC '22 S3 - Good Samples

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 1G

Author:

Problem types

Canadian Computing Competition: 2022 Stage 1, Senior #3

You are composing music for the Cool Clarinet Competition (CCC). You have been instructed to make a piece of music with exactly $N$ ~N~ notes. A note is represented as a positive integer, indicating the pitch of the note.

We call a non-empty sequence of consecutive notes in the piece a sample. For instance, $(3, 4, 2)$ ~(3, 4, 2)~, $(1, 2, 3, 4, 2)$ ~(1, 2, 3, 4, 2)~, and $(4)$ ~(4)~ are samples of $1, 2, 3, 4, 2$ ~1, 2, 3, 4, 2~. Note that $(1, 3)$ ~(1, 3)~ is not a sample of $1, 2, 3, 4, 2$ ~1, 2, 3, 4, 2~. We call two samples different if they start or end at a different position in the piece.

We call a sample good if no two notes in the sample have the same pitch.

The clarinet players are picky in two ways. First, they will not play any note with pitch higher than $M$ ~M~. Second, they want a piece with exactly $K$ ~K~ good samples.

Can you construct a piece to satisfy the clarinet players?

Input Specification

The first and only line of input will contain $3$ ~3~ space-separated integers, $N$ ~N~, $M$ ~M~, and $K$ ~K~.

The following table shows how the available 15 marks are distributed.

Marks Awarded	Bounds on $N$ ~N~	Bounds on $M$ ~M~	Bounds on $K$ ~K~
$3$ ~3~ marks	$1 \le N \le 16$ ~1 \le N \le 16~	$M = 2$ ~M = 2~	$1 \le K \le 1\,000$ ~1 \le K \le 1\,000~
$3$ ~3~ marks	$1 \le N \le 10^6$ ~1 \le N \le 10^6~	$M = 2$ ~M = 2~	$1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~
$4$ ~4~ marks	$1 \le N \le 10^6$ ~1 \le N \le 10^6~	$M = N$ ~M = N~	$1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~
$5$ ~5~ marks	$1 \le N \le 10^6$ ~1 \le N \le 10^6~	$1 \le M \le N$ ~1 \le M \le N~	$1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~

Output Specification

If there is a piece of music that satisfies the given constraints, output $N$ ~N~ integers between $1$ ~1~ and $M$ ~M~, representing the pitches of the notes of the piece of music. If there is more than one such piece of music, any such piece of music may be outputted.

Otherwise, output $-1$ ~-1~.

Sample Input 1

3 2 5

Sample Output 1

1 2 1

Explanation of Output for Sample Input 1

Notice that the piece is composed of $N = 3$ ~N = 3~ notes, each of which is one of $M = 2$ ~M = 2~ possible pitches, $1$ ~1~ and $2$ ~2~. That piece of music has a total of $6$ ~6~ samples, but only $K = 5$ ~K = 5~ good samples: $(1)$ ~(1)~, $(1, 2)$ ~(1, 2)~, $(2)$ ~(2)~, $(2, 1)$ ~(2, 1)~, $(1)$ ~(1)~. Notice that the two good samples of $(1)$ ~(1)~ are different since they start at two different positions.

Note that the piece $2 1 2$ ~2 1 2~ is the only other valid output for this input.

One example of an output that would be incorrect is $3 2 3$ ~3 2 3~, since it has notes with pitches larger than $2$ ~2~. Another incorrect output would be $1 1 2$ ~1 1 2~, since it only has four good samples: $(1)$ ~(1)~, $(1)$ ~(1)~, $(2)$ ~(2)~, and $(1, 2)$ ~(1, 2)~.

Sample Input 2

5 5 14

Sample Output 2

1 5 3 2 1

Explanation of Output for Sample Input 2

The 14 good samples are: $(1)$ ~(1)~, $(1, 5)$ ~(1, 5)~, $(1, 5, 3)$ ~(1, 5, 3)~, $(1, 5, 3, 2)$ ~(1, 5, 3, 2)~, $(5)$ ~(5)~, $(5, 3)$ ~(5, 3)~, $(5, 3, 2)$ ~(5, 3, 2)~, $(5, 3, 2, 1)$ ~(5, 3, 2, 1)~, $(3)$ ~(3)~, $(3, 2)$ ~(3, 2)~, $(3, 2, 1)$ ~(3, 2, 1)~, $(2)$ ~(2)~, $(2, 1)$ ~(2, 1)~, $(1)$ ~(1)~.

Sample Input 3

5 5 50

Sample Output 3

-1

Explanation of Output for Sample Input 3

There are no pieces with $5$ ~5~ notes that can produce $50$ ~50~ different good samples.

Comments

0

PHo3NIX commented on Oct. 20, 2024, 7:06 p.m.

gg

0

dogecanswim commented on May 9, 2024, 11:12 p.m.

gg go next

4

Jinx commented on Feb. 24, 2023, 4:05 a.m.

lowkey fun question just not when u have 3 hours to do it

20

1jiangand2 commented on Jan. 10, 2023, 2:43 a.m.

I really don't like this problem.

5

iamaperson133769420 commented on March 13, 2022, 8:07 p.m.

does 0 count as a "positive integer"

5

ASDAN118A commented on March 27, 2022, 3:22 p.m.

No

-50

Riolku commented on March 13, 2022, 8:23 p.m.

What do you think?

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

26

andrewtam commented on March 14, 2022, 12:20 a.m.

yes

6

Maillew commented on March 14, 2022, 12:56 a.m.

Thanks for clearing that up, I was confused on that part too. 🙏🙏🙏

60

Victor_Chan commented on Feb. 26, 2022, 2:53 a.m.

-85

2022_CCC_S3 commented on Feb. 26, 2022, 3:10 a.m.

L + Bozo + Waterloo Reject + Family Disgrace + Commit Seppuku

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

24

ColonelBy_team10 commented on Nov. 10, 2022, 6:05 a.m.

bro created a throwaway account as if he was gonna get banned off DMOJ 😭

6

yunz_qiao commented on Feb. 24, 2022, 10:32 p.m.

i rlly like this problem except i didnt solve it during ccc

13

kdrkdr commented on Feb. 24, 2022, 7:05 p.m.

angery ;-;

17

b_wang commented on Feb. 24, 2022, 6:06 p.m.

rip ccc score :(

16

Gamma_Ray commented on Feb. 24, 2022, 4:58 p.m.

CCC has become terrible this year, thanks to Mr. Riolku Gugeler and his team. Lots of server issues and users joining the wrong contest on the main CCC site this year. 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 and duplicate contests on the users, your team, or the wind blowing than learn a bit about load balancing to prevent overloading your servers, and naming conventions to prevent students from accidentally joining the contest outside North and South America.

This must have emboldened them to make the 2022 Senior contests a disaster. Take for example Problem S3 in 2022 - Good Samples. It has efficient solutions using Ad Hoc. However, these subjects are not in the Canadian high school math curricula, let alone computer studies.

In fact, Mr. Riolku Gugeler has SPECIFICALLY complained about difficult Ad Hoc problems. Take his comment on the Ad Hoc problem 'Loop Town' on last year's CCO:

eliden (loop town author) handed me the editorial, and i [still] didnt get the first subtask

Maybe there are other ways to solve it but they'd be extremely contorted. Ad Hoc provides a decisive advantage. Unsuspecting kids who attempt to circumvent or reinvent Ad Hoc will burn out their entire contest time and more.

The other problems in 2022 CCC Senior are equally out of whack. Either an illusionary image of Cancer Geo, some obscure 'Tree DP' technique being mandatory for S5, or overly implement-y and math-y questions like the question with the fours and fives. No fun data structures which make up a good portion 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 advanced problem solving techniques 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 2022 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 powers that be are willing to fix the 2022 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 Mr. Riolku Gugeler took over and wasted it. 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

29

wleung_bvg commented on Feb. 24, 2022, 11:51 p.m.

I get that this is a long running gag that's not meant to be taken too seriously, but I think it is getting a bit out of hand.

Keenan (Riolku) Gugeler is not in charge of CCC. He (and most of the other committee members) are not involved in (and not responsible for) setting up the contest registration or handling server issues. Despite this, he is going above and beyond and is actively working on a solution to address the server issues, as well as other CCC Grader concerns. Students who joined the wrong contest will still be eligible for the Honour Roll and CCO, as this is based on the school you are registed with, not which contest you joined.

Keenan has definitely not complained about Ad Hoc problems in the past, and I fail to see how his comment on a single question's editorial is related to his opinion on the category. Saying a problem is hard does not mean that all problems in that category are hard, nor is it equivalent to a complaint about that problem or the category.

On the topic of the IOI syllabus, most fun data structure are actually considered out of scope. 2D data structures, wavelet matrices, skew heaps, static and dynamic graph data structures, most string data structures, and almost all geometry related data structures are considered out of scope. In fact, in recent years, there has been a shift towards Ad Hoc problems, with around half of the problems every year being Ad Hoc (https://dmoj.ca/problems/?show_types=1&category=5&page=3). That being said, CCC is not soley used for IOI selection (it is around one-third of the weight, with the remainder from CCO, which follows the IOI syllabus even more closely).

Funny enough, the intended solution (and the solution most contestants used) is much closer to greedy than Ad Hoc. For the other problems, S1 is something you would probably see on a Codeforces Div 2 Problem A. S2 tests basic understanding of the map data structure, which is usually taught by this time in Grade 12 computer science courses. S4 is a counting/combinatorics problem that would perhaps show up on a contest like USACO or AtCoder. S5 is tree dp which shows up almost everywhere in competitive programming. While the problem quality is not as high as some would have liked, it is certainly unfair to declare them to be "out of whack" when similar problems have showed up in many other competitive programming contests.

CCC scores (along with many other high school achievements) have very little impact on jobs and grants, especially after the first year of university.

As I mentioned before, work is currently being done to address many of the CCC Grader concerns, with Keenan contributing significantly. But as he is not the person in charge, his suggestions may not necessarily be implemented.

Hopefully this is the last time we will see this copy pasta. Certainly there are disappointments with the current state of CCC, but this copy pasta highlights all the wrong parts and none of the actual issues.

0

badlol commented on Feb. 25, 2022, 12:14 a.m.

orz riolku

-15

Lost commented on Feb. 24, 2022, 11:20 p.m.

Do you think a template contest is better? Where you memorize tons of data structures and copy paste them?

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

10

fireball commented on Sept. 4, 2022, 3:25 p.m.

If you memorize the data structures then why would you copy-paste them?

15

LeonLiur commented on Feb. 24, 2022, 3:11 a.m.

gg hardstuck p3