vovuh's blog

By vovuh, history, 6 years ago, translation, In English

1066A - Vova and Train

Tutorial
Solution

1066B - Heaters

Tutorial
Solution 1
Solution 2

1066C - Books Queries

Tutorial
Solution

1066D - Boxes Packing

Tutorial
Solution 1
Solution 2

1066E - Binary Numbers AND Sum

Tutorial
Solution

1066F - Yet another 2D Walking

Tutorial
Solution
  • Vote: I like it
  • +61
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the proof for problem E?

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

    First, some easy facts for you:

    a = sum of pow(2,ai) where ai is array of unique indexes of 1 in binary representation of a

    and b = sum of pow(2,bi) where bi is array of unique indexes of 1 in binary representation of b

    pow(2,x) here is 2 raised to the power x

    then a&b = sum for i,j of pow(2,ai)&pow(2,bj) where & is bitwise and.

    now, imagine you've erased k last bits of b, and result will be sum of pow(2,bi-k), and all elements with bi-k < 0 will just vanish.

    so, answer for the problem is: sum for k,i,j of pow(2,ai)&pow(2,bj-k)

    ranges for k,i,j think yourself.

    other fact, for integers x,y: pow(2,x)&pow(2,y) != 0 if and only if x == y and result is pow(2,x)

    so, answer for the problem is: for k,i,j: if ai == bj-k then add to result pow(2,ai)

    main observation: you can swap order of "for"s:

    then answer for the problem is: for i,j,k: if ai == bj-k then add to result pow(2,ai)

    now, ai, bj, k >= 0, then bj >= ai, so you can ignore all others. also, for any bj >= ai, there is k that ai == bj-k, more precisely k = bj-ai. k is basically how many bits you should erase so ai bit from a will match with bj bit from b.

    so, answer for the problem is: for i: pow(2,ai)*(count how many bits is 1 at position ai or higher) because any bj >= ai will incorporate in the sum.

    you can precalculate count of high bits.

    Now all you have to do is calculate recurrently: ans_next = ans_prev*2+count, where count is how many bits is 1 at current position or higher.

    This trick works because:

    a*8+b*4+c*2+d*1 = (a*4+b*2+c*1)*2+d = ((a*4+b)*2+c)*2+d

    You could also first precalculate counts of high bits (count of bits on all prefixes), and then go from backward, and in parallel raising 2 to power ai, but it is more nice to do it recurrently

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

can someone explain why the answer of D's test 4 is 4?

5 4 2

1 2 1 2 1

why it isnt 5?

1 1

2

2

1

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

I want real proof of D. What is in explanation is incomplete. For example fact: if you can fit some sequence in straight order, then you can fit in reverse order. Explanation says that you can go in reverse order in same certain box, and it will still fit. But it doesn't touch the fact that any box may change its content. Then what?

You can prove this fact by considering content after algorithm ran forward. Then, if last box still has space for previous item that is not in the box but next item is in the box, then you can move it to the box (closer to the end). And you can repeat this proccess until space in the box won't fit previous item. So, the box will have exactly same content as if you ran algorithm backward. Now you can do the same for all other boxes running backwards. In the end, you'll get the same result as if you ran algorithm backward. But you was starting from result of algorithm if it ran forward. Q.E.D.

In my opinion this proof is not enough. I don't know how to get proof of continuality from this. In other words: how do you know this: if you can fit starting from i, and you can't fit starting from i-1, then there is no possible j < i-1, that you can fit starting from j. Huh?

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

    Is it clear for you that if the last box in the best answer contains some set of objects then the first box in the best answer for the reversed array will contain at least this set of objects and possibly other objects? I think it is clear. So if the first box can contain the same objects let's put these objects in it and go to the next box. In such a way we can construct the same answer as in the straight order. Is it clear now?

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

      Indeed, I'm dumb. I just need apply same fact to best answer. If you can fit best answer forward, then you can fit it backward, and for each step, you can make "forward version" of algorithm for each starting position using algorithm discussed above.

      Very nice problem :)

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

    Forget about the previous version of the tutorial. I fixed it and now, I hope, there is more clear proof of this solution.

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

Can't solution for problem C be hacked which used linear search for answering 3rd query. A lot of such solutions passed it.

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

Could anybody help me why I am getting wrong answer for Problem C? Submission

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

    you have to consider that very first placed book has nothing on left or right..so take that input separately and put 0 distance for it.....and everything else in your solution is right

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

In the tutorial for problem F, I think it should be py > qy.

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

    You are right, thank you, fixed

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

    why p < q in case px = py, if py > qy?

    sorry, I understand)

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

Could anyone help me solve the problem that my code at the test 10 of problem B get a TLE??? ignore the chinese please!

#include<iostream>
#include<algorithm>
using namespace std;
#define N 1010
int n,r;
int a[N];
int main()
{
    cin>>n>>r;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
    }
    int ans=0;
    int last_warmed_pos=0;//初始最后加热点
    while(last_warmed_pos<n)
    {
        int next_h_pos=-1;
        //这里这个条件用来限定h的范围//如果在最后加热点右侧没有合适的h 那就只能在其左侧找且不能为上一个所选h
        for(int i=n;i>=max(0,last_warmed_pos-r+1);i--)
        {
            if(a[i]==1&&i-r<=last_warmed_pos)//找到最右端的h使加热范围覆盖进入last_warmed_pos
            //注意这里的i-r<=last_warmed_pos 所找h的最左未加热部分要确保已加热
            //等价于i-r+1<=last_warmed_pos+1 所找h的最左加热起点要小于等于下一个加热点
            //而不是i-r+1<=last_warmed_pos 错误!!!
            {
                next_h_pos=i;
                //cout<<"next h:"<<next_h_pos<<endl;
                break;
            }
        }
        if(next_h_pos==-1)
        {
            ans=-1;
            break;//找不到符合的h
        }
        ans++;
        last_warmed_pos=next_h_pos+r-1;//更新最后加热点
    }
    cout<<ans<<endl;
}
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    last_warmed_pos do not increase test: 2 1 1 0

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

Can anyone tell me why my FFT gets Wrong Answer on test 3 in problem E? Thanks in advance...

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL MOD = 998244353;
const int N = 524288;
double PI = acos(-1);
struct comp {
	double re, im;
	comp operator*(const comp& a){
		comp ret;
		ret.re = re * a.re - im * a.im;
		ret.im = re * a.im + im * a.re;
		return ret;
	}
	comp operator+(const comp& a){
		comp ret;
		ret.re = re + a.re;
		ret.im = im + a.im;
		return ret;
	}
	comp operator-(const comp& a){
		comp ret;
		ret.re = re - a.re;
		ret.im = im - a.im;
		return ret;
	}
};
int getord(int x){
	int ret = 0;
	while ((1 << ret) < x) {
		ret++;
	}
	return ret;
}
comp tmp[N];
comp A[N];
comp B[N];
void fft(comp* ar, int n, int mode) {
	if (n == 1) return;
	comp base;
	base.re = cos(2*PI/n);
	base.im = sin(2*PI/n);
	if (mode) base.im *= -1;
	comp cur;
	cur.re = 1;
	cur.im = 0;
	int dnc = n/2;
	for (int i = 0; i < dnc; i++) {
		tmp[i] = ar[i*2 + 1];
	}
	for (int i = 0; i < dnc; i++) {
		ar[i] = ar[i*2];
	}
	for (int i = 0; i < dnc; i++) {
		ar[i+dnc] = tmp[i];
	}
	fft(ar, dnc, mode);
	fft(ar + dnc, dnc, mode);
	for (int i = 0; i < dnc; i++) {
		comp ta = ar[i];
		comp tb = ar[i+dnc] * cur;
		ar[i] = ta + tb;
		ar[i+dnc] = ta - tb;
		cur = cur * base;
	}
}
char str1[200005];
char str2[200005];
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	scanf("%s", str1);
	scanf("%s", str2);
	int L = (1 << getord(n+m+2));
	for (int i = 0; i < L; i++) {
		A[i].re = A[i].im = 0;
		B[i].re = B[i].im = 0;
	}
	LL mul = 1;
	for (int i = 0; i < n; i++) {
		if (str1[n-i-1] == '1') {
			A[n-i-1 + 1].re = mul;
		}
		mul = (mul*2)%MOD;
	}
	for (int i = 0; i < m; i++) {
		if (str2[i] == '1') {
			B[m-i-1 + 1].re = 1;
		}
	}
	fft(A, L, 0);
	fft(B, L, 0);
	for (int i = 0; i < L; i++) {
		A[i] = A[i] * B[i];
	}
	fft(A, L, 1);
	LL ans = 0;
	for (int i = n + 1; i < L; i++) {
		LL tmp = fmod((A[i].re + 0.5) / L, MOD);
		ans += tmp;
		ans %= MOD;
	}
	printf("%lld\n", ans);
}
  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My guess is because of the roundoff error the use of floating-point values induces. Your FFT implementation uses doubles, which are imprecise for large numbers. The solution works on small inputs, but fails on larger ones, for example: https://ideone.com/cdIzUi

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

      Would it be possible for NTT to pass large test cases then?

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

How to solve D if those distribution in which there my be no empty space left for some last objects and they are not put in any box is also valid like some continuous subarray can also produce maximum answer no matter it reaches to end or not. Ex: n = 5, m = 1, k = 6, A[i] = (6 2 2 2 6) answer: 3 (from element 2 to 4)

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

    Anyone, please answer this question? "If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects." If we are able to pack all sets of objects then only it is considered as the answer. Do we have to find the max size set?

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

Clean implementations, really loved it <3

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

Can anyone please find a bug in my problem B code.....

44389702

Its giving runtime error on test case 5

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mem(dp,a) memset(dp,a,sizeof dp)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define pb(x) push_back(x)
#define sl(a) scanf("%lld",&a)
#define si(a) scanf("%d",&a)
ll INF=1ll<<60;
ll MOD=1000000007;

int main()
{
	ll n,k;sl(n);sl(k);
	ll a[n];
	rep(i,0,n)
	sl(a[i]);
	ll last=-1;
	rep(i,0,k)
	{
		if(a[i]==1)
		last=i;
	}
	ll c=0,cant=0;
	if(last!=-1)
		c=1;
	else
		cant=1;
	while(last+k<n)
	{
		ll start=last+1,end=last+2*k;
		rep(i,start,end)
		{
			if(a[i]==1)
			last=i;
		}
		if(last==start-1)
                {
                        cant=1;
                        break;
                }
		else
			c++;
	}
	cant==0 ? cout<<c<<endl : cout<<-1<<endl;
}

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

I am getting wrong on 4rth test case of F problem Please help if anyone knows the problem here is my code for the same

http://codeforces.net/contest/1066/submission/44486589

Thanks in advance

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

I've solved B using DP 55118824

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

(Necroposting). But, is the note for the 2nd test case correct? The distribution in the cases should be [4], [2], [3] and [4], not just [4].