Vovuh's blog

By Vovuh, history, 5 weeks 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  

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

What is the proof for problem E?

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

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

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

    It is given that we have to go from left to right in sequence.
    You cannot change sequence.

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

    You need to go sequentially i.e after putting 1 you cannot put a 1 again because there are no consecutive 1's. If it was not so then i guess it could not be solved in linear time as of now. Btw an easy and interesting problem :)

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

    Hobody don't speaks, what him algorithm works good and puts maximum things in box.

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

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

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

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

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

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

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

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

»
5 weeks 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;
}
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    last_warmed_pos do not increase test: 2 1 1 0

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

      Thank you! l just find the reason that i should > max(0,last_warmed_pos-r+1) rather than >=.:)

»
5 weeks 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);
}
  • »
    »
    5 weeks 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

»
5 weeks 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)

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

Clean implementations, really loved it <3

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

Single pass solution for B:

#include<stdio.h>
int n,r,p,q,c,i,b;
int main(){
 scanf("%d%d",&n,&r);
 while(i<n){
  scanf("%d",&b);
  if(b)p=i+r;
  if(++i==q+r){if(p==q)break; q=p; ++c;}
 }
 printf("%d\n",i>p?-1:i>q?c+1:c);
}
»
4 weeks 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;
}

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

1066E — Binary Numbers AND Sum

How to approach this question ?

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

hey,I'm not clear about level .anybody help me .

1066F

»
4 weeks 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.com/contest/1066/submission/44486589

Thanks in advance

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

in problem A how can we proof the formula that calculate the number of lanterns that are in range ( l-r)

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

Hi, can someone explain to me in details about how does problem A works? I only get a few parts out of the entire statements.

»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How do we get the complexity in approach 1 as O(nlogn). The n part of the complexity is clear with me I am not able to figure out the presence of logn, where does it come from? Kindly explain. Thanks.