lewin's blog

By lewin, 2 months ago, In English,

Here's the editorial. Hope you have a happy new year!

Code can be found here: https://www.dropbox.com/sh/i9cxj44tvv5pqvn/AACQs7LLNyTZT-Gt_AMf7UQFa?dl=0

New Year and Counting Cards
New Year and Buggy Bot
New Year and Curling
New Year and Arbitrary Arrangement
New Year and Entity Enumeration
New Year and Rainbow Roads
New Year and Original Order
New Year and Boolean Bridges
Tutorial of Good Bye 2017
 
 
 
 
  • Vote: I like it  
  • +336
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it +60 Vote: I do not like it

kudos to a lightening fast editorial!

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

Is there any way to interpret E as a vector space or group or something like that?

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

    If I'm not mistaken, E should be related to counting the number of topologies on {1, 2, ..., m} in which the given family of n sets is open.

    (Not topologies but sigma algebras — lapsus calami)

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

      It is not a requirement in topological spaces that the complement of an open set is also open (In fact, in spaces like R^n, the complement of an open set is a closed set, and only R^n and the empty set are both open and closed sets). So in this problem, what is asked is exactly to count the number of topological spaces on , such that the complement of any open set is also an open set.

      Such spaces happen to also be linear subspaces of , since it is easy to write xor using only and, or and not. This observation might or might not help in arriving at the key observation on partitions (it is equivalent to observing than, when performing a careful Gaussian elimination, one can achieve a triangular matrix that has exactly one "1" per column).

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

        Continuing with this completely unnecessary abstract translation, the key observation regarding partitions is equivalent to the fact that the Kolmogorov quotient of our space has the discrete topology (Kolmogorov quotient "glues" indistinguishable elements into one new single element).

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

      I think the term you are looking for is "Sigma Algebra".

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

        Indeed! Nice catch. So the key observation can also be stated as "finite sigma algebras are essentially equivalent to partitions". Googling that right now shows a related question here: https://math.stackexchange.com/questions/143796/number-of-sigma-algebra-on-the-finite-set

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

          Which is how I solved it :D

          Well, I would have probably figured it out on my own if I had thought about it for a minute or two, but it was too tempting to just google "Number of sigma algebras on a finite set".

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

        In fact (to be even more pedantic :D) you don't need the "sigma" part, which refers to countable unions.

        Since everything is finite it is just an algebra of sets.

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

          For anyone delighted with the present display of pedantry, a friend of mine just made me notice that finite topologies are equivalent to preorders (a point x is less than another y, if any open set containing y also contains x), which are also essentially just "transitive" directed graphs.

          So in the finite case:

          Sigma algebra --> partitions

          Topology --> preorder

»
2 months ago, # |
  Vote: I like it +53 Vote: I do not like it

maths too hard~~

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

Codeforces is becoming awesome day by day :D

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

Editorial even before system testing finished, amazing punctuality grandmaster.

»
2 months ago, # |
  Vote: I like it +64 Vote: I do not like it

My solution to H is probably equivalent to yours, but it's explained in much simpler terms than Walsh-Hadamard transform :)

See "4.2 Inclusion-exclusion" in http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf

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

    Nice solution. I noticed my solution looked like inclusion/exclusion but didn't know how to explain it. I found it easier to explain through walsh hadamard transform since that's how I originally thought of the problem/solution. Glad to know there is a simpler explanation :)

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

      I actually admire that your knowledge enables you to use Walsh-Hadamard transform in a solution so easily :) I had to Google the paper to make progress.

      Thanks a lot for the contest!

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

    The O(nk·2.45n) algorithm (dynamic programming, only iterating over maximal independent subsets) also passes in less than 1 second.

    Unfortunately, too many bugs :(

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

      We can also all borrow a trick from dotorya:

      	while (clock() - st <= CLOCKS_PER_SEC * 4.5) {
      		random_shuffle(u, u + X);
      		int mx = 0;
      		for (i = 0; i < X; i++) col[i] = 0;
      		for (i = 0; i < X; i++) {
      			int t = u[i];
      			for (j = 1; j <= X; j++) tchk[j] = false;
      			for (j = 0; j < X; j++) if (conn2[t][j]) tchk[col[j]] = true;
      			for (j = 1;; j++) if (!tchk[j]) break;
      			col[t] = j;
      			mx = max(mx, j);
      		}
      		mn = min(mn, mx);
      	}
      
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        That should probably fail on a chain of length 23, though?... Or does it have so many attempts that it passes that one as well?

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

          For a chain of length 23, I think the expected round is at most .

          I have no time left and implemented a similar solution.

          And I passed all the system testcases with only 100 iterations and 15ms :)

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

            At least for a bipartite graph, this solution should work in O(2n).

            Take one valid coloring, and suppose that there are B black vertices and W white vertices. If dotorya chooses a permutation such that all black vertices come before all white vertices (and vice versa), it works correctly. This happens with probability .

            Is this O(2n) for general graphs or not?

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

              What about complement of complete tripartite graph (so? Growth rate of is around O(33n).

              UPD: I misunderstood algorithm, sorry for many updates.

              However, it seems like it might be more difficult to bound this runtime.

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

                Doesn't it always handle complete tripartite graphs correctly?

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

              What do you think about the graph on n vertices where vertex i is connected to vertices in interval [i - k, i + k] with chromatic number k + 1?

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

          Actually I didn't compute probability at all. I just wrote general time-cutting method and prayed this would pass. Sorry :( After the conteat, I thought that the worst case is a chain with 23 vertices, which makes 10^-6 probability, which can pass this within time limit. But I was not sure whether this is the worst case...

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

            There's nothing to be sorry about, I meant it when I said we should borrow a trick from you — you got the problem accepted quicker, and that is good!

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

    I imagine that the number of k-colourings can get quite big though (n! for a complete graph, and I'm not sure if that's the worst case). I see you used a randomly selected prime modulus to get a solution that is right with high probability (and which is hack-resistant), but would a solution that's guaranteed correct (presumably using bignums) run fast enough?

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

      Well, the probability of error is at most 23*1e-9, so I would say that there's not much difference — i.e., in my mind it's like quicksort working in O(nlogn).

      But I don't know a deterministic fast enough version of my solution.

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

        I managed to add an extra O(logk) factor, and I had to use modulo 232 hash to fit into TL. Luckily it passes.

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

Really nice problems! I kept thinking about how to handle the infinitely large case in D, but couldn't figure it out at last :( And also, F is a really cool problem I think :D

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

WOW! Thank you so much for super fast Editorial and also for the awesome problems !

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

Whoohh such a fast editorial!!!!!!!!

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

F was a Div2C question. I wonder why the authors kept it at F :(

»
2 months ago, # |
Rev. 2   Vote: I like it -90 Vote: I do not like it
What's wrong with my code for problem B?
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	string s="lrud";
	int n,m;
	cin>>n>>m;
	char a[n][m];
	int x,y,p,q;
	for(int i=0;i<n;i++)
	{
		scanf("%s",&a[i]);
	}

	string c;
	cin>>c;
	sort(s.begin(),s.end());
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			
			if(a[i][j]=='S')
			{
				y=i;
				x=j;
			}
			else if(a[i][j]=='E')
			{
				q=i;
				p=j;
			}
		}
	}
	int ans,count=0;
	char ch;
	int k;
	int stx=x;
	int sty=y;
	do
	{
		ans=0;
		x=stx;
		y=sty;
		for(int i=0;i<c.length();i++)
		{
			ch=s[c[i]-'0'];
			k=0;
			if(ch=='l' && x>0 && a[x-1][y]!='#')
				{
					x--;				
					k=1;
				}
			if(ch=='r' && x<m-1 && a[x+1][y]!='#')
				{
					x++;					
					k=1;
				}
			if(ch=='u' && y>0 && a[x][y-1]!='#')
				{
					y--;					
					k=1;
				}
			if(ch=='d' && y<n-1 && a[x][y+1]!='#')
				{
					y++;
					k=1;
				}

			if(k==0)
				break;	
			if(x==p && y==q)
			{
				ans=1;
				break;
			}
		}
		if(ans)
			count++;
	}while(next_permutation(s.begin(),s.end()));

	printf("%d",count);
	return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please help in understanding the dp transition in D.

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

goodbye rating

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

    dude you solved 4 question on one go. you shouldn't be saying this :P

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

      but the problem D had cost most of my time during the contest. :( Anyway the problems are good, yet I'm foolish.

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

Problems blew my mind, great contest-great problems.

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

For C, do we need to compute dy for all discs that can possibly touch (i.e. all discs in the ≤ 2r range), or can we just compute it for the disc with the highest y coordinate of these?

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

    You want to find the highest y+dy overall, not the highest y (and then + the dy of that).

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

      My question is:

      Suppose a disc X is within the +/- 2r range. That means, if the disc currently being processed keeps dropping, it will eventually touch this disc X, unless it first touches some disc Z.

      The question is whether we can conclude such disc Z must have a higher Y coordinate than disc X.

      I.E. for N discs in the range, the dropping disc must touch the one with the highest Y coordinate.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        No, that's not true in general. You can try this case for example:

        5 1
        2 1 4 4 2
        

        For the last disk, the highest y-coordinate disk wihtin range is the fourth one, but it will touch the second disk first.

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

        No, that's false. if the highest-y disc is far away, and an almost-as-high-y disc is very close, it can touch the almost-as-high disc before the highest disc.

        For concreteness, consider R=2, discs at (0, 2), (2, 1), and a new disc dropping at x=2. Then it will touch the (2,1) disc first.

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

      That is where I fell :( I found the highest y colliding with a circle and then found the dy of that. :/

      Great question btw!

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Light-speed Tutorial,Light-speed System Test! I like it!

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Editorial before Final testing. So fast. (y)

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

Editorials before system testing. That's a perfect goodbye to 2017 (*-*)

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Great problems and a fast, nice, and concise editorial. Great Job!

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

There is a slight formatting error with the bell number link. (Extra right bracket at the end)

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

Thanks for good contest!

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

In Problem D Can somebody please explain why infinite length sequence is not necessary for "exact answer" ?

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

    Didn't solve it, but I'm guessing it's because you can find the expected value of the amount of trials until first success with a closed form formula: https://www.cut-the-knot.org/Probability/LengthToFirstSuccess.shtml

    Just 1/p.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    At some point adding only one 'b' will satisfy the condition k. The probability of adding n 'a's then one 'b' at this point is: (1 - p)n × p where p is the probability of putting a 'b' (e.g: ).

    Hence the expected value of the sequence's length is: which is finite.

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

      I know i am wrong,but i don't know why

      why cant i say that

      E = (1 — p)(E + 1) + p

      because it has probability p of ending here,taking one step,or it has 1 — p of continuing,which takes one extra step

      then

      E = E(1 — p) + 1 — p + p

      E * p = 1

      E = 1 / p LE:this would give me the average number of steps untill i stop,but i should subtract 1 from it because i am interested in the average numbers of ab,not the avreage length. So 1/p — 1 = (1-p) / p

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

        This is correct!!

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          yeah but i didn't realise for a long time that i need to subtract 1 :))).

          But yeah,now it's corect :))

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

        can you please help me in understanding the solution. I didn't understand : "because it has probability p of ending here,taking one step,or it has 1 — p of continuing,which takes one extra step" please elaborate it a little and if possible please explain it with an example.

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

          So lets say 2 events could happen:

          -a succes with probability of p

          -a failure with probabilty of 1 — p we are at the first step,and we ant to see the expected number of steps untill the first succes

          well if you have a succes(with probability p),then you only take one step. so E = p * 1 + the other case

          if you have a failure(with probability 1 — p),then imagine that the next step is exactly like step 1,so the expected from that point would be the same. But,because you already had a failure,you must add one to it.

          so E = p * 1 + (1 — p) * (E + 1)

          if you do a bit of math this means

          E = 1 / p

          Now,back to our original problem,this is the expected length of a string untill we put a b.this would give us length — 1 more ab's.

          So the real expected value is E — 1 = (1 / p) — 1 = (1 — p) / p

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

      I wonder how to prove this formula..

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

      Why we need to use DP if the answer to the problem is (1-p)/p? I can not understand it at all.

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

        The condition for applying the formula is when adding only one ‘b’ is enough to satisfy the condition ‘k’. This means that we have constructed a prefix of ‘a’s and ‘b’s, and that appending one ‘b’ to our prefix is enough to satisfy our condition.

        To construct that prefix we use DP. The formula is applied when we hit a base case.

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

For problem D, I managed to get the formula but then I did not know how to make sure P and Q to be coprime. It turned out that I did not have to do anything and it would still pass. Can someone explain to me please why. (I used the same formula in the editorial)

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

    Say you have integers p = p'g and q = q'g where g = gcd(p, q).

    Then pq - 1 = p'g(q'g) - 1 = p'gg - 1q' - 1 = p'q' - 1.

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

What is wrong with my approach to problem C ? Approach — for any circle- check all the points in the range c-r to c+r (c is center). find which previous circle(if any) in that range has the largest height. so it will touch that circle. then find the height as per the formula in the editorial. and update the range with the new circle.

My solution link http://codeforces.com/contest/908/submission/33786083

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

    I haven't seen ur code but you have to check from c-r-r to c+r+r

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

      why is it? range of the outermost points of the circle colliding should be [c-r,c+r] right?

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

        The center of the circle it collides with is another r distance away

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

          I mark the range of each circle, so it will encounter the circle whose center is r distance away from its circumference. The reason I got wa was the thing that bmerry explained below.

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

    I think you made a mistake that I hacked a few other solutions on too: you've assumed that the disk you hit first will be the one that stopped with greatest y, but that's not necessarily true if there is one with a slightly lower y but much closer x.

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

      yes, that might be the case. I should have taken the max over all. :( Thanks.

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

Will there be an editorial in Russian?

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

It should be noted for problem F that, if there are no green points, you do not have to connect the red points and the blue points. In every other case, the optimal solution must involve connecting all points to each other, but, in this case, none of the red points have to be connected to the blue points. The problem may be a little misleading in this regard, as it says that Roy and Biv want all the points to be connected; however, later on, it does specify that they only want all the points they can see to be connected.

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

In H, I've picked random number and calculated result modulo this number, hopeing, that when number of colorings will be greater than zero, then it will also after moduling be greater than zero. Can you prove, that we don't have to use any modulo (so use 2^64), and it'll still be ok?

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

Thanks for the contest :) was really fun ^^ and thank you for the fast editorial! srsly.

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

    And wow kudos for the solution in multiple language!!

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

what is wrong in my solution for problem C the link is here.

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

Editorial has appear faster than ratings. Hm....

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I can't get D solution. Could somebody explain the solution with more detail?

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

What is wrong with this solution for Problem C http://codeforces.com/contest/908/submission/33779874 . It is giving WA for Test Case 7.

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

Why is the formula for D not dp[i][j] = (pa * dp[i  minus  1][j] + pb * dp[i][i  minus j]) / (pa + pb) ?

As in to reach current state with i a's we can only arrive here from having i-1 a's

and to reach current state having j ab subsequences we can add b to prefix with i-j a's and get a prefix with j ab's

Thanks :)

EDIT(for those who clicked pluses): Okay, so it seems we are working backwards, because our base cases are when j >= k, it means that at (i,j) we are ending our algorithm, so expected value of 'ab' subsequences is j.

Because of that our answer should be dp[0][0]

we also have the i + j >= k condition, to ensure that a's in our prefix doesn't exceed b's so that out count of a's are bounded by k.

Therefore our answer is dp[1][0], because there has to be atleast one 'a' to form some amount of 'ab' subsequences

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

    Thank you your comment helped to understand the way the editorial thinks.

    The key is that you start the algorithm from a fixed state and it only matters the amount of a's and ab's sub-sequences to compute the expected ab's when the algorithm finishes

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

dotorya solved G at 00:49:58 before bmerry

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

    Oops, thanks for catching this.

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

Didn't understand some moments in explanation of problem F. Firstly, outer points = the leftmost and the rightmost points on the line ? Assuming that let's consider the first case: the outer green points are not directly connected, in which case, we must connect all the red/blue points in the line. Okay, look at the test:

1 G
3 B
5 G
7 B
9 G

Firstly, doing the second observation I should connect 3 — 5 and 5 — 7. Okay, what's next? I guess I should connect 7 — 9 and 1 — 3 ? Just can't see something like that in editorial. Secondly, let's consider the second case: the outer green points are directly connected, in which case, we can omit the heaviest red and blue segment. Word "directly" seems very strange to me there. I really can't imagine that case not counting variant when we have only two adjacent green points. For example:

1 G
3 G
5 G

Are x = 1 and x = 5 points directly connected if they linked through the point with x = 3 ? Need more detailed explanation, please.

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

    I think you may be misinterpreting what the observations give you. The main point is that there can be no edge that "skips" a green point, thus, we can split the problem into sections which are each independent so that we only need to solve the case where the only green points could be first and last points.

    For the second case, I should have clarified that a "red" edge is an edge that connects (red/green) to (red/green), and a "blue" edge is an edge that connects (blue/green) to (blue/green).

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

In D why "The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored. To fix this, we can adjust our answer to be dp[1][0]."

Why just ignore it? Why doesn't it change the answer?

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

    Those b's can't be part of any subsequence that forms 'ab', since there's no 'a' before them, and we're only interested in expected amount of times 'ab' occurs.

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

      So what happens with sequences like "bab.." or "bbbaab.."? Don't we count them in the answer?

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

        The reasoning is this way. With no loss of generality every case we run the algorithm start with a finite amount of b's and then an a. In all the cases so we finish with 1 a and 0 ab's, thus, by definition the answer is dp[1][0].

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

In problem D, I didn't understand the meaning of this statement.
You stop once there are at least k subsequences that form 'ab'.
We can have infinite bs then an ab, can this be the case?
Please help me understand the problem.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored.

Shouldn't we multiply by 1 + p + p2 + .. where p = pb / (pa + pb) instead of ignoring?

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

    dp[i][j] = (pa * dp[i + 1][j] + pb * dp[i][i + j]) / (pa + pb)
    When i = j = 0, dp[0][0] = (pa * dp[1][0] + pb * dp[0][ 0]) / (pa + pb)
    bring pb/(pa+pb) to the left and it becomes (1-pb)/(pa+pb) = pa/(pa+pb) which cancels on both sides, so we get
    dp[0][0] = dp[1][0]

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

      Ah, or continuing from what I said, the answer is (1 + p + p2 + ...) * pa / (pa + pb) * dp[1][0] = dp[1][0]. In either your derivation or what I wrote above, the initial 'b's cannot be "ignored", they simply cancel out with the leading a. Is there any intuitive explanation of this fact, or is lewin's editorial misleading in using the word "ignored"?

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

        The number of 'ab' subsequences in a string s is the same as if there was an extra 'b' in the beginning of s (or two b's, three, etc).

        Maybe it gets intuitive if you think that the distribution is constant for every "pattern" (I mean, s, s and an extra 'b', two extra b's, etc), and the expected value of a constant distribution is the value of the constant. It's like you could just get the value for s rather than the "average" of all these cases, since all their values are equal.

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

      Logically, (pa+pb)/pa * dp[0][0] is the answer. Which is also equivalent to dp[1][0] by calculation. But how are they equivalent intuitively?

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

When will the ratings be updated ?

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

In solution code of D- why have you kept

if (ab >= k)

? if we already have this check -

if (a + ab >= k)

? First one will never be encountered.

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

    Keep this if (ab >= k) condition above second one so that it is checked earlier

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

      But its useless. if you have ab>=k then a+ab>=k is already satisfied. so it never executes.

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

Problem G can be solved in O(102n).

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

    Well what do one and cnt mean in your code? Would you please explain it a little bit? Thanks a lot.

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

      For fixed d, we would like to add o(x) = 111...1 (x's ones) to the answer if the number contains x digits not less than d.

      To maintain when we find a new digits not less than d, .

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

My approach to F(New Year and Rainbow Roads) is to connect all green points where the cost = (last green - first green). And then considering all green points a single one, connect it with the red ones using mst and do the same with blue ones. If there is no green point then ans should be (last red - first red + last blue - first blue). Can someone tell me where I am wrong...please

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

    The issue is that green points don't need to be directly connected: it is also valid to connect two green points using two different paths, one going over all the red points in between and one going over all blue points in between. It is easy to verify that this satisfies the constraints of the problem.

    The following should be a breaking case that tests this case:

    7
    1 G
    2 R
    3 B
    4 R
    5 B
    6 R
    7 G
    

    The correct answer for this case is 12, but it seems like your solution would output 14.

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

Can someone help where I am going wrong in finding closed-form condition for Problem D

Image

UPD : The derivation is actually correct we can put (1-a)=b then cancel out b and the ans will finally be x+b/a = done+f+(b/a)

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

      Yes, it is similar but i is varying from 0 to inf but I wonder what about that constant factor x(=done + f) Why it is not added later?

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

        I think you are having trouble with the base case.

        The formula you wrote there in the image is wrong. You are not considering all the cases. (a+ab >= k) is just the marker. here we know one b has to come to satisfy the min k ab's constraint.

        In base case we have to consider three things -

        1. expectation(of already present ab) it will simply 1*ab = ab

        2. expectation(ab's formed with already present a's and coming one b) it will be equal to 1*a = a

        3. expectation(of ab's formed with, one coming b and number of a's it brings with it).

        For the calculation of 3. we consider say it brings 0 a or 1 a with it or 2 a or n a, upto inf a's. we consider all these cases by the summation formula in my image. As 1 and 2 will always be the same irrespective of the number of a's the coming one b brings with it.

        summation formula = Here if the coming number of extra ab's formed will be equal to number of a's it brings with it.
        So, P(ab) = Pa*Pb and E(ab) = P(ab)*1 ,as 1 ab is formed
        P(aab) = Pa2*Pb and E(ab) = P(aab)*2 ,as 2 ab's are formed.
        similary you can compute upto inf and get the summation formula to generalize.

        Here, Pa = a/(a+b) , Pb = b/(a+b) , Pa = 1 — Pb

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

Can someone please provide a good explanation of problem E?

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

In problem D, in second base case, i  +  j  ≥  k, can some one explain the closed form of expectation?

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

    Check http://codeforces.com/blog/entry/56713?#comment-404349 and the image I posted in that thread above.

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

    I will try to explain it:

    i => number of a's in the prefix,

    j => number of ab's in the prefix.

    and i+j >= K,

    so we can do like this:

    1) put 1 b in the end => number of ab is now (i+j) which is >= K so we stop and probability is (Pb/(Pa+Pb)) so we add (i+j)*(Pb/(Pa+Pb)) .

    2) put 1 a and then 1 b in the end => number of ab is now (i+j+1) which is >= K , so we stop and probability is (Pa/(Pa+Pb))*(Pb/(Pa+Pb)) so we add (i+j+1)*(Pa/(Pa+Pb))*(Pb/(Pa+Pb)).

    3)put 2 a and then 1 b in the end => number of ab is now (i+j+2) which is >= K , so we stop and probability is ((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)) so we add (i+j+2)*((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)).

    and so on..

    Now if we add these it becomes =>

    (i+j)*(Pb/(Pa+Pb)) + (i+j+1)*(Pa/(Pa+Pb))*Pb/(Pa+Pb)) + (i+j+2)*((Pa/(Pa+Pb))^2)*(Pb/(Pa+Pb)) + ...

    Let's leave as an exercise for you to solve this. Spoiler: answer is => i+j+Pa/Pb

    Hope this helps :)

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

      Thanks, I got it from the picture and comment described in http://codeforces.com/blog/entry/56713?#comment-404349

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

      Hi faceless_man =))) Can you explain me more about the line : "1) put 1 b in the end => number of ab is now (i+j) which is >= K so we stop and probability is (Pb/(Pa+Pb)) so we add (i+j)*(Pb/(Pa+Pb)) "

      Why when put 1b in the end => we add (i+j) * (Pb / (Pa+Pb)) instead of adding Pb / (Pa + Pb) . I can't find the reason for why (i+j) * ... ?? =)))

      Sory for my bad English =))

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

      i have a question for i+j>=k if i=k and j=0 is this like aaaaaa(k times) and 0 'ab' if we put 1 'b' at the end it become aaaaa(k times)b why we can stop this if we only get one 'ab' but not at least k 'ab'?

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

Can anyone explain paragraph 5th of D'solution? I couldn't get it's idea

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

      This is how i understand: we consider all satisfied subsequence, for each of them, calculate p = probality and x = number of 'ab' sequence, then our excepted number equal sum of product of all pair (p, x). So why can we ignore subsequences which is large or have 'b' continuously at the beginning?

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

        we are not ignoring the large subsequences. we are including that in the summation formula. also if you have b's in the beginning then number of ab's formed is zero since no a's are prior to those b's. so expectation = (probab of those b)*0 = 0, so we ignore that case.

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

          I was wrong when asking ignore subsequences which have 'b' continuously at the beginning. i mean why can we ignore all continuously 'b' at the beginning of every sequence, as the editorial said that we can ignore them, or did i misunderstood the editorial?

          For example, probality of adding 'a' is 0.3, adding 'b' is 0.7, then for subsequence 'bab', p = 0.147 and x = 1. But if we ignore first 'b', we get p = 0,21, which change the anwser.

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

            Oh you are confused over the word "ignored"
            our answer has to be Pbn * Pa * dp[1][0] for lets say n b's occurred before the first a.
            so generalizing this case for we can get 0 to inf number of b's before first a.
            we get ans = (Pb0 + Pb1 + Pb2 + ..) * Pa * dp[1][0]
            = = dp[1][0]

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

              I don't know why they didn't explain in the editorial like what you did. Ignore few explanations could make the editorial harder, when they can add them easily.

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

                Maybe because It was div1+div2 combined that's why.

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

                  Yeah, but at least D is still for div 2

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

              Also, intuitively you can think that if you start the algorithm from beginning in all cases you will expect to have n b's and one a in some moment, thus the expected answer in all cases is dp[1][0], thus ans=dp[1][0] no matter how we weigh the cases.

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

Looking at number of solutions passed each task we could notice that A,B,C and too far from D,E,F. I think difficulty should reduce more.. gradually.

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

Can't Understand G. Anyone?

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

In Problem E, can someone explain me — by taking f(i) as a partitioning factor how can we get a partition of the bit positions?

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

    Elements with the same f value will belong in the same set in a particular partition.

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

Problem D.

-Let dp[i][j] be the expected answer given that there are i subsequences of the form 'a' in the prefix and j subsequences of the form 'ab' in the prefix.

-The answer should be dp[0][0].

These two statements seem contradicting to me.

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

    We are working backwards. We start our dp from known values which are dp[i][j] where i + j >= k, and the answer is in dp[1][0]. In state dp[i][j] we can add a letter 'a' with probability p and have expected value which is in dp[i + 1][j] or 'b' with probability (1 — p) and have expected value from dp[i][i + j].

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    You start with an empty string (that does not have any 'a' nor 'ab' occurrence)

    I think what may be troubling you is that the "base case" of this dynamic programming approach is not in the beginning, but in the end. (Sometimes the base case is i == 0 or j == 0, but here we have i+j >= k)

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

      Ok, I got it now.

      But still I think the definition of dp in the editorial is quite confusing. I suppose it would be more clear if explained as "answer we get if we start with a sequence containing i subsequences of the form 'a' and j of the form 'ab'". But maybe that's just my dullness.

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

Didn't know cards can have same indentity, which pay me 1 hack!

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

I have a solution to G with higher time complexity and I don't know how to make it better.

Supposed X have len digit, we enumerate the first different digit i with X (notice the case that the first element is 0) , then we can use any number in the last len-i digit. It can be solved with f[a][b],g[a][b] which means we have filled the first b digit using 0~a,the sum and the count of it(Remember to consider the number we filled in fist i-1 digit).

I have to pay len*10 in the part of enumerate , and used len^2*10 in dp , so the general time complexity is len^3*100 that can't pass the test cases :(

Can anyone help me?

My English isn't good and I may have many mistakes in my expreesion , sorry for it.

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

Problem H was nice and hard!

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

in problem E, can someone explain to me what is the relation between: 1- when f(x) != f(y) therefore f(x) & f(y) will be 0. and 2- the good sets S correspond to the partitions of {1,2,...,m} ??

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

    Elements with the same f value belong in the same set in a particular partition

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

I think I'm missing some concepts in order to fully understand problem D. Can anyone point me out where to look?

In the first example, if we stop when we get the first 'ab' sub-sequence, how is it possible for expected value of the number of such sub-sequences be greater than 1 in the end?

Thank you.

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

    For the first example, we could make a sequence like "aaab", which has 3 occurences of the subsequence "ab".

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

      Ah, that's what message was about. Are these three exactly: "a**b", "*a*b" and "**ab"?

      Anyway, I think I've got it now. Thanks :)

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

Can someone give a brief description on solution of D. I read the editorial, but couldn't understand it....

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

    Define dp[i][j] as they expected answer of se start problem algoritm with Amy position that has i a's and j ab's subsequences. Imagine you start the algorithm from one of these positions. In one case worth pa a's are incremented and in the other case worth pb ab's are incremented by i. So we know in both cases the new state thus the expected answer in them (asumming we have already computed dp with higher i,j) We just make a weigthed average of expected answer in both cases to reach dp[i][j] formula (case a worths pa, expected answer dp[i+1][j], case b worths pb, expected answer dp[i][i+j]. (See Wikipedia for weigthed average, it is an easy formula ) Base case and final case are very hard. Try to think them and ask if you are lost

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

      thanks a lot..... i understood it a bit now. One query, why the final answer is dp[1][0] and not dp[0][0]??

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

        dp[0][0] is defines as any starting position with only b's. dp[1][0] is any starting positions with a finite amount of b's and then an a. It can be proved mathematically dp[0][0]=dp[1][0] but I used intuitive aproach. When you start algorithm you have 0 b's thus expected answer must be dp[0][0]. However no matter your luck when you the algorithm in all scenarios you end in a moment with a finite amount of b's and an a (could be 0 b's). Thus in all cases expected answer should be dp[1][0]

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

Hi! and Happy new Year to all. In problem E, I think to understand the editorial (most of it) but I don't get how all hypothesis claimed there implies a solution for the given problem. If someone would give me an example where this hypothesis are used. thanks

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

Can anyone please explain Problem G in details ? Codeforces editorial was a bit difficult to understand. Something about dynamic programming on digits...... I watched Endagorion's screencast of the same, but I couldn't understand properly.

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

for those who are having problem in understanding D : https://discuss.codechef.com/questions/120548/help-in-understanding-expectation

All the credits to John_smith :)

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

    Thanks, E(aaa)=E(aaaa)/2+E(aaab)/2 nice example explanation for understanding dp

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

      yaah it's awesome ! ALl thanks to JOHN :)

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

      btw did you have any good tutorial for centroid decomposition? If you have then please share!

      Happy coding :)

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

        currently don't have enough EXP to unlock that skill :(

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

Need some help for problem E. I understood it as letting fi=fj or fi*fj=0 for all i,j, thus counting the number of ways of partitioning {1,2...m}. But how are we take into account set T?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

    so, basically, T is describing whether 2 elements can stay in the same set in the partition or not.

    for example, you are given T as (the same format as problem input):

    01234567
    --------
    11100000
    10100111
    10011111
    01101111
    

    And for example, you are now checking whether element 0 and 2 can be in the same set, then you retrieve their bits (just take the corresponding columns of the input matrix):

    02
    --
    11
    11
    10
    01
    

    now the third row is 1 and 0, meaning if 0 is taken, don't take 2 in the final partition.

    you will see that 2 elements can be in the same set iff their bits (columns) are the same.

    So you can group the elements with same bits together and calculate how many ways you can partition them.

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

Thank you for the great problems and quality editorials!

Since I still have difficulty in understanding editorial of problem D, can I add one more question? Can you explain how i+j >= k can contribute to make sequence space closed ? For example, with k = 3, there are infinite i, j pairs. (3,0), (4, 0), (5, 0), and so on.

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

    So for i + j >= k, if you get another 'b', you will stop. Now ignore the i and j.

    Suppose you get a 'b' with probability p each time, which corresponds to pb/(pa+pb) in the problem. Then the expected number of experiments you have to do to get a 'b' is 1/p.

    So i + j >= k the case where you can calculate the exact expected number.

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

      To be honest, I am not clear with your statement "i + j >= k the case where you can calculate the exact expected number." Could you elaborate a little further on that point?

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

    Let me answer my previous question as I understood.

    If i + j >= k, E(i, j) = i + j + Pa/Pb <== faceless_man showed how it is calculated. Though infinite i/j pairs satisfies i+j>=k, we want to have smaller number of base cases for the efficiency (which means smaller DP states to be calculated.)

    So, with k=3, (3,0), (2,1), (1, 2) are considered as the base cases, but (4,0), (2,2), (3,1), (1,3) are not.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

That D has to be one of the coolest DP problems I've seen. Seriously, compressing an infinitely long memoization matrix into finite size is sweet.

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I can't get G solution.Can somebody explain me the solution with more details?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    You need to calculate this subproblem: solve n[i][j], which means the number of integers that is <= X and when sorted, has i-th digit >= j. (say, i starting from 0 and counting from the least significant digit)

    For example, let X = 22, and let's sort the numbers:

    1 2 3 4 5 6 7 8 9 01 11 12 13 14 15 16 17 18 19 02 12 22
    

    You will see that, n[1][1] = 10 {11,12,...,19, 12} and n[1][2] = 1 {22}.

    Suppose you have this subproblem solved, you can get the final answer by doing sum for i to be the length of the sequence and for j to be 1 to 9:

    (n[i][j] - n[i][j + 1]) * 10^(i) * j
    

    i.e. you reformulate the sum of the original problem, by doing it digit by digit.

    However, to calculate n[i][j] is not easy (I'm not sure). (this is similar to calculating bell numbers directly is not easy, you need a O(n^2) dp).

    So, you now turn to calculate dp[a][b][c] for a fixed digit j. The state represents that you have considered a digits, how many intergers <= X, when not sorted, have equal to or more than b occurrence of j, given that integer is still equal to X or not (c). (the same defined in the official solution)

    After solving that dp, n[i][j] = dp[0][i + 1][0]. (Since you have a number >= j on i-th index, then you must have at least i+1 digits that are >= j for that number)

    And to calculate dp[a][b][c], you will need: dp[a+1][b/b-1][0/1]. The boundary cases are when b = 0/ a = |len(X)|.

    Also, you must be careful about the multiplication and modulo.

    So you see this problem is not so direct. If this is your first-ish digit dp problem, don't worry. It is not easy to understand and you may want to first do some easier digit dp first. Also, you may notice that there is a common strategy for solving dp[a][b][c] (like, assuming whether you are getting a number < or == the given upperbound or so...).

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

Can someone read my solution of problem H and tell me the complexity? http://codeforces.com/contest/908/submission/33975786

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

Can somebody explain me, how in problem D do we get 370000006 from 341/100 and 1e9+7? ... как взять дробь по модулю целого числа?

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

    a / b = a * b^-1 ≡(mod m) a * b^-1 * b^φ(m) = a * b^(φ(m) - 1)

    For prime m latter is equal to a * b^(m - 2). It can be calculated using binary exponentiation.

    φ is called Euler function, b^-1 ≡(mod m) b^(φ(m) - 1) is called modular (multiplicative) inverse.

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

What is the meaning of "the expected number of times 'ab' is a subsequence in the resulting sequence" in D?