Are coupon codes sent? I haven't received it yet.

For Chef and Deque isn't the time limit tight if $$$O(3^{logn})$$$ was allowed to pass? My solution in C++17 (https://www.codechef.com/viewsolution/50292475) failed and the same in C++14(https://www.codechef.com/viewsolution/50317654) passed right on the time limit. Is C++17 slow on Codechef?

Did it with $$$DP[v][l]$$$ = min cost to reach $$$v$$$ from source using $$$l$$$ edges

Find number of subsets when $$$k$$$ is even. Natasha will win if and only if unblocked states with odd parity is greater than unblocked states with even parity. Iterate over number of blocked states with odd parity. Some algebra and counting is left afterwards. Do the same for odd $$$k$$$ and add them.

Same didn't realized that until I saw your comment, I thought maybe $$$4N$$$ was too large but fortunately writing iterative segment tree worked it didn't required handling $$$n=1$$$ case separately.

For D2E is this true — If we make a graph of array as nodes result is $$$2^{c}$$$ where $$$c =$$$ number of bipartite components?

Weak pretest in E1 — my AC code fails on n=8,k=8 [dcdadcdb]

You already commented the same before ¯_(ツ)_/¯

Yeah, very stupid of me being unable to find such simple algorithm given that I had used this before more than once

I found that my $$$D$$$ is on the edge of the TL much latter in the contest but decided against improving it(I hope it passes), how to calculate number of divisors for each [1,2n] fast, I did $$$O(sieve*logn)$$$?

Can precision loss be an issue? I did the same but it failed and I still don't know what's going wrong in my solution https://ideone.com/iedIGo

C++17(64-bit) is really fast(For $$$E$$$ TC-15 takes more than 2000ms while same code runs in 841ms on C++17 on TC-15), I managed to AC $$$E$$$ in $$$O(n^{3}m)$$$

Is it possible to add a feature where we can extract all contests authored by a [username]?

First assume that $$$b = 0$$$. Let the value we end up in the interval be $$$v \in [L, R]$$$. $$$ax\equiv v$$$$$$(mod$$$ $$$M)$$$. Since $$$gcd(a,M)$$$ maybe $$$ \gt 1$$$ we cannot directly take $$$a^{-1}$$$.

$$$\Rightarrow$$$ $$$ax\equiv v$$$$$$(mod$$$ $$$M)$$$
$$$\Rightarrow$$$ $$$ax + qM = v$$$
$$$\Rightarrow$$$ $$$d(a'x + qM') = v$$$ where $$$d = gcd(a,M)$$$
$$$\Rightarrow$$$ $$$(a'x + qM') = (v' = v/d)$$$ $$$and$$$ $$$d|v$$$
$$$\Rightarrow$$$ $$$a'x\equiv v'$$$$$$(mod$$$ $$$M')$$$
Now we can use $$$(a')^{-1}$$$ to get value for $$$x$$$ given $$$v'$$$.
Since, $$$L \leq v \leq R$$$
$$$\Rightarrow$$$ $$$L/d \leq v/d \leq R/d$$$. We can divide $$$L$$$ and $$$R$$$ by $$$d$$$.
Now if $$$b \gt 0$$$ then $$$d|(v - b)$$$. Then $$$d$$$ divides either both of $$$v$$$ and $$$b$$$ or none of them, this means that $$$\frac{v-b}{d} = \frac{v}{d} - \frac{b}{d}$$$. Now we can also divide $$$b$$$ by $$$d$$$ and use the inverse

$$$C$$$ can also be done in $$$4$$$$$$\lfloor \frac {n} {3} \rfloor$$$ $$$+$$$ $$$2$$$ queries, though my solution uses $$$3$$$ more queries

How to solve E? I can only come up with $$$O(n^4)$$$ $$$dp[i][j] =$$$ ways to turn on $$$i$$$ computers with $$$j$$$ operations used

D is so much harder than E for me. How to solve it?

An ARC as well

Let's first to solve this problem — Consider a set $$$S$$$ union of an element $$$e$$$ and a set $$$S'$$$. Let $$$a$$$ be an element of $$$S'$$$. What's the probability that $$$a$$$ is taken out of $$$S$$$ before any other element from $$$S'$$$? Following calculation can be done to find that p-bility. First take $$$e$$$ and than $$$a$$$ or take $$$a$$$ on first turn. p-bility is $$$(1/|S|)*(1/|S'|) + (1/|S|) = (|S'| + 1)/(|S|*|S'|) = 1/|S'|$$$ since $$$|S| = |S'| + 1$$$. Now let $$$S = P\bigcup$$$ $$$Q$$$ and $$$P\bigcap$$$ $$$Q = NULL$$$. What's the p-bility that element $$$a$$$ form set $$$P$$$ is taken before any other element from $$$P$$$. We can notice that order of elements from $$$Q$$$ does not matter therefore we can consider the set $$$Q$$$ as single element $$$e$$$ and this is same as above problem.

Here is my submission — https://atcoder.jp/contests/arc114/submissions/20961705

$$$E[turns] = E[horizontal cuts + vertical cuts] = E[horizontal cuts] + E[vertical cuts]$$$. . $$$E[horizontal cuts]$$$ = $$$\sum_{i}P(i).1$$$ where $$$P(i)$$$ is probability that $$$i'th$$$ row is cut in some turn. To calculate this sum iterate over each row and find probability that this row is deleted. Let's consider the two given black cells have rows $$$r$$$ and $$$y$$$ where $$$r \lt y$$$. Make a square having two black cells as opposite ends. Whenever we cut any lines in this square game ends immediately. Let's call total lines in this square as $$$T$$$. Consider each line above $$$r$$$, to find $$$P(r)$$$ notice that we have to cut this line first from a set of rows which should have every row from this row to $$$y$$$ and all columns in the square we drawn above which is equal to $$$S=y-i+T$$$. $$$P(i \lt r) = 1/S$$$. Now you can similarly consider other two cases where row resides in square and row lies below square. Also do the same for vertical lines.

My solution is very different and I am yet to prove why it is correct Basically we can find a formula $$$n(3n - 3 - 2s) = \sum{t_i}$$$ where $$$s$$$ is score of each team and $$$t_i$$$ is number of ties played by team $$$i$$$. Here comes my unproved assumption that each team will play same number of ties. Now to minimise total ties maximize score and then I just greedly assigned wins, loses and ties and I don't know why this is correct

Yeah for me D was easier than B and far easier than C. How did you guys solved C?

Is E just doing DP courses by courses and for storing DP values of previous course in segment tree to get DP values in current course i.e. for DP[i] in current course we will get $$$m$$$ segments in previous course to consider value?

Genius!

Yeah it should fail systest. I didn't even bothered to calculate the probability of success during the contest :(. What is TLE retry trick?

My randomised solution for C/A - Ask randomly for value at indices until we get a value <= 50. I used 40 iterations. Find two neighbours if both are greater we got the result else one neighbour must be less than this value if we follow this decreasing chain which is atmost of length 50 we can get our result at the end of such chain

Anyone with randomised solution for div2 C?

Not a closed form solution as mentioned in editorial but here is my approach — Starting with standard approach to this type of problems — $$$f(i)$$$ denotes expected turns to reach the goal given that we start with prefix of length $$$i$$$ Recurrence — $$$f(i)$$$ = $$$p(s[i+1]).(f(i+1) + 1)$$$ $$$+$$$ $$$sum_{ch!=s[i+1]}p(ch).(f(trans(i,ch)) + 1)$$$ where $$$p(ch)$$$ is probability to get the digit $$$ch$$$ and $$$trans(i,ch)$$$ is normal KMP failure function. Problem is we cannot use $$$DP$$$ to solve since recurrences are cyclic. We need Gauss but it is slow(Can we use some other kind of substitution trick to solve?). After that I thought if we can find the expected value to get from $$$trans(i,ch)$$$ to $$$i$$$ we can get the acyclic recurrence. Let's denote $$$DP[from][to] = EV$$$ to reach $$$to$$$ from $$$from$$$. Assume $$$from = to - 1$$$. We can write $$$DP[to-1][to] = p(s[to]).1 + sum_{ch!=s[to]}p(ch).(DP[trans(to-1,ch)][to-1] + DP[to-1][to])$$$. Open the recurrence accumulate coefficients of $$$DP[to-1][to]$$$ to left side which is simply equal to $$$p(s[to])$$$. When $$$from \lt to - 1$$$ we need $$$DP$$$ values for $$$DP[from+1][to]$$$ and $$$DP[loc][from]$$$ where $$$loc \lt from$$$ so process $$$DP[i][j]$$$ in increasing order of $$$j$$$ and decreasing order of $$$i$$$ you have acyclic recurrence now you can use $$$DP$$$ to solve it. Proof from the editorial of the formula is very good.

Pairs whose parity of powers of prime are same are adjacent

Please predict adhvana future rating

Does greedily converting 'X' which provides most number of winning configs work in C1?

Can someone please explain time complexity of https://atcoder.jp/contests/arc105/submissions/17342664? Shouldn't it be TLE with case $$$n = 2$$$, $$$a = [1, 1e9]$$$? Edit — Another user mentioned this above

For each $$$n$$$ we only require $$$phi(d)$$$ where $$$d|n$$$ and some powers of $$$k$$$ and $$$k-1$$$ which can be precalculated, Now we can just perform sieve like process

I keep getting MLE until I switched to bfs

I solved 4 problems(1-4)

Problem 2 : For each node with depth < p, it is valid to color them either Red/Blue, for the rest of the nodes colors are determined by the nodes with depth < p

Problem 3 : Using linearity of expectation, fix a color find the total number of valid necklaces which have atleast one bead with this color, finding ways is straight-forward application of Burnside Lemma

Problem 4 : Use this construction — (1, 2, 3,..,b-1, n, b, b+1,....,n-1)

My sad story — Wasted more than 1.5 hours on P2 because dfs doesn't work, Wasted another 1.5 hour on P3 due to a stupid bug in Eulier totient function

$$$O(n*m)$$$ is trivial if you know about linearity of expectation. To optimize it observe that for a fixed shield all $$$d_i$$$ smaller than $$$b_j$$$ have same contribution(number of ways such that we can $$$d_i$$$ damage to $$$j'th$$$ shield) and all $$$d_i$$$ greater than or equal to $$$b_j$$$ have same contribution. Do some counting and prefix sum and binary search and that's it.

If you figured it out, could you please help me? UPD — Done

Sorry t is tot only

For D is this correct — $$$result = max(a_1 - x, tot + x)$$$ where $$$x = (a_1 - tot)/2$$$ and $$$tot = sum(a_i - a_{i-1}) $$$ $$$if$$$ $$$positive$$$ ?

Maintain left and right childs and a tag for each level if they have to be swapped. Reverse operation is same as swapping at all levels below current level.

This is not the reason for my TLE verdict

I am not using "\n"

My 2-dfs calls in B is receiving TLE, is it expected ?

Does this works for Div-2 E — Make a graph $$$g[i][j][k]$$$ = how many edges exist such that its head is on node with $$$i$$$ outgoing edges and tail is in node with $$$j$$$ outgoing edges and it is $$$k'th$$$ smallest one. Then we brute force every $$$c_i$$$. That will be $$$O(k!k^2)$$$

Likelihood of me featuring in a Lockout dual vs tourist?

It's same solution except that I used dp to find longest subsequence of form xyxyxy..xy instead of simple greedy.

I see many people solved $$$C$$$ without $$$DP$$$, how to do it without $$$DP$$$ ?

For me "play with a problem on paper, then code something trivial when done" is much more interesting than "write some STL/DS and play with its details while coding the trivial solution".

Do you have any plans for problem solving? I have some problems from earlier SRMs for which I am interested to know the solutions.

Maybe a bit off-topic but I am curious to know are there any CPers whose works are different like historian, music, agriculture, biology etc..

There always exist an optimal solution with $$$k \lt = 3$$$

How to solve A? I had following idea — Find basis of both list and check if for each element of 2nd basis there exist a subset with xor sum equal to that element using 1st basis? Sadly, I cannot find any test or flaw in this solution

I will try — $$${p^{k_{n}}}$$$ = $$${(00..010...)}_{p}$$$ where on-bit is position $$${k}_{n}$$$. Assume $$${k_{n-1}}$$$ is less than $$$k_{n}$$$ otherewise take them in different sets and proceed. Let $$$j$$$ be the largest index such that adding $$$p^{k_{j}}$$$ will result in sum $$$greater$$$ $$$than$$$ $$$or$$$ $$$equal$$$ $$$to$$$ $$${p^{k_{n}}}$$$. Before adding $$$p^{k_{j}}$$$ state will look like — $$${(00...(p-1)(p-1)(p-1)(p-1)...(p-1)00..00)}_{p}$$$. Earlier digits are not set because we are proceeding in non-increasing powers.

How to prove that there exists such j ? UPD — Convinced myself by thinking in terms of base p.

For D does sum of size of $$$k$$$ subsets is equal to n or was it not necessary ?

Why is this incorrect in D — Find maximum. Then use binary searchto find which subset contains that max element. Ask another query not containing that subset

It will be minimized by the number of nodes at next level

_t can exceed long long range https://ideone.com/WCUZ3U

Yeah, did the same when I finally got an AC

Yes, I solved with DP.

Can $$$ \lfloor X \rfloor $$$ and $$$ \lceil X \rceil $$$ and then temperatures at these points be calculated with good precision ?

Petr is recently using C++ and he writes neat and detailed code.

Hey Arpa can you help in figuring out the mentioned straightforward transition step in Div1-Medium $$$dp[t][i] = p*dp[t-1][i] + q*(dp[t-1][i] - 1) + r*(dp[t-1][i] + 1)$$$ where $$$p, q, r$$$ are probabilities of selecting counter which do not have value $$$i$$$ or $$$i-1$$$, selecting counter with value $$$i$$$, selecting counter with value $$$i-1$$$ respectively. How can I find these probabilties ? Is $$$q = dp[t-1][i]/n$$$, $$$r = dp[t-1][i-1]/n$$$ ?

If only colors to be used are 1 and 2, arriving to the concept of bipartite will be instantaneous. And it's just a couple of more lines of code. Tracing dp is hated but so is geometry so your claim for C can be loosely applied here. Where do you suggest to place this problem in problemset?

I agree E doesn't require much creativity but why E isn't suited for edu round(I think it bring concepts of bipartite graphs, knapsack and the building dp answer which is educational)

Use binary jumps

There will be $$$n$$$ equations one for each $$$state$$$. You can write them as $$$AX=B$$$ where $$$A$$$ is $$$n*n$$$ probability matrix and $$$X$$$ is $$$n*1$$$ vector of expected values.

How to solve? Was the answer just n?

I meant that A was good and C was not

My views on A and C are opposite to yours. There is only one special case in A and even that is given in sample tc.

This is exactly what I did but got WA-2, I used double rolling hash

Is it possible to solve D with hashing?

It's fine — You missed a multiplying factor $$$x$$$ because you can choose any of them on the bigger side. 72880191

How to solve E ? I had following idea — Sort by 'a' and then do dp[i][mask] = maximum score till i'th index such that 'mask' position of players are selected. Add it to audience if possible. This gave WA-16.

Edit — Caught the error.

What's the reason 70267449 'Compilation Error' in C++17 but the same 70270849 worked on C++14 ?

What's wrong with this solution for F — dp[node][level] = answer for subtree rooted at 'node' such that among all selected nodes the smallest depth is at 'level'? This recieved WA-3

Let's fix the root of the optimal sub-graph. Let's define two types of segment for each node — a point segment(where only this node is used in optimal sub-graph) and a batch segment(where this node along with its its subtree childs are used). Assume fixed root has batch segment, then we can use atmost two types of batch segments which intersects with segment of root and infinite point segments. For all non-root nodes we can use atmost one batch segment and infinitely many points one. This may be not clear to understand because of my explaination but maybe this picture can give you an idea — (https://imgur.com/HPwMhoi) This is simple DP. Details in my code. But root can be any node not just the one we selected initially. Assume child of above fixed node is new root then either previous node will add as point segment — we can add 1 to dp[new_root][0] otherwise it act as a batch segment then we can just swap two batch segments of new_root and prev_root and hence this value will be equal or maybe there exist a rerooting parameters(?).

Do bfs by starting a node in first set.

So for set {6,6,1,1} We can insert 1 or 2 or 4 but cannot insert 3 because it will better than both 1 and 6. Right, you cleared it up, Thanks!

Why cannot we take complete set — 1 and 4 obviously cannot dominate 5 and 5 cannot dominate in presence pf both 1 and 4. Is it flawed ?

What is the answer of D2-D for case -> A = 5, 4, 1 and B = 5, 5, 5 ?

Firstly, thank you for reaching out to help :). I got my mistake.

Can someone explain why this solution 40510312 is getting TLE on problem 600E - Lomsat gelral. I'm using style 4.

No that was not the problem. cntcl[op] -> cntcl[maxn]

Different answer for same code 1. http://codeforces.me/contest/990/submission/39189478 2. https://ideone.com/XWY4uR

TopCoder Recipes - 1. https://apps.topcoder.com/forums/?module=Thread&threadID=700080&start=0 2. https://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0 3. https://apps.topcoder.com/forums/?module=Thread&threadID=697925&start=0

x2 = k2p2 — (1) x2 >= x1 — (2) (k2-1)p2 < x1 -> k2p2 — p2 < x1 -> x2 — p2 < x1 by (1) — (3) By (2) & (3) Range of x1 is (x2 — p2, x2] -> [x2 — p2 + 1, x2] where p2 is largest prime factor of x2.

Yes : http://codeforces.me/contest/914/submission/34679495

[DELETED]