Codeforces round #900 (Div.3) Editorial

Thank you for participating in the first ever Serbian Div. 3 Codeforces round!

Also a massive thanks to Vladosiya for giving us a chance to create a divison 3 round!

1878A - How Much Does Daytona Cost?

1878B - Aleksa and Stack

1878C - Vasilije in Cacak

1878D - Reverse Madness

1878E - Iva & Pav

1878F - Vasilije Loves Number Theory

1878G - wxhtzdy ORO Tree

• 3 months ago, # ^ | Why my solution is failing for F on tc 4 ; Solution Used pollard rho algorithm for d(n)

  • 3 months ago, # ^ | ← Rev. 2 →   +2 it usually fails on test 4 when n overflows Spoiler

    • 3 months ago, # ^ | ok, thanks !!

  • 3 months ago, # ^ | because n can be much more than 1e9 only d(n) <= 1e9, but not n

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int sl,k;
int check(int x)
{
	int res = a[sl];
	for(int i=sl+1;i<=x;i++)
	{
		res &= a[i];
		if(res<k) return 0;
	}
	return 1;
 
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int q;
		scanf("%d",&q);
		while(q--)//Խ��ԽС
		{
			scanf("%d%d",&sl,&k);
			if(a[sl]<k) printf("-1 ");
			else{
			int l=sl,r=n;
			while(l<r)
			{
				int mid=(l+r+1)/2;
				if(check(mid)) l=mid;
				else r=mid-1;
			}
			printf("%d ",l);
			}
		}
		printf("\n");
	}
}

• 3 months ago, # ^ | Your check functions runs in

  • 3 months ago, # ^ | Is the total time complexity O(t*p*n*logn)?

• 3 months ago, # ^ | You can use a ST table or binary lifting to make your check in O(logn).

  • 3 months ago, # ^ | Thank you very much!

• 3 months ago, # ^ | This implementation got TLE. To fix the TLE we can use vector of pairs instead of using an map. New implementation

• 3 months ago, # ^ | ← Rev. 2 →   +10 If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done. m < n, so maximal is not n it is mentioned. even if it is n, we have to replace next maximal by +1 if it does not already exist. so on...

  • 3 months ago, # ^ | Yes. I think the original proof in the tutorial is incomplete. The original proof actually proves the m = n case. When first reading the solution, it was hard for me to understand "However, since we have k of them, these are the k numbers that would yield the maximum sum (n,n−1,n−2,…,n−k+1). This is a contradiction!"

    • 3 months ago, # ^ | I don't get it how it's contradiction. but it is obvious that if we want maximum sum of k digit out of any random n numbers without repetition, we would choose first k digit after sorting in desending order or last k digit in asending order. Sometime Induction principle create overhead for simple problems isn't it?

      • 3 months ago, # ^ | It contradicts with the assumption that the sum s of the k numbers is not the maximal. As stated before, the key observation is we can always achieve a sum s + 1 for the sum s, given that "s is not the maximal". Based on this observation, any value that lies between the minimal and maximal can be achieved. To prove the correctness of the observation, we can sort current k numbers and denote the maximal as m. 1) If m < n, we can replace m with m + 1 and obtain s + 1. 2) If m = n, we can prove by contradiction that "there exists a number a<n such that a+1 is not among those k numbers". Then we can obtain s + 1 by replacing a with a + 1. Assuming the opposite of the conclusion gives us a consecutive sequence whose length is k and maximal is n. However, the sum of this sequence is maximal, which contradicts the assumption that "s is not the maximal". This is how it is contradicted. The proof by contradiction actually works in the same way as your induction, while it is stated in a reversed manner.

• 3 months ago, # ^ | Because it would produce the same results with the closest one. Therefore we don't have to check that node

  • 3 months ago, # ^ | I don't know if I misunderstand something. I think that if we choose another vertex that is not the closest one, the result for the current bit which we want will stay the same, but we don't know whether bits in other positions will increase the answer or not.

    • 3 months ago, # ^ | That's why we need to consider both nodes For example assume the path from to looks like this : Here are the path looks for each bits from to : And for bits from to : For the sake of explanation, let's number the nodes in the path with (where and ) Now the closest nodes with that has a bit on for each bits are : And the closest nodes with are : Notice that the only important nodes are Node — for instance — is not important because from the perspective of , the bit and will be "turned on" at node and respectively. While the bit is still "turned off" at node The key observation here is once the bit has turned on within a path, it will never be turned off again because the nature of the operations

      • 3 months ago, # ^ | Okay, let me think about it for a while, since I don't strongly understand about the fact of picking the first occurrence will give us optimal answer. However, thanks for your help!

        • 3 months ago, # ^ | Maybe the way you view it should be something like this : if the first occurence node produces the same outcome with the other nodes for the rest of the path, then it's sufficient for us to only check the first one and no need to check the rest

          • 3 months ago, # ^ | ← Rev. 2 →   0 Could you provide an example when the second occurrence will be useless? The node 5 you provide above is not one of that type (it is totally 0)

            • 3 months ago, # ^ | Try this : The important nodes are respectively : From : From : We can see that node is useless because it produces the same results as node and And node is useless because it produce the same as node

              • 3 months ago, # ^ | Thanks, I get it now!

• 3 months ago, # ^ | simple just print odd numbers from 1 to n since the condtion is always true for odd numbers

• 3 months ago, # ^ | Have you seen the authors solution

  • 3 months ago, # ^ | Small tutorial doesn't necessarily mean small code, apparently me being noob in implementing long code also hurts. Creation of prefix of all bits and then applying binary search on all of it is too much imo.

• 3 months ago, # ^ | Lol, you should have seen Problem G then

• 3 months ago, # ^ | That is a O(NlogN + QlogN)

  • 3 months ago, # ^ | ← Rev. 2 →   0 It's not logN, it's log(max a[i]), but fair enough, I guess it shouldn't be considered a constant

    • 3 months ago, # ^ | That's more than log N lol(n<=2e5, max(a) is 1e9)

      • 3 months ago, # ^ | my point is it's faster than the editorial solution while not being any more complex

        • 3 months ago, # ^ | In editorial its said it can be O(NlogN) with sparse tables(which is faster than yours) :)

        • 3 months ago, # ^ | Yeah, we said there is a solution with sparse tables, and it's very simple (if you know sparse table). We said we allowed slower solutions because it's div. 3.

• 3 months ago, # ^ | for(int i = n; i >= l; i--) This doesn't look like binary search I think.

  • 3 months ago, # ^ | Thanks for the reply. When I used this for loop I was getting TLE. But when I used binary search, I got wrong answer on the first test case.

• • 3 months ago, # ^ | Thanks vai.

  • 3 months ago, # ^ | ← Rev. 2 →   0 Can you tell me where did i do wrong? void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n); vector<int> rn; int q; cin >> q; while (q--) { int l, k; cin >> l >> k; int ans = -1; int left = l; int right = n; while (left+1 < right) { int mid = (left + right) / 2; int val = query(1, 1, n, l, mid); if (val >= k) { left = mid; ans = mid; } else { right = mid - 1; } } rn.push_back(ans); } for (int i = 0; i < rn.size(); i++) { cout << rn[i] << " "; } cout << endl; }

• 3 months ago, # ^ | You can even perform it when you are in some node in the segment tree, you see if the to the right child is still >=k then you go there. Else you go left.

  • 3 months ago, # ^ | Would you mind giving me the code?

  • 3 months ago, # ^ | May be there is a misunderstanding. How the complexity is O(qlogn)? ..ans every query by binary search and inside every transition of binary search finding "AND" of (l to mid) take O( q* (log(n) )^2)

    • 3 months ago, # ^ | sorry I was wrong I don't think my solution works

• 3 months ago, # ^ | ← Rev. 2 →   0 Yup..after the contest when i was going on through the questions and saw problem E,the first approach which came to my mind was of segment tree. I coded it and it got accepted. It's time complexity was of O(nlogn+q*logn*logn). It crossed 2s time limit. I got little astonished but then i saw that the maximum time limit was of 5s. Here is my code 225420310

• 3 months ago, # ^ | ← Rev. 2 →   0 NOP! It cause TLE. It is because the complexity will be O(q * n * log(n)), but expected is O(q*log(n)) or O(q * (log(n))^2)

  • 3 months ago, # ^ | ok got it thanks buddy!

• 3 months ago, # ^ | YES got it, and one thing the time complexity is better if we solve by using bit by bit than seg tree I guess ?

  • 3 months ago, # ^ | I think, my solution can be optimized a little bit to gain expected complexity.

    • 3 months ago, # ^ | okay.

  • 3 months ago, # ^ | Using pref sums or sparse tables is lowest possible complexity in this problem, but segtree also passes with added log N factor :)

    • 3 months ago, # ^ | Yes.okay.

    • 3 months ago, # ^ | Can you please let me know if there exists a way to calculate bitwise between given range l and r using segment tree?

      • 3 months ago, # ^ | yea its pretty easy. Just search on internet AND segment tree(u can take lets say sum segment tree and just instead + write &). Just note that in E from this round u don't need update(its called modify in some sources), so just use qry and build function.

        • 3 months ago, # ^ | ok thanks dude

        • 3 months ago, # ^ | am sorry, i am about to upvote yourr reply, by mistaken I downvoted and now its undoing even i try :|

• 3 months ago, # ^ | That's a Div3G though. Div3G can be near Div2E level, which is fine to have these kinds of algorithms

• 3 months ago, # ^ | The task cannot be solved the same way, because here the operations aren't symmetrical, and the order of operations matters.

  • 3 months ago, # ^ | Oh, ok. Thanks for clarifying.

• 3 months ago, # ^ | Have you tried lowering your bitscount to 30 or at least 31? Also you don't need 64-bit integers for this problem since all elements in the array are not greater than .

  • 3 months ago, # ^ | Yes , but it is still giving TLE 225510500

    • 3 months ago, # ^ | Your prefix array size MAX is wrong, in the problem array can have up to integers. Accepted submission: 225521320, TLE: 225521499

      • 3 months ago, # ^ | Thank you so much , I didnt realise that simple mistake in contest :(

• 3 months ago, # ^ | Thank you, it's my favorite problem I created

for(int i = 0; i < n; i++)
{
    std::cout << i + 5 << ' ';
}

• 3 months ago, # ^ | I know, I said there are many constructions, but this one is the easiest to prove I think.

  • 3 months ago, # ^ | I guess you're right. This one though also fits a possible restriction for the output like a_i <= 3 * 10^5.

• 3 months ago, # ^ | Ahhhhhh I tried to make the answer table, but the code is too long... And I used a strange code:225314696

• 3 months ago, # ^ | I don't know much about python but pypy is much faster than standard python compiler(found that while was working on round xD).

• 3 months ago, # ^ | Iva & Pav as best problem on codeforces ever :)

  • 3 months ago, # ^ | Agree :)

• 3 months ago, # ^ | You do realize that in problem's text is a gimmick because it can be simplified to always? This means that in your query loop you can directly use without calculating and bounds at all.

• 3 months ago, # ^ | Could you elaborate?

• 3 months ago, # ^ | Sparse table also used to find and , or , xor , min , max , sum etc in subarray

  • 3 months ago, # ^ | ok what will it be used here as ? its not finding xor or min or max or sum isnt here?

• 3 months ago, # ^ | Yeah it is, but many people learn some topics that are really advanced for their rank(like segment tree, not including pref sums here because it's easy to learn that idea even for newbie) and that's why E has more solves than D.

• 3 months ago, # ^ | I'm pretty sure they use sparse tables (the thing mentioned in the end of editorial for E), that's how they get a solution in

  • 3 months ago, # ^ | ← Rev. 5 →   +3 My solution (linked above) used a segment tree and it is (that's why memory is so small). I don't know why it runs so fast. Looking at the codes, neither of the other two linked solutions seem to use sparse tables. To me, it looks like they're using the fact that for fixed , there are only at most different values of bitwise and of subarray over all . The "changing points" of the bitwise and can be calculated for each and stored in time and memory, and each query can be solved in leading to a solution.

    • 3 months ago, # ^ | ← Rev. 2 →   0 thanks for the reply it really helped me to understand now vgtcross AlphaMale06. The '31' is because suppose the l is having all bits set then we can put 1 bit to 0 and then the and will reduce that bit only else it all remains set only . likewise we can have maximum 31 different numbers. is this interpretation right ?

      • 3 months ago, # ^ | Yes. Each bit can change value at most once so the total value can change 30 times, meaning that there can be 31 different values.

• 3 months ago, # ^ | If a query result can contain overlapping segments (min, max, or, and) then the sparse table only needs to look at two values for the answer. You find the largest power of 2 less than the range and calculate an overlap (eg for length 7 you do 2 queries of length 4 and include the value at position 4 twice).

  • 3 months ago, # ^ | Ohhhh I see, thank you.

• 3 months ago, # ^ | ← Rev. 4 →   0 the sum on over all the test cases exceed

  • 3 months ago, # ^ | oof, need to turn off the autocomplete thanks

    • 3 months ago, # ^ | no problem, I thought also the same xD

• 3 months ago, # ^ | If you have all the primes up to sqrt(1e9) there are less than 3500 primes to check. You can loop through that list and if you don't find a factor then the value is a prime. It isn't logarithmic complexity, but fast enough as there are only 1000 queries.

  • 3 months ago, # ^ | However, in the editorial it is claimed that a logarithmic time complexity can be achieved for the prime factorization d(n) (it shows this in the time complexity). How is that achieved?

    • 3 months ago, # ^ | It's possible to store d(N) as the map of prime divisors adding/removing new divisors on each query and never needing to factor a large number. Each query can add at most 19 new divisors.