DeliciousFlatChest's blog

By DeliciousFlatChest, history, 5 years ago, In English

1245A - Good ol' Numbers Coloring

Tutorial
Solution

1245B - Restricted RPS

Tutorial
Solution

1245C - Constanze's Machine

Tutorial
Solution
Solution (Arpa)

1245D - Shichikuji and Power Grid

Tutorial
Solution
Solution (PikMike)

1245E - Hyakugoku and Ladders

Tutorial
Solution

1245F - Daniel and Spring Cleaning

Tutorial
Solution
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DeliciousFlatChest (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by DeliciousFlatChest (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

fastest editorial :D It also shows that the blog was made 4 hours ago

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    even made before the contest :) This round is excellent, good job!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

orz DeliciousFlatChest

Please, don't stop creating CF rounds!!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Sorry, what is orz mean?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      Orz (or more commonly, orz) is an emoticon that represents someone who has fallen over or is bowing down on their knees and perhaps pounding their head on the floor. The o is the head, the r is the arms and upper torso, and the z is the rest of the body and legs.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +40 Vote: I do not like it

      "orz" is a verb. The original meaning of "orz someone" is "kneel down for someone", and the extended meaning is "show respect to someone".

»
5 years ago, # |
Rev. 2   Vote: I like it +60 Vote: I do not like it

A smooth Contest without any DDOS attack and any waiting judgement problem!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for so fast editorial! :)

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I solved A without knowing proof. =)))

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow, the fastest editorial I've ever seen! Thanks for the round. Keep hosting rounds further!

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Fastest Tutorial ! Cool !

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I just hope there are 2:15 minutes

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    cool theorem name XD

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    This conclusion was also used in a problem of NOIP2017, whose name is Xiao Kai's doubt (小凯的疑惑 in Chinese). In fact, (A) is an excellent number theory problem. Thanks to DeliciousFlatChest for this perfect round. :)

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I remained stuck in problem 1 for an hour until I realized I have been reading the question all wrong...

»
5 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Is there any way to push dp value ahead for E? I was getting wrong answer for no ladders case, and I couldn't figure out why.

After contest, I saw some solutions ( namely neal's solution, PS: please share some insight ), and I had missed the case when the player is at the last 6 squares, after which he will waste some moves standing there itself.

How to implement this using push dp? I understand the pull from previous 6 version. Is it not possible to push in this case?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    There is a theorem on bernoulli trials that says if there is a probability $$$p$$$ of an event happening on a turn, then the expected number of turns to reach the event once is $$$1/p$$$. With some logic you can see that for the closest 6 squares to the end, the answer will be 6 for all of them.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This result is so beautiful. Thanks.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I implemented push dp for E, calculating p[i] for the possibility for square i to be reached, and dp[i] for the expectation of runs before reaching square i. Also precalculate to[i] for the endpoint for ladder which starts at i.

    Then this code can give currect answer to first two pretests:

    for(int i=1; i<100; i++){
    	int t = to[i]?to[i]:i;
    	for(int j=max(i-6, 0); j<=i-1; j++){
    		int k = min(6, 99-j);       // k is 6 except for last few squares
    		p[t]+=p[j]/k;
    		dp[t]+=p[j]*(dp[j]+1)/k;
    	}
    	if(p[i]>0) dp[i]/=p[i];
    }
    auto ans = dp[99];
    for(int i=1; i<=5; i++){
    	ans += p[93+i]*(i/6.)/(1-i/6.); // expectation of standing still
    }
    

    But later i found out that using this method you cannot judge optically whether using the ladder or not. Because this requires information from the upper values. So i think this problem can only be dp'ed from top to bottom.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand why you say 'requires information from the upper values'. In fact, it is the opposite, for every cell that is the top of some ladder(s) you require answer from the bottom of the ladder(s).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I get accepted using push DP in 64069972. I hope its helpful to you.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DeliciousFlatChest Thanks for the amazing round.

»
5 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

I thought of solving D with MST but statement confused me and I gave up XD. Just came back after contest end to see the clarification.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    It was indeed intended to be MST.

    To not get confused by statement, you can always simplify the statement.

    Simple idea here is, if all vertices are numbered from $$$1$$$ to $$$N$$$, then make a new vertex with number $$$0$$$, and for each $$$c_i$$$ given, make an edge from $$$0$$$ to $$$i$$$ with weight $$$c_i$$$, $$$ 1 \le i \le N $$$. This edge signifies making power station at $$$i$$$.

    Apart from this, make edges between $$$i$$$, $$$j$$$, as mentioned, in $$$O(n^2)$$$ time. Then, it is just simple MST.

    ( EDIT: just realized Editorial has the same thing written xD ).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Amazing explanation. Things just clicked for me after you added the explanation of an additional vertex $$$0$$$

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Exactly D was very deceiving. At first I thought about MST. Then I realised, that constraints are very low, so MST shouldn't be the answer(and it was D question). so I started looking in some other direction. Something like $$$O(N^2)$$$. After the contest I realised, that my assumption was incorrect. The solution could be MST because though the number of nodes is less, Number of edges are very significant( in worst case around $$$ 4 * 10^6$$$).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Actually MST is a poosible solution, and once you saw this problem you might think of MST. Each city is a point in the graph, and you add an edge for each pair of points $$$ (i, j) $$$ with weight $$$ (k_i + k_j) \cdot (|x_i - x_j| + |y_i - y_j|) $$$. According to the statement, we can build a power station in any city. This can be solved by adding a point indexed $$$0$$$. For each point $$$ i $$$ we add an edge between $$$i$$$ and $$$0$$$ with weight $$$ c_i $$$, and this edge means to build a power station in city $$$ i $$$ and costs $$$ c_i $$$. Our purpose is to choose some edges to make all the points connected (including point $$$0$$$). And clearly it's the MST problem.

    However, we've got two algorithms to solve the MST problem — Kruskal and Prim. Kruskal needs to sort all the edges, so its time complexity is at least $$$ O(m \log m) $$$. There are about $$$ n^2 $$$ edges in our graph, so maybe you'll get a TLE. Prim is different. It is similar to Dijkstra and has time complexity $$$ O(n^2) $$$ and you can easily use it to get an AC in this problem.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone help me figure out where am I going wrong in Problem D. Here is my submission 64039688. Thanks in advance.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I Had made the same mistake, found it by trying one of the later test cases.


    Try the following test case
    6
    802169 415058
    438621 719382
    427378 361095
    938841 703007
    651689 546630
    543902 45803
    928313110 402257489 40475518 321650025 335526487 752229521
    91 19 18 39 15 99

    Correct answer:- 171488866
    1
    3
    5
    3 5
    2 5
    4 5
    1 5
    3 6

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In case someone wants to know the reason behind dp[i]=dp[i-1]+dp[i-2]

Eg: Suppose you want to know answer for uuuu, u =1 {u}, uu=2 {uu,w}, uuu=3 {uuu,uw,wu}. Think of uuuu as follows: Uuuu = u+ uuu (Just add u to the strings created by uuu). Also, Uuuu =w+uu (Just add w to the strings created by uu) considering w, because uu case would be considered in previous one)

Hence, uuuu={u+(uuu,uw,wu)}+ {w+ (uu,w)}

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Are you sure it is the reason? I suppose it's due to the fact that by pressing one button we can add either one or two symbols (m -> nn or n -> n) so the number of ways to get to i'th position is dp[i-1] + d[i-2] (e.g. in string "ann" dp[2] = 2 because we could've either written m->nn after "a", that's dp[i-2] ,or just added n in the end of "an", that's dp[i-1])

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone suggest me a solution of problem C using modular inverse?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somebody explain me please what is wrong with this approach to problem B.

Let dp[i][j][k] — maximal number of games we can win if we i times choose R, j times P and k times S.

So if we are at condition r,p,s than we can do the following:

if r+1 <= a than we can choose R one more time and move to r+1,p,s and if our opponent chooses S than we will win one more game so dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]+1), if our opponent chooses something different dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]).

Also we remember that if wins we can get with now is bigger than we already know we can, than parent[r+1][p][s] = 1

And we do the same for p and s

After that we check if 2*dp[a][b][c] < n and say "NO"

else we can win this game and recover the answer.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Idea doesn't seem to be wrong.

    According to checker, you have printed only $$$9$$$ characters, whereas you should have $$$10$$$ chars for input

    $$$n=10, a=5, b=0, c=5, string = RPRSRSRPPS$$$

    Your output: $$$RSRRSRSSS$$$

    Actual output : $$$RRSRRSSSSS$$$

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok,i got it, it was my previous submission. there i got situation where parent[r][p][s] == 0, so that means i cant get there but i didnt check for that. If i check it i cant find sol for this one at all

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, an easy way to solve it is greedily. DP is too complicated, and possibly could give TLE as well. Your solution looks like $$$O(10^8)$$$.

        Easier way is to solve greedily.

        If Bob plays $$$r_b$$$ Rocks, $$$p_b$$$ Papers, $$$s_b$$$ Scissors, and we have $$$a$$$ Rocks, $$$b$$$ Papers, and $$$c$$$ Scissors.

        Then maximum wins are $$$min(r_b,b) + min(p_b,c) + min(s_b,a)$$$.

        Then, just assign $$$min(r_b,b)$$$ places of Rocks in Bob's string by Paper. Similiarly for the rest.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I just quickly wrote the same DP code. ( Check it here. )

        It seems the problem is that you should initialize dp with $$$-1$$$ instead of $$$0$$$. Because in case you have Bob's string as $$$RRRRRR$$$ and you don't have any Paper with you, i.e. $$$b=0$$$, then answer is zero.

        But, since you are updating by checking strict inequality, parent is never updated, even though something like $$$SSS$$$ has parent $$$S$$$.

        Okay, I might be explaining it in a very bad way, but I think you get the gist of it.

        I have done similiar errors. Some basic question like, return index of maximum element in array. I initialize $$$mx = 0$$$ and $$$ind = -1$$$ and return $$$-1$$$, instead of actual index of an element with value $$$0$$$.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          I tried initialize dp as -1 and still get wa.

          After that i rewrote my whole dp once more and finally get ac. No idea what was wrong in my last one

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WA for problem B. Can anyone figure out what's wrong in my code? Thanks in advance

(https://codeforces.net/contest/1245/submission/64019871)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You append thing in the "out" variable only when alice can win, but you should append something when alice loses too.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to understand the editorial for problem F.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain why my code is wrong.

Link to submission:- https://codeforces.net/contest/1245/submission/64040834

Logic Explained:-

For every city, I calculate the minimum cost of providing electricity to it (either by joining with someother city or by installing a power station in it, the former includes adding an edge between the two cities and the latter introduces no new edge.) Then I calculate the cost for every connected component using dfs.

Any help would be highly appreciated.

Thanks in advance

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

for D, what was the intended corner case for test case 13? here is my submission:64025515.

my idea was: consider the graph where every node x is connected to every other node y with edge weight cost dist(x,y)*(k[x]+k[y]). for every node, join them with union find to the closest node in the graph, unless it is cheaper to just add a power station to that node (in this case, don't join this node to any other node). then, assign one power station (the cheapest one) for every connected component. can anyone point out the flaw in my algorithm? thanks.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      thanks! update: the mistake in my algorithm was that i wasn't considering the scenario where the node that has a cheaper power station cost than any neighboring connections could actually be "helpful" to its neighbors and lower the overall cost.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Who can explain proof for D from editorial? I stuck on the case, when there is smaller cost in component. Why is it true that putting power plant there gives more profit? I think myself understanding wrong this point. Here is my exmple breaking this statement: City1 : c = 10001, k = 1 City2 : c = 10001, k = 1 City3 : c = 10000, k = 2

And let take coordinates such as dist(City1, City2) = 2, dist(City1, City3) = dist(City2, City3) = 100

let our optimal city to be City1 There are only 3 cases:

  1. Leave all without changes. Then we have cost = 10000 + 2 * (1 + 1) + 100 * (1 + 2) = 10403

  2. Assign new power plant at City3. Obviously, cost > 20000

  3. Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601

So best power plant is City with c = 10001 So to take the lowest c_i appears not to be optimal.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601",

    There's an issue here... Looks like you've connected City 3 with 1 and 2, but you should have connected City 3 with City 1 and then provide power to city 2 to via City 1. The answer would be 10000 (Station at City 3) + (1+2)*100 + (1+1)*2 = 10304

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In Problem F, Shouldn't f(0,r) = 2 * r — 1 + f(1, r) ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me with my solution of D. here is my code https://ideone.com/tRcPzZ

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem C , how it is reduced to fibonacci ?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    let's suppose we have i n's in sequence ( nnn....n i times ). Now two cases can be there:-

    (1) last character is n

    (2) last character is m ( disguised as nn )

    hence dp[i] = dp[i-1] + dp[i-2].

    The first term for the first case and the second term for the second case.

    Hence, fibonacci

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem C, what is wrong with this approach?

Find the number of consecutive n or u.

Then find the number of possible strings that can create it.

eg. number of consecutive n = 4.

With 0 m, number of possible string = 4!/4! = 1

With 1 m, number of possible string = 3!/(2!*1!) = 3

With 2 m, number of possible string = 2!/2! = 1

Total = 5

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is correct approach and gives AC.

    Link to submission:-

    https://codeforces.net/contest/1245/submission/64014595

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I was getting WA because of an overflow :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Nothing, that's exactly what fibonacci is ! Memoize what you just said and you'll have the fibonacci sequence ! Either way will get to the same answer, just that your way the calculation will get a bit lengthy soon! Better just observe how it can be generalized.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I was getting WA because of an overflow :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding Problem C, what is the intuition behind applying Fibonacci( dpi=dpi−1+dpi−2 ),i mean do i try all possible combinations for small input and then deduce the Sequence is Fibonacci. Any help will be appreciated, Thanks in advance.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can anybody explain why my solution to D is wrong. For each two city x, y add edge between them if (k[x] + k[y]) * d(x, y) is less than building a power station in at least one of them. Then for each component build a power station in city where has the minimum cost and calculate MST for each component for edges that we have to make.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Lets say you have 3 nodes 1,2,3

    dist(1,2)=10

    dist(2,3)=20

    dist(1,3)=30

    let k be 1 for all

    C[1]=5

    C[2]=50

    C[3]=10

    you try to put them all in one same component,because edge cost for 1,2 would be 20 but max(c[1],c[2]) would be 50. Same explanation for 2,3.

    Now you assign power station to minimum C value node in each component. So here in this example it would be 1, and for rest of the node in the component you use MST of edges.

    This fails for the above mentioned example. The above mentioned example in terms of input would be,

    3

    5 10

    15 10

    35 10

    5 50 10

    1 1 1

    The answer for this input would be 35, power stations on 1 and 3 and edge 1,2

    This fails because you join things to same component when edge weight is less than max of c values of nodes.

    When one of the nodes has a c value less than the edge weight, but unfortunately in MST, the node with max c weight can be assigned first, you shouldn't use that edge in this scenario, because instead of the edge, creating a power station on the min C weight node would give better answer.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For 1245E, let's say there are no ladders. After flattening the array, why push dp is wrong.

I am getting 28.0476190

Pushing logic is straightforward.

for(int d= 1;d<=6;d++) 
   dp[f(i +d)]+=(1.0 + dp[i])/6.0

f(x) is the new move as mentioned in editorial.

Here is the code : https://ide.geeksforgeeks.org/BvBaJFwLip

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is r. If the Goal is less than r squares away on the path, the player doesn't move (but the turn is performed).

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Thank you for the beautiful contest, DeliciousFlatChest !

Here are my thoughts on the problems —

  • $$$A$$$ — It was a very elegant problem on Bezout's Identity

  • $$$B$$$ — Good Greedy Construction Problem

  • $$$C$$$ — DP

  • $$$D$$$ — It reminded me of this problem on AtCoder — Various Sushi 116D. I was trying to use a similar idea here. After sorting the power stations by their cost,

I thought of first, making power stations in only the first power station and building connections for all the other stations.

Then, to make a power station in only the first 2 power stations and build connections in all other power stations.

And so on.

However, this was $$$O(n^3)$$$ and I couldn't find a way to make it shorter.

The MST solution is quite surprising !

  • $$$F$$$ — Again it reminded me of 2 AtCoder questions — Sum Equals XOR 129E and XOR Sum 2 098D. The main difference between $$$129E$$$ and this question was that in $$$129E$$$, only $$$a + b$$$ had to be $$$ < L$$$, but here both $$$a, b$$$ had to be in $$$[L, R]$$$. I was trying to build on the solution to these problems for this one.

By the way, here are my solutions to the problems of this contest so far in case anybody wants to refer them.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve F using digit-dp like algorithm?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Yes.

    Alternate solution to problem F: you can use digit dp to find the answer :) You need to keep track of 5 states. Let, $$$dp[f1][f2][f3][f4][p]$$$ = Number of pairs of binary numbers with $$$p$$$ digits and $$$f1, f2, f3, f3$$$ are $$$0/1$$$ values indicating:

    $$$f1 = 1$$$ means first number is bigger than $$$l, 0$$$ otherwise
    $$$f2 = 1$$$ means first number is smaller than $$$r, 0$$$ otherwise
    $$$f3 = 1$$$ means second number is bigger than $$$l, 0$$$ otherwise
    $$$f4 = 1$$$ means second number is smaller than $$$r, 0$$$ otherwise

    Ideally, when you have $$$f1 = f2 = 1$$$, that means our current number is already within $$$[l,r]$$$ giving us the freedom of putting any $$$0/1$$$ as current digit. Other cases? You can easily figure that out.

    So using $$$f1, f2$$$ we can find some $$$[l1, r1]$$$ bound for current digit of first number. And using $$$f3, f4$$$ get another bound for second number $$$[l2, r2]$$$. Now bruteforce on all possible pairs other than $$$1,1$$$ pair :)

    My submission 64025375

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you elaborately explain your approach with few examples.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for your solution, but I think the definition of $$$DP(f1, f2, f3, f4, p)$$$ should be

      "The number of pairs of integers $$$(a, b)$$$ GIVEN that the first $$$p$$$ digits of BOTH $$$a$$$ and $$$b$$$ cause... (now cases on $$$f1, f2, f3$$$ and $$$f4$$$)"

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I recommend to try out few digit-dp problems otherwise you may not understand anything.

    My digit-dp approach:
    Let $$$f(x, y)$$$ be a function which returns all pairs $$$(a, b)$$$ such that $$$a + b = a \oplus b$$$ where $$$0 \le a \le x$$$ and $$$0 \le b \le y$$$.

    Now to calculate $$$f(x, y)$$$ we will use digit-dp approach. In our digit-dp we will consider bit representation of $$$x$$$ and $$$y$$$ rather than decimal representation which is generally used(as this is obviously a bit manipulation problem :P). Let $$$dp[i][f1][f2]$$$ = Number of pairs possible such that $$$a \& b = 0$$$ $$$(0 \le a \le x$$$ and $$$0 \le b \le y)$$$ considering $$$i$$$ rightmost bits. Here $$$f1$$$ signifies if we selected $$$i - 1$$$ rightmost bits in such way that we may not want to consider $$$1$$$ bit for $$$i$$$. $$$f2$$$ signifies same but for $$$y$$$.

    Now, answer will be $$$f(r, r) - 2 \times f(l - 1, r) + f(l - 1, l - 1)$$$.

    Answer Explaination

    Link to Code

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can some explain what is mean by "minimum expected number of turns" in problem E?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It means assuming that the player plays optimally. In this specific problem, whether to take the ladder or not.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A is very, very beautiful. Sad that many of us (including me) solved it without being aware of the complete proof. (I only proved the Bezout's theorem part).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me. Im getting wrong answer Testcase 9 for Problem C. I think my logic is correct as the alternative solution. Still doesn't work. How to even debug in such cases?64029232

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    rep(i,2,100002)
    {
        dp[i] = sum[i-2]+1;
        sum[i]=sum[i-1]+dp[i];
    }

    won't you get an overflow here?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why? after I change to dp[i]=dp[i-1]+dp[i-2] I still get signed integer overflow. Im unable to see why its overflow, dp size is big enough? 64068550

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Um, yes, but integer/long long size is not big enough. You should be doing operations mod10^9+7

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for the problem f I am checking accepted solution and here I found one in which I am not able to understand this line. solution link — https://codeforces.net/contest/1245/submission/64013273

line ===>> int ans = f(r, r) — 2 * f(l — 1, r) + f(l — 1, l — 1);

How above line gonna work . Anybody ..thankyou.

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I think that in function f is gets pairs, which a <= l && b <= r && a ^ b == a + b in the rectangle 0, 0, l, r. This line is getting the value of function f in rectangle l, l, r, r, which is rectangle(0, 0, r, r) -rectangle(0, 0, l-1, r) -rectangle(0, 0, r, l-1) + rectangle(0, 0, l-1, l-1)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      @DimmyT I got it thankyou..Takes a time but now understand completely..thankyou :)

»
5 years ago, # |
Rev. 8   Vote: I like it +8 Vote: I do not like it

Problem E is quite interesting; I did manage to figure out the DP logic but I didn't know how to calculate the sum for the squares near the goal... however there is a kick-yourself-simple solution I found once I coded it according to the editorial.

$$$dp_i$$$ for $$$94 \leq i \leq 99$$$ is... always exactly $$$6$$$. Why? Because consider: you have a $$$p = \frac16$$$ chance of rolling the right number to reach the goal exactly, and the expected number of turns require to hit it is the mean of its geometric distribution, $$$\frac1p = 6$$$. But if you roll a lesser number, your new square still only has a $$$\frac16$$$ chance of getting the right number, so though you're closer to the goal physically, you're still no closer in terms of the turns required to roll the right number, so you might as well not have moved at all.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got your point, moving not at all and moving some pieces ahead has no difference as it won't affect the number of expected turns, So it's always 6 for that region. Nice observation.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain A?I didn't understand the solution.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I venture most people just solved A by staring at it for a while and conjecturing the correct solution. Actually proving it is somewhat harder.

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    OK, here's a perhaps simpler "proof" based on the images in my head when I solved this problem.

    Assume WLOG $$$a < b$$$. Consider the sequence $$$an \mod b$$$ for integers $$$n$$$ incrementing from $$$0$$$. If and only if $$$\gcd(a, b) = 1$$$, it will eventually cover the entire ring of integers $$$\mod b$$$ (forming a discrete Weyl sequence), which is equivalent to the cells colored white as you consider chunks of length $$$b$$$ moving to the right, thereby limiting the black cells to a finite number.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Even I don't know how works my ac code of 1245A. But how i got ac !!! :o

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me in problem D? Here is my code: Code

I've used Kruskal using DSU to solve this problem by sorting all the edges by weights and then merging the nodes if the cost of wire to connect them is less than the maximum of their cost of building powerhouses(because on making connection, there will be one powerhouse needed which should be minimum of both).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the proof of problem A in an easy way?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if we can reproduce number with any remainder of division by one number using another number, then answer is Finite, otherwise answer is Infinite. This can be checked using GCD (if GCD of two numbers is 1, then answer is Finite, otherwise Infinite).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solutions to some of the problems: B: 64089807, C: 64086504, D: 64086519, E: 64086541.

»
5 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

C can be solved by normal PnC too.My solution

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we have to necessarily connect a city in a group to it's parent? Or we can connect it to any city in the group which will give us the minimum connection cost(basically which has electricity but not a power station necessarily)?

PS: Parent of a group is the one with a power station

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The latter is the case.

    UPD : My code is giving me WA on Test case 13. Could someone please help me with it? I've tried a lot. But couldn't debug it.

    My code

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think TC 13 means: You were asked to make all of cities have electricity, and to do it, you don't need all cities connected each other, you only need each city to belong to 1 connected component which has at least 1 city containing power state. To simplify problem, you add a dummy city and make all components connect each other. Now you only need to find the MST of $$$n+1$$$ city (including dummy city).

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The statement only says,

    You must provide electricity to all cities ( either by making a power station there, or connecting it to "some" other city that already has electricity ).

    And the second part basically says, that electricity is transitive, i.e. if City $$$A$$$ has a power station and City $$$B$$$ is connected to it, then $$$B$$$ also has electricity, and thus, if you connect City $$$C$$$ with $$$B$$$, then $$$C$$$ also has electricity.

    Also, about your code. It seems you are using a greedy strategy, by making the cheapest power stations, but that is not correct. There could be a possibility to make a costlier power station that supplies all cities, instead of making cheap power stations in each city. ( Read my short explanation here ).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain to me, what does 'rt' and 'sz' mean in your code? And what exactly does 'connect' function does!

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        It's just DSU ( Disjoint Set Union ). Read about it online.

        This is a good resource.

        UPDATE: Also, I think I didn't explain it clearly, so, we use DSU as part of Kruskal's algorithm for finding a MST ( Minimum spanning tree ) for a graph.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is tagged with trees.Can any one explain this problem according to trees algorithms.And thanx in advance.Happy coding.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be solved using MST (Minimum Spanning Tree) like this. You can use either Prim or Kruskal algorithm. But in this problem, Prim is better.

    You can learn more about this in Wikipeia. (Poor Chinese, we can't link to the Wiki page!)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know if it is right for you to say that f(2l,2r) = 3*f(l,r). Suppose we are looking at the interval 2,5. Your argument implies that, when counting f(4,10), we must consider the case where we chose for the first one's less significant bit number 0, and, for the second one's less significant bit, number 1, and the other ones we chose, for instance, 10 and 101, respectively (that are pairs found in f(2,5) ). But that does not give the answer. In fact, f(2,5) = 6 and f(4,10) = 16.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good editorial!

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello guys!

I was wondering if I could get some help on problem D. I can't seem to find a corner case or prove why my solution is wrong. My solution follows this idea that was already mentioned in the comments by anakib1 in the Announcement page.

"I had following idea to D. Lets make minimum spanning tree of graph with edges c(i,j)=(ki+kj)∗d(i,j) for all i,j. Firstly lets add the cheapest plant. Then sort edges in non-increasing order and we will try to delete every edge. If we are considering edge (x,y) let c1 will be component with vert x of tree without edge (x,y) and c2 will be component with vert y of tree without edge (x,y). Only one of this components has installed plant now. Let it be c2 . Then find cost of the cheapest plant in c2 and check if its better to add plant instead of edge from spanning tree. If its better to add plant, we delete edge (x,y) and add plant."

I did get to test 32, but can't analyze the test case since its quite large (N = 2000). I would really appreciate if anyone can help me find my mistake. I've added comments in the my submission, hope it helps. Thanks! 64906030

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hello.

    Here is the generator used for test 32: https://dpaste.de/hSQn

    To generate test 32, compile it (you'll need the testlib.h file), and run with command-line arguments 21 2000 100. So for example, if I would do it on my Linux machine, after compiling using g++ file.cpp, I would type ./a.out 21 2000 100 > in and then the testcase would be saved in file in. Hope this helps.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the quick reply! I will check this out!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, can somebody point out what's wrong in my approach

  1. first iterate over all cities one by one

  2. for each city i , find the minimum of all costs to connect this city j ( 1 <= j <= n) let's call it min_cost

  3. now we have two scenario either this city i has its own power house or is connected to some other city which will have a power house

  4. just compare C[i] with min_cost

    a. if(C[i] < min_cost) , we can simply have a individual plant for this city
    
     b. otherwise we connect this to city j, which gave us min_cost
  5. now we have a graph with

  6. simply iterate over all connected components

  7. for each component find the minimum C[i] and add it to final cost answer, since we are planting a power plant at this i'th city

  8. rest of this connected component let's just find the MST and add this to final answer , since all the other cities would be connected to some other city with wires having power connection

  9. repeat 7

My Submission

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah this logic is incorrect because i might miss some of the edges which could help reduce the overall cost see this example copied from above cmt

    5

    5 15

    19 13

    19 13

    24 14

    20 13

    2 10 20 10 2

    6 4 2 4 5

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

D was asked in google interview lol

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

why it is getting tle

void _segfault_()
{
    ll n; cin >> n;
    vector<pair<ll, ll>>vec(n); cin >> vec;
    vector<ll>a(n), b(n); cin >> a >> b;
    vector<pair<pair<ll, ll>, pair<ll, ll>>>aa;
    vector<vector<ll>>adj(n + 1);
    for (ll i = 0; i < n; i++) {
        aa.pb({{a[i], i}, {vec[i].ff, vec[i].ss}});
    }
    sort(all(aa));
    for (ll i = 0; i < n; i++) {
        for (ll j = i + 1; j < n; j++) {
            adj[i].pb(j);
            adj[j].pb(i);
        }
    }
    ll ans = aa[0].ff.ff;
    vector<ll>temp;
    vector<pair<ll, ll>>temp2;
    temp.pb(aa[0].ff.ss + 1);
    for (ll i = 1; i < n; i++) {
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>pq;
        vector<ll>dis(n + 1, LLONG_MAX / 2);
        for (ll j = 0; j < i; j++) {
            pq.push({0, j});
            dis[j] = 0;
        }
        vector<ll>par(n + 1, -1);
        while (!pq.empty()) {
            pair<ll, ll>p = pq.top();
            pq.pop();
            for (auto child : adj[p.ss]) {
                if (dis[child] > dis[p.ss] + (abs(aa[p.ss].ss.ss - aa[child].ss.ss) + abs(aa[p.ss].ss.ff - aa[child].ss.ff)) * (b[aa[p.ss].ff.ss] + b[aa[child].ff.ss])) {
                    dis[child] = dis[p.ss] + (abs(aa[p.ss].ss.ss - aa[child].ss.ss) + abs(aa[p.ss].ss.ff - aa[child].ss.ff)) * (b[aa[p.ss].ff.ss] + b[aa[child].ff.ss]);
                    par[child] = p.ss;
                    pq.push({dis[child], child});
                }
            }
        }
        ans += min(dis[i], aa[i].ff.ff);
        if (aa[i].ff.ff <= dis[i]) {
            temp.pb(aa[i].ff.ss + 1);
        }
        else {
            temp2.pb({aa[par[i]].ss.ff + 1, aa[i].ff.ss + 1});
        }
    }
    cout << ans << endl;
    cout << temp.size() << endl;
    cout << temp << endl;
    cout << temp2.size() << endl;
    for (auto it : temp2) {
        cout << it.ff << " " << it.ss << endl;
    }
}

for each node i have two choices whether to setup station or connect to any existing station so i am using multisource dijikstra to find min cost required to connect it station .

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I have a weird approach for D, but I can not proof it myself. Hope somebody has the same idea give some proof. Basically, I just "greedy" delete edges of MST. Suppose we have built our MST successfully with n — 1 edges. We will ask "what kind of edges we can remove from the MST by adding power station to reduce the total cost" or we need to choose edges to remove and vertices to build power station so that all connected components connect to at least 1 power station.

The observation: with n — 1 edges chosen it will form a tree, if we remove any edge, the tree will be separated into two components. Greedily, we want to remove the largest edge of the MST. Suppose the largest edge E connect two nodes u, v. We claim that, we can remove this edge if after removing the cost to make "all connected components connect to at least 1 power station" better. If we remove E, we need to make sure two trees in two sides with u and v are root connected, then we DFS from u and v to find two smallest power stations X and Y in two sides (there will be a case when a side is already connected with power station then the cost for that side is 0). And we will remove E if X + Y < weight E + min(X,Y) (the least cost after removing is smaller than least cost before removing then we remove). This expression can be expressed as max(X,Y) < weight E.

Submission: 289959387