Maybe it's like Div 2A, Div 2B, Div 2C/1A, Div 2D/1B, Div 2E/1C, Div 1D and Div 1 E?

1

YEEEEEEEEEEEEEESSSSSSSSSS!!!

Codefest'17 is excited to present a mathematical programming contest — Mathmania. It will bring a delectable collection of problems which will be an absolute delight for all the mathematics geeks. Cash prizes worth INR 50,000.

Anyone can participate and win the overall 1st,2nd and 3rd prizes. Same is true with the best in India prize.

These are the links for the previous year's machine learning and CTF contests.

Also, this year's CTF event has already started and can be found here.

This year's machine learning and NLP events will also start soon.

The round is rated for both Div1 and Div2 participants and consists of 7 problems.

Manthan, Codefest 17 will take place on Sunday 24th September, 2017 08:05 IST with a duration of 2.5 hours (tentative).

And it must be XD.

well every one cant have high rating ...

I won't post any comment taking about the future contest.Every time I post such comments I got TONS OF DOWNVOTE!!!!!!!

TooDumbToWin Fandom!!

Sometimes we should enjoy the process of the game rather than care about the rating...

Thanks! I have updated it.

.

On the best platform ever — codeforces. :')

That means you already registered

Your comment is rated.

In B, Did you applied DP ?

It smells like DP.

Please ask these things after the contest

My solution:

We can distinguish three types of parents for each node:
1. A parent which is high security, which means this node has to have a type that is smaller than k
2. A parent which is not high security, but has a type 1...k-1, so this node could be high security, or have a type from 1...k-1 or from k+1...m
3. A parent which is not high security, but has a type k+1...m, so this node can not be high security, but it can have a type from 1...k-1 and k+1...m

So you can specify a dynamic programming state as node id, parent type, number of high security nodes in subtree, which leaves a complexity of O(N*3*x)=O(Nx) which is small enough.

I didn't manage to implement it during contest successfully, but I'm pretty sure it's correct :/

.

Did we have to print answer modulo 1^9+7 or something for Problem B? My submission kept failing.

also the structure is not a tree but a forest and "...An object is considered to be neither a part of itself nor a special case of itself". That caused me 2 WAs :(

Overflow:

3 -1000000000 -1000000000 -1000000000
1000000000 1000000000 1000000000

I hacked with this 1 1000000000 1000000000 1000000000 -1000000000

min or max value of result -3e18 or 3e18 wtf

3 -2 3 -2 1 2 1

Answer: 2

I approached just like yours(with some hardcoded precomputations) but it was too slow.

Yes, "object", "special case", "part" all these terms are very unintuitive and it was very difficult to reason anything about this. I tried for 5 minutes and for the sake of my sanity I decided to let go this problem even if it later turns out to be very easy :P

ah, it can be forest. Beautiful. Wonderful. So I guess that's why I got WA 9.

How is it possible to get "in query of type 2 if v is ancestor of u then NO" from the statement? I don't think it follows from "An object is considered to be neither a part of itself nor a special case of itself." sentence. Why a special case of object is object? It looks more like isinstance vs type in python :)

.

I honestly felt the difficult was A<B<E<D<C. Both E and D are well known problems and E takes less time to code while D is so difficult to understand with so unusual choices for terms and input conditions. In the case of C, maybe I'm approaching it wrong but I couldn't get the problem state in any clearer manner than 4 parameters (2 to specify sub-tree, number of high security, can build high security) with several end conditions.

If you're at state "I can use every number from now because I guaranteed current number is smaller than R", then you have nothing to do with R so you can just use precalculated values for every base.

Precompute the following values: dp[base][length][mask] = number of combinations of the digits 0 to base-1. The binary representation of mask determines, which digit should appear odd and which even times.

Then you can define a function f(base, x), which returns the number of numbers <= x, with each digit appearing an even time. Then the answer is f(r) - f(l-1).

To implement f:

• Convert x to base base.
• iterate over all possible lengths of the numbers
• if the length is stricktly smaller then the length of x, the answer is sum(dp[base][length-1][1<<digit] for 1 <= digit < base).
• and if the length is equal to the length of x, you need to iterate over the digits of x, keep the mask and build similar sums.

Fix the position of q. Then p matches with max(input[1..pos_q]) and r matches with max(input[pos_q...n]). Both maxes can be calculated in O(1) thanks to easy precomputations.

I figure this is much much simpler than DP:

	ll bestp = -INF;
	ll bestpq = -INF;
	ll bestpqr = -INF;

	for (int i = 0; i < n; i++) {
		bestp = max(bestp, p * values[i]);
		bestpq = max(bestpq, bestp + q * values[i]);
		bestpqr = max(bestpqr, bestpq + r * values[i]);
	}

	cout << bestpqr << endl;

You can solve C with next DP states DP[ root of subtree] [ amount of highest elements] [ value of current element ( smaller than k, equal to k, bigger than k ].

For E I think it is also some easy DP, I think it is called DP on Digts — but I didn't try to write code :)

E is just well-known DP on digits.

At least, E's statement is much easier to understand than D's.

For example if somebody set the final answer as 0 then update it in O(n) process then when there have some cases like

4 12 14 16

-1000000000 -1000000000 -1000000000 -1000000000

then he will output 0 instead of correct answer

How did you solve C?