TREFFE - Editorial

[vijju123]

PROBLEM LINK:

Div1
Div2
Practice

Setter- Abhishek Pandey
Tester- Swetank Modi
Editorialist- Abhishek Pandey

DIFFICULTY:

HARD

PRE-REQUISITES:

Graph Theory, Dynamic Programming, GCD Properties, Number Theory, FFT

PROBLEM:

Its too big to be cited here. Please read the problem statement.

QUICK-EXPLANATION:

Key to AC- Reading the problem carefully is the key for making the crucial observations which would allow use of DP and FFT in the question. GCD properties also help.

EXPLANATION:

Explanation (Detailed)

Before starting the editorial, you are HIGHLY advised to read and practice these two problems in the tab below.

They are-

1. CIELHACK
2. WORDNINJ

Once you are done with them, you’d realize that this problem is a very simple, or trivial extension of the intermixed concepts applied by them. Note that the solution uses the concept used by the best solution in WORDNINJ and hence can be slightly tricky to understand. Once you are done with these problems, you may refer to the tab below.

Detailed Solution

Your effort and intent to plagiarize in APRIL19 long is recorded (thanks to discourse giving names of users clicking links). Appropriate rating penalty and/or account ban will be applied in a few hours. We’d like to remind that codechef is committed in weeding out cheaters from the community who spoil the fun and decorum of the forums and also play against the contest spirit.

Cheers!
Regards,
Yours Faithfully
@vijju123

SOLUTION

Setter

TBD

Tester

His lazy barbie doll hands are yet to write the code. Lol.

Time Complexity=O(N^\frac{5}{3}LogN)
Space Complexity=O(N)

CHEF VIJJU’S CORNER

1. TBD after looking at contestant’s solution

[abhi2402]

Actually, the question also requires knowledge of persistent data structures, heavy light decomposition and anything else that makes this question more simple than it already is

[akashbhalotia]

Lol, reported it, thinking @vijju123 was high or something and then they said ki read the full thing

@vijju123, why you do this?

[vijju123]

Everyone who clicked Div1 or Div2 link will also be counted towards penalty. We’d like to remind that codechef is committed in weeding out cheaters from the community who spoil the fun and decorum of the forums and also play against the contest spirit.

Regards
@vijju123

[anon55659401]

Thank-you for giving the editorial before the contest starts

Next thing, should be, everyone having more than 100-Codechef laddus should be given no time limit constraints for 2-3 problems in long challenge of their choice

[vijju123]

It is already in our pipeline! Dont worry

[vijju123]

You got peeped!!!