keima915's blog

By keima915, history, 2 weeks 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
 
 
 
 
  • Vote: I like it
  • +188
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
2 weeks 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

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

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

orz keima915

Please, don't stop creating CF rounds!!

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

    Sorry, what is orz mean?

    • »
      »
      »
      2 weeks 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.

    • »
      »
      »
      2 weeks 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".

»
2 weeks 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!

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for so fast editorial! :)

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I solved A without knowing proof. =)))

»
2 weeks 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!

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Fastest Tutorial ! Cool !

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

I just hope there are 2:15 minutes

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it
»
2 weeks 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...

»
2 weeks 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?

  • »
    »
    2 weeks 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.

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

      This result is so beautiful. Thanks.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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).

  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

keima915 Thanks for the amazing round.

»
2 weeks 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.

  • »
    »
    2 weeks 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 ).

    • »
      »
      »
      2 weeks 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$$$

  • »
    »
    2 weeks 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$$$).

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What was wrong in the logic of your code. Could you please elaborate

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We were picking the cities with min cost, then comparing its cost with cost if it was connected with any of the taken cities. This fails since like in the above test case.
        order of the cities acc. to thier cost would be
        3 4 5 2 6 1
        so we picked 3, then 4. connected it to 3. But here it would have been better to instead pick 5, connect 3 and 5 and then connect 4 to 5.

»
2 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

In problem B: My output matches with jury's output..still i'm getting wrong answer verdict on pretest 4..how??

Verdict: WRONG_ANSWER

Input 100 100 5 91 4 PPSRSRSSSRSSSRSSSSSRSPSRPPRSPSSRSRRPPSPPPPRSSPPPPRSRSRSSPRPRRPSSPSSRSPRPSPRRSPRPRPRSRSRPPSPSRSRPPSRS 100 61 30 9 RRSRRSRSPSRSRPPRRRPPPPSPRRPSSSRPPPRPRRPPPSSRRPSPPPSRRPPPPSPPSRRSRPRSSPPRSPRSSRSPPPRPRSSPRRPPPSSRRSSP 100 81 1 18 PSSSSSRRPRPPRSSRSRRRPRPRSRSPRSSRPSRRRSPSRSRRRPRPRRPRPPPSPSSPSSSRPSRPPPRSPPPPSSSSPSRSSPPSSPPRRRSRSRRS 100 30 38 32 SSRRPSPPRPRRPPRRSSRPRPRSSRRSRPSRSPSSRSSSPRRRPRRSPSRPPSRPRSPRRSPRPSRRPSPSRPRSPRRSRSRRPSSPRPPRPPRPRSPR 100 15 45 40 SSSRSPSPSPPRPPPRRPSRRPRSPPR...

Participant's output NO YES PPRPPRPRSRPRPSSPPPSSSSRSPPSRRRPRRRPRPPRRRRRPPRRRRRRPPRRRRRRRRPPRPRPRRRRPRRPRRPRRRRPRPRRRPRRRRRRRRRRR YES SRRRRRPRSRSSRRRRRRRRSRSRRRRSRRRRSRRRRRSRRRRRRSRSRRSRSSSRSRRSRRRRSRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR YES RRPPSRSSPSPPSSPPRRPSPSPRRPPRPSRPRSRRPRRRSPPPSPPRSRPSSRPSPRSPPRSPSRPPSRSRPSPRSPPRPRPPSRRSPSSPSSPSRRSS YES RRRPRSRSRSSPSSSPPSRPPSPRSSPRPRSSRRRRPPPPPRPPPSPPSSPPSPPPSPPPPPPPPSPPPPPSSSSSSSSSSSPPSPPSSPPSSSSSPSSP YES SSRSRSSRRSRRRPSRRRRRRRSSSSSRSRSSRSSSSSSSSRSSSRSSSSRRRSSSSSSRSSSRSRSSRRRSSR...

Jury's answer NO YES PPRPPRPRSRPRPSSPPPSSSSRSPPSRRRPRRRPRPPRRRRRPPRRRRRRPPRRRRRRRRPPRPRPRRRRPRRPRRPRRRRPRPRRRPRRRRRRRRRRR YES SRRRRRPRSRSSRRRRRRRRSRSRRRRSRRRRSRRRRRSRRRRRRSRSRRSRSSSRSRRSRRRRSRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR YES RRPPSRSSPSPPSSPPRRPSPSPRRPPRPSRPRSRRPRRRSPPPSPPRSRPSSRPSPRSPPRSPSRPPSRSRPSPRSPPRPRPPSRRSPSSPSSPSRRSS YES RRRPRSRSRSSPSSSPPSRPPSPRSSPRPRSSRRRRPPPPPRPPPSPPSSPPSPPPSPPPPPPPPSPPPPPSSSSSSSSSSSPPSPPSSPPSSSSSPSSP YES SSRSRSSRRSRRRPSRRRRRRRSSSSSRSRSSRSSSSSSSSRSSSRSSSSRRRSSSSSSRSSSRSRSSRRRSSR...

Checker comment wrong answer The number of throws of each kind doesn't match (a, b, c) resrictions

»
2 weeks 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)}

  • »
    »
    2 weeks 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])

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are saying the same thing, your way of understanding it is a bit different than mine

»
2 weeks 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?

»
2 weeks 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.

  • »
    »
    2 weeks 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$$$

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

      Thanks for your answer.

      That is strange,because when i do it in my pc it says SSSRRRRSSR and it's correct answer

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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$$$.

        • »
          »
          »
          »
          »
          2 weeks 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

»
2 weeks 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.com/contest/1245/submission/64019871)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to understand the editorial for problem F.

»
2 weeks 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.com/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

»
2 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    • »
      »
      »
      2 weeks 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.

»
2 weeks 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.

  • »
    »
    7 days 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

»
2 weeks 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) ?

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

    Ahh yes, thanks for pointing it out. It has been updated now.

»
2 weeks 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

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

For problem C , how it is reduced to fibonacci ?

  • »
    »
    2 weeks 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

»
2 weeks 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

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

    It is correct approach and gives AC.

    Link to submission:-

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D using greedy idea given in editorial. Just different implementation using priority queue

https://codeforces.com/contest/1245/submission/64051184

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what the DP transition for problem C would be if 'nn' and 'uu', instead of being replaced by one letter each, 'm' and 'w', could be replaced by more. Say 'nn' could be either 'm' or 'l'.

»
2 weeks 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

  • »
    »
    2 weeks 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).

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

Thank you for the beautiful contest, keima915 !

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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks 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

  • »
    »
    2 weeks ago, # ^ |
      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 $$$35 - i$$$ leftmost bits are same as that of $$$x$$$ or not. $$$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

»
2 weeks 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?

  • »
    »
    2 weeks 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.

»
2 weeks 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).

»
2 weeks 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

  • »
    »
    2 weeks 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?

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks 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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I see now. all I had to do was dp[i] = ( dp[i-1]+dp[i-2])% mod and it works. Jeeez... my bad. Thanks a lot :)

»
2 weeks 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.com/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.

  • »
    »
    2 weeks 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)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could please explain little better .I am not able to understand what are you talking about the rectangle thing...

    • »
      »
      »
      2 weeks 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 :)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anyone who can explain in a better way ..Please thankyou

»
2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the Editorial

»
2 weeks 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).

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Arpa's soluion for Problem C:

»
2 weeks 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?

  • »
    »
    2 weeks 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).

»
2 weeks 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.

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

C can be solved by normal PnC too.My solution

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

I am not able to understand the Question F tutorial form the below points: Somebody help me with this. Thanks in advance.

What if l and r are not both even? Define a function g as follows: let x and n be non-negative integers, then g(x,n) should be the number of integers y such that the following conditions are satisfied:

0≤y<n

x+y=x⊕y

Then, if l is odd, f(l+1,r)=f(l,r)−2⋅(g(l,r)−g(l,l)), or f(l,r)=f(l+1,r)+2⋅(g(l,r)−g(l,l)). Similarly, if r is odd, f(l,r−1)=f(l,r)−2⋅(g(r−1,r)−g(r−1,l), or f(l,r)=f(l,r−1)+2⋅(g(r−1,r)−g(r−1,l)).

Now all that remains is to implement g efficiently. Define a function LSB as follows: let n be a positive integer, then LSB(n) should be the least significant 1-bit of n. Next, define a function has follows: let x and n be positive integers, then h(x,n) should be the number of integers y

such that the following conditions are satisfied:

n−LSB(n)≤y<n

x+y=x⊕y

Then, g(x,n)=h(x,n)+g(x,n−LSB(n)) if n>0 and g(x,n)=0 otherwise. Moreover, it is easy to implement h so that its time complexity is logarithmic with respect to n.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does this "Arpa" stand for in the solution of seco

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

wrong answer The number of throws of each kind doesn't match (a, b, c) resrictions. In problem B,what is this error. My output is same as jury's output.

»
2 weeks 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

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks 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).

  • »
    »
    2 weeks 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 ).

    • »
      »
      »
      2 weeks 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!

      • »
        »
        »
        »
        2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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!)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @iyym could you please explain me this line in your solution question f . calc(b,b)-calc(a-1,b)-calc(b,a-1)+calc(a-1,a-1)). Thankyou

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain solution to problem A in detail.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I got the logic of B but I am getting WA.What am I doing wrong?? My code link

»
12 days 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.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody please explain the function 'f' in the editorial solution of "Daniel and Spring cleaning" problem?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good editorial!

»
3 days 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

  • »
    »
    3 days 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.

    • »
      »
      »
      47 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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