July 18- Problem Discussion

fuck… I only referred one new algo for this problem… and that was LCA !!!
but didn’t worked on it thinking that would be a tougher question… :frowning:

polynomial multiplication means FFT.

also had an intuition that I ll need DP

@vijju123 yes, you are right about tom and jerry

Thanks for your insight @psaini72 . Lol no, its not a way to collect alternate solutions. Its just a mix of factors which prompted me to make this thread. Like, problem discussion after CF is cool, why not have it at CC as well? Then, editorials arent out and its just after the contest- many high rated coders surf discuss at this time for editorials. I think they’d love to hear and share approaches as well. The igniting point was, hearing from a friend that “I feel shy sharing my approach - people will feel I am self-publicizing.”- So there you are, why not have a fun thread with alt. soln? :slight_smile:

@swetankmodi - Any hints if you solved the question? Any link to tutorial etc?

modulo is wrong. Refer to my solution.

@vijju123, that is a nice thought and a nice effort on your part. You should also add some of these answers on the actual editorial page ( if you feel they should be ) just to help anyone trying out these problems in the future, because I don’t think many people will write another answer on the editorial page.

An unrelated question:
Do you get a notif everytime someone writes @vijju123, or do you just regularly check the forums everyday?

2 Likes

Also, why aren’t the editorials released just after ( or a few minutes after ) the contest is over, if, according to Guidelines | CodeChef, the editorials are finished even before the contest starts?

AFAIK its 50 karma for commenting on other’s answers. Yes, I will add it in editorial part via links, i.e. something like "Many interesting approaches are also discussed here - ". I cant copy paste their answers - else that’d mean me getting karma which ideally belongs to them. I can give links to make sure everyone’s effort is seem :slight_smile:

Top solutions will be marked as accepted so that they remain at top always :slight_smile:

At every index of the string, if u have the count of each alphabet before and after the current index, you should be able to calculate the cost of replacing current index with 25 other characters.

Now the problem is computing the count. This can be done using partial sums. Think about it.

Time complexity - 26 * O(N)

@psaini72 could you please share your integration idea. I was kind of thinking on similar lines.

I started with n = 2 and tried to find a pattern. For n = 2 the required region is the circumference of a circle centered at origin and of radius k/2. But I was stuck with the denominator. I was thinking like choosing 2 circles whose radii sum upto k. I was stuck on constructing the integral as I was modelling them as discrete structures.

I don’t understand your approach that you described in your answer but maybe you should check out my answer to this because I have used the series of e^x there. I can give a brief explanation if you want.

ooooooops :stuck_out_tongue: . Sorry for typo. Thanks! :slight_smile:

Sort pizzerias by position, and construct a segment tree of CHT (each node [L, R] contains a CHT of lines between L and R).

To get the answer for a consumer, you don't need to remove a line from your structure.

Now, supose there are 11 pizzerias, and consumer i doesn't like 3, 7 and 9. To answer this, you should get the minimum of 4 queries: [1, 2], [4, 6], [8, 8] and [10,11]. This works because the sum of forbidden pizzerias is at most 4 * 10^5 and the number of queries is about (N + M). The complexity of the query is log(N)^2 (one log from segment tree and one from CHT).

Above comment taken from here - Invitation to CodeChef July Long Challenge 2018! - Codeforces had run out of chars.

i had the same idea. but didnt code …damn

Idea is if one of the magnitude is greater than k/2 => then there is no way to get sum of vectors to zero.
Alternatively, if all the magnitude is less than k/2 => There is always a way to get sum to zero.

Since the values can be real magnitude and there is a constraint, the possible values will form a hyperplane. So we need to find, what fraction of this possible solution space will have atmost one dimension greater than k/2.

For first dimension to violate the condition, it can be caluculated using integrals to be 1/2^(N-1), N different directions are there. So answer is 1 - N*(1/2^(N-1))

2 Likes

@psaini72, my approach and formula is same as yours. How do you calculate the terms in denominator of g(z) where the denominator is polynomial? The doubt is what is inverse of polynomial and how to calculate it.

First, I thought of: What is the (geometric ?) condition that given n vectors ( both magnitude and direction ) that their sum is the 0 vector.
Looking at the case for n=3, they can be arranged into a triangle when placing the tail of each at the head of another. Similarly, if n vectors sum to 0, they form a sort of chain. From the head of one to the tail of the next.

1 Like