Анонсирован VK Cup 2018! Регистрация уже идет! Приглашаем ознакомиться с информацией о Чемпионате на его странице. ×

Блог пользователя lewin

Автор lewin, 2 месяца назад, По-английски,

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
Разбор задач Good Bye 2017
 
 
 
 
  • Проголосовать: нравится  
  • +336
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

kudos to a lightening fast editorial!

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

          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 месяца назад, # ^ |
          Проголосовать: нравится +21 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          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 месяца назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

maths too hard~~

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Codeforces is becoming awesome day by day :D

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Editorial even before system testing finished, amazing punctuality grandmaster.

»
2 месяца назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +44 Проголосовать: не нравится

      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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

          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 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 месяца назад, # ^ |
              Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

              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 месяца назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Doesn't it always handle complete tripartite graphs correctly?

            • »
              »
              »
              »
              »
              »
              »
              2 месяца назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 месяца назад, # ^ |
            Проголосовать: нравится +31 Проголосовать: не нравится

          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 месяца назад, # ^ |
              Проголосовать: нравится +31 Проголосовать: не нравится

            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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -90 Проголосовать: не нравится
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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

goodbye rating

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problems blew my mind, great contest-great problems.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Editorial before Final testing. So fast. (y)

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for good contest!

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        This is correct!!

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится -7 Проголосовать: не нравится

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

          But yeah,now it's corect :))

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I wonder how to prove this formula..

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 недель назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяца назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be an editorial in Russian?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

dotorya solved G at 00:49:58 before bmerry

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When will the ratings be updated ?

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
        Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can someone please provide a good explanation of problem E?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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 месяца назад, # ^ |
              Проголосовать: нравится +7 Проголосовать: не нравится

            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 месяца назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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 месяца назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can't Understand G. Anyone?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem H was nice and hard!

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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 недель назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Happy coding :)

      • »
        »
        »
        »
        7 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    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 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 недель назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 недель назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 недель назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 недель назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    7 недель назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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