### ch_egor's blog

By ch_egor, 11 months ago, translation,

Thanks for the participation!

1323A - Even Subset Sum Problem was authored and prepared by vintage_Vlad_Makeev

1323B - Count Subrectangles was authored and prepared by vintage_Vlad_Makeev

1322A - Unusual Competitions was authored by vintage_Vlad_Makeev and prepared by DebNatkh

1322B - Present was authored by meshanya and prepared by wrg0ababd

1322C - Instant Noodles was authored by vintage_Vlad_Makeev and prepared by ch_egor

1322D - Reality Show was authored by voidmax and prepared by okwedook

1322E - Median Mountain Range was authored by Sender and prepared by grphil

1322F - Assigning Fares was authored by mingaleg, vintage_Vlad_Makeev and prepared by KiKoS

c++ code by gritukan
#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

vector<ll> gao(vector<int> a) {
int n = a.size();
vector<ll> res(n + 1);
int i = 0;
while (i < n) {
if (a[i] == 0) {
i++;
continue;
}

int j = i;
while (j < n && a[j] == 1) {
j++;
}
for (int len = 1; len <= j - i; len++) {
res[len] += j - i - len + 1;
}
i = j;
}

return res;
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m;
ll k;
cin >> n >> m >> k;
vector<int> a(n);
vector<int> b(m);
for (int& x : a) {
cin >> x;
}
for (int& x : b) {
cin >> x;
}

ll ans = 0;

auto ga = gao(a);
auto gb = gao(b);
for (int i = 1; i < ga.size(); i++) {
if (k % i == 0 && k / i <= m) {
ans += ga[i] * gb[k / i];
}
}

cout << ans << "\n";
return 0;
}



• +39

 » 11 months ago, # |   +6 Why editorial for D1C in Russian?
•  » » 11 months ago, # ^ |   +3 fixed
 » 11 months ago, # |   0 How is it written 2weeks ago?
•  » » 11 months ago, # ^ |   0 Just look at the announcement;)
 » 11 months ago, # |   +69 Div1.D reminds me 2048.
•  » » 9 months ago, # ^ |   0 By 2048, what do you mean?
•  » » » 9 months ago, # ^ |   0 google 2048, game
 » 11 months ago, # |   +16 can anyone explain div2 D problem
•  » » 10 months ago, # ^ |   0 It's the same problem as Div1 B -> 1322B — Present
 » 11 months ago, # |   +8 How can I split the vertices with same neighboring set in div1 C? I tired hashing with mod 1000000009 and add vertices with same hash values, but got WA at main test 88 :(
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 With hashing you need two modulos to avoid conflicts
•  » » 11 months ago, # ^ |   0 trying not well-known modulos(or return pair of integer with different modulos as hash value) might help.
•  » » » 11 months ago, # ^ |   +66 I highly dissuade hashing (multi)sets modulo a prime. Instead: assign random 64bit integer for each element, and use xor/sum of all elements as hash of the whole set (xor if we are guaranteed there are no repetitions, or we do want repetitions to cancel out, sum if we're hashing a multiset). To get those values of each element I use following function: ull mix(ull o){ o+=0x9e3779b97f4a7c15; o=(o^(o>>30))*0xbf58476d1ce4e5b9; o=(o^(o>>27))*0x94d049bb133111eb; return o^(o>>31); //Those constants supposedly are chosen to give this function better pseudo-random properties, but on any on-site contest, when one can't have team reference document/doesn't want to waste time searching it for implementation typing arbitrary large odd numbers by hand should be good enough } And value used for x is mix(x), or in case of rounds with hacking mix(x ^ salt), where salt is value returned by chrono::steady_clock::now().time_since_epoch().count() at the beginning of runtime. This is way faster than anything using modulo, uses all 2^64 possible hash values, so avoids any birthday paradox issues, also avoids any overflows/issues with and requires way less code than using more than one modulo.Moreover this technique can be used for hashing other objects than sets, e.g. sequences, which can be represented as set of pairs $(i, a_i)$, the only difference is that now we need random value for each pair, but this can be easily done e.g. by ull hash(pii a) {return mix(a.first ^ mix(a.second));} And finally: using well-known modulos is not an issue, as long as you use random number as base (guaranteed by Schwartz–Zippel lemma).
•  » » » » 11 months ago, # ^ |   0 really appreciate it! thanks :D
•  » » » » 11 months ago, # ^ |   0 Hashing sequences modulo two highly non-random primes has always worked for me. Your method seems better, but the critical part is avoiding outright bad hashes and the second is avoiding easy hacks, the rest is finetuning.
•  » » » » 10 months ago, # ^ |   0 thanks a lot!!
•  » » » » 8 months ago, # ^ |   0 Hey, would it possible for you to give a little insight on its applications and also could you give some links to your own codes using this methodology so that I can study them.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +16 Using a map passes in a little bit less than 1s 72663606. Memory is easy to analyze here since total number of elements in all vectors in the map will be equal to $E$ (where $E$ is the total number of edges). But I'm not sure how to analyze the time complexity of this solution.
•  » » » 10 months ago, # ^ |   +3 Insertion: comparing two vectors a,b takes $min(a.size(),b.size())$. In balanced BST like map comparison occurs $O(log(n))$ times (n -> size of map before insertion). So when inserting vector of size s, time is $O(s*log(n))$. So inserting multiple vectors with combined size $m$ is $O(s_1*log(n))+O(s_2*log(n))+ \ldots = O(m*log(n))$Retrieval : similar to above analysis.
•  » » » » 10 months ago, # ^ |   0 Got it. Thank you!
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 You can just keep a map,long long>, where the key (vector< int>) is the list of all connected vertices and the value is the sum. This passes in about 800ms.
•  » » » 11 months ago, # ^ |   +16 How to analyze the time complexity of this solution? How to calculate the upper bound on the total number of comparisons made in the map?
•  » » » » 11 months ago, # ^ |   +3 Good question, I'm not at all sure. Maybe someone can hack our solutions. But if i had to guess, I would say that it can not be hacked and maybe someone can show that the complexity is something better than $O(n^2 log~n)$.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +3 Well, the number of comparisons is $O(\log m)$ and each comparison takes $O(size)$. Since you search every vector in map only once and the sum of all sizes is $m$, the complexity is $O(m \log m)$
•  » » 11 months ago, # ^ |   +3 Your text to link here... I was calculating equivalence classes of vertices on the right (v ~ u iff N(v) = N(u)), adding vertices to the left part. The complexity this procedure should be around $O(V\log{V} + E)$.
 » 11 months ago, # |   +110
 » 11 months ago, # |   +5 Is the time limit of Div1B set according to $O(n \log n \log C)$ solution? My submission 72640450 runs 2979ms, which is very close to get TLE.
•  » » 11 months ago, # ^ |   0 Yes, it's pretty tight, but the first thing I wrote runs in 2 seconds and it's easy to optimise — e.g. by handling small bits more easily because everything is small when we discard larger bits.
 » 11 months ago, # | ← Rev. 3 →   +54 I will try to provide some intuition to the solution of Div1 C. Look at the image below, each node in the left half of the graph is drawn as a cricle (denoting a set, not the problem's defined set, but a new set we're going to define). The numbers in the rectangles are the ID's of the nodes and the characters are the elements included in the node's set. These set elements (the characters) represent sum of node values of the right half of the graph. For example, if $S = \{ 0 \}$ then $F(S) = a + b + c + d$. if $S = \{0, 2\}$ then $F(S) = a + b + c + d + f + g$. Note that each character in picture may denote more than one node in the right half of the original graph. Now assume you've computed the gcd of all intersections of sets like the editorial have mentioned in the first paragraph. In the image below this will mean you've computed $gcd(a, g, e, d + c, b + c, c + f, c) = m$ You will observe that if you union any number of sets now, the summation will (hopefully) be multiple of $m$. For example if $S = \{0, 1\}$ then $F(S) = a + b + c + d + e + f$, or if $S = \{0, 1, 2\}$ then $F(S) = a + b + c + d + e + f + g$. You will find that each term in the summation is a multiple of $m$. I'm not sure how to prove this formally (if someone can formalize all this trash, it would be appreciated!), but I wanted to show some intuition on how one would approach such problem.
•  » » 11 months ago, # ^ |   0 The text of the editorial for problem Div1C (D1C) is not ideal.For further clarity, I think the author had something like the following in mind. For example for the instance: LeftSide={a,b,c,d,e}; RightSide={X(11),A(7),B(8),Y(10)} and edges {a,b}-->{A,X}, {d,e}-->{B,Y} and c-->{A,B}, by what I understand for the editorial solution, the partition would be something like this:Set1 = {A,X} with value sum(11+9) = 18. Set2 = {B,Y} with value sum(8+10) = 18. Set3 = {A,B} with value sum(7+8) = 15.Clearly any non-empty subset of the LeftSide elements will have as sum a linear combination of values from the resulting sets Set1..Set3 above. Including the one with a single 1 and all 0s. As such, clearly the solution is the CMMDC of the values of these sets.The tricky part however stirs from the fact a single right hand side element (A or B in the above example) can belong to several partitions. I am not sure the author covered the part about constructing such partitions (and proving there cannot be too many of them) properly (detailed enough).My own approach (did not have time to finish implementing it during the contest), relied on the following observations: the sum of any subset is of the form Sum(Right(a1))+..+Sum(Right(ak)) - Sum(Intersect(Right(a1),Right(a2)) - ... - Sum(Interesect(Right(a[k-1]),Right(ak))). Thus all we need is the CMMDC of all singleton sets to be further reduced to common multiples to Sums of each pairwise intersection of right-hand sides of all singleton sets.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +8 An exercise in formalization for readers: think of how 908E - New Year and Entity Enumeration and this are related, and what properties of the GCD function we use.
•  » » 10 months ago, # ^ |   0 Your idea is very nice and it inspired me. I'd like to share mine to you and hope it can make some help to you.In the Tutorial, the first step is to make the "same" points into one in the right half of graph, because they look no difference at all.The "same" means having the same neighboring set, it's easy to understand the first step.After we do that, suppose we get some vertices of the right half $(1, 2, 3, 4, 5)$ with values $(v_1, v_2, v_3, v_4, v_5)$The answer is the $gcd(v_1, v_2, v_3, v_4, v_5)$, that may confused you ,why we can calculate the answer by this way? There is a way thinking about problems is from the special to the general.Suppose there're just two vertices connected with the right half of graph.We have to calculate $gcd(A, B, A\bigcup B )$ but we can use the nature of the $gcd$ to change the the problem into $gcd(x, y, z)$.Because $gcd(a, b, c)=gcd(a, gcd(b,c))$ and $gca(a+b, a)=gcd(a+b, b)=gcd(a, b)$When the numbers of vertices becomes $3, 4, 5$ or even more, you can also use the way above to "break the answer into small pieces"
 » 11 months ago, # | ← Rev. 3 →   0 I just use the loop. esay,but of course TLE.So, I have some trouble.I do not really understand the editorial.And, what should I do to improve my code.please help me, thanks!
•  » » 10 months ago, # ^ |   0 Your code runs in O(n^2). Your solution is a straight forward brute force. However, you should find an another solution in many problems due to time limit.
 » 11 months ago, # |   0 1322A - Unusual CompetitionsIn it's editorial. it's written that .Consider an index i such that bali−1≤0, bali<0, or bali−1<0, bali≤0. Then, if the si character does not participate in any shuffle oeration, the resulting string will have a ith or i−1th prefix balance negative, making the resulting sequence incorrect.How did we get this intuition ?
 » 11 months ago, # |   0 If the intended solution was O(nlognlog(1e7)) for div 1 B, where can I reduce the constant factor in my code. I am not very experienced in optimizations so any help is appreciated.
 » 11 months ago, # |   +23 Completely different solution to D1E: Prove that if $a_i$ doesn't change at some moment of time, then it will never change anymore. Assume that $a_{i-1} < a_i > a_{i+1}$. Prove that each odd-indexed change to $a_i$ will decrease the number, and each even-indexed change will increase it. (A symmetric claim works if $a_{i-1} > a_i < a_{i+1}$.) If $a_i$ decreased in the first step and increased in the second step, each of the values $a_{i-1}, a_{i+1}$ must have increased in the first step. So if $a_i$ changes at least twice, $a_{i-2} > a_{i-1} < a_i > a_{i+1} < a_{i+2}$ must hold. (Similar claim follows for any number of changes). Assume that $a_{i-1} < a_i > a_{i+1}$. Prove that the value of $a_i$ after $k$ changes is equal to $\max(a_{i-k}, a_{i-k+2}, a_{i-k+4}, \dots, a_{i+k})$ if $k$ is odd, and $\min(\text{same stuff})$ if $k$ is even. (For $a_{i-1} > a_i < a_{i+1}$, $\max$ and $\min$ are swapped.) Therefore, $a_i$ changes at least $k$ times if each $a_{i-1}, a_{i+1}$ changes at least $k-1$ times and after $k-1$ operations, $a'_i$ is not the median of ${a'_{i-1}, a'_i, a'_{i+1}}$. In particular, if $a_i$ changes exactly $k$ times, then $a_{i+1}$ will change exactly $k-1$, $k$ or $k+1$ times. Then, for each $a_i$ we will compute how many times this value changes. Obviously, $a_1$ changes 0 times. For each following $a_i$, we have three options on the number of times $k$ that $a_i$ will change. We can check if $a_i$ will change, by computing $a_{i-1}$, $a_i$, $a_{i+1}$ after $k-1$ operations using simple RMQ (we need 4 RMQ instances for computing min/max on odd/even-indexed values) and checking if $a_i$ is not the median of these three values. After we compute these values, the rest is easy: we know maximum number of times the sequence will change, and we can restore the final sequence using the formulas in (4). Not everything in here is sound, but it's possible to write down and analyze all formulas and find out everything should be OK with this solution.Total runtime is $O(n + \text{RMQBuild} + n \cdot \text{RMQQuery})$. When RMQ is implemented using a sparse table or a segment tree, we end up with a very fast $O(n \log n)$ solution: 72662345. Using the optimal RMQ, we can solve the problem in $O(n)$ time.
 » 11 months ago, # |   +1 Can someone walk me through the complexity of D2 B of the editorial. I thought it will led to TLE but it didn't.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 For finding factors of k, you need O(sqrt(k)). After that you can pre-calculate the no. segments of all length(up to the size of array) which only contains 1 in one go. So, you need O(m+n) for this. Finally iterate over all the factors of k (which is very small compared to other factors, so you can neglect its complexity) and calculate the answer. ( Say the current factor is a , then other correspondin factor will be b(=k/a), since a*b must be k. Now check how many segments of a are in array 1 and how many segments of b are in array 2 and vice versa. Add these to the final ans ) So, final complexity is O(sqrt(k)*(n+m)).
 » 11 months ago, # |   0 What was the intended complexity of div2B? I can see so many solutions running in about sqrt(k)*(n+m). Shouldn't that TLE? I had come up with something similar too early in the contest but didn't submit because I thought it will TLE :/. Ended up submitting an optimisation of the same, which runs in somewhat similar complexity.
•  » » 11 months ago, # ^ |   0 Well, complexity sqrt(k) * (n + m) will have TLE. This sqrt(k) comes from finding all divisors of k. You don't need to do that. You only need to find divisors d such that either (d <= n and k / d <= m) or (d <= m and k / d <= n), others are just too big. And that will be fast enough.
•  » » » 11 months ago, # ^ |   0 Yeah, agreed. What I meant to ask was, why are submissions like these [LINK] getting accepted ? Isn't this exactly sqrt(k)*(n + m) complexity, which is of the order 10^9 as per the given constraints ?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0 I'm also not sure why submissions like that are accepted. In my solution, I did loop sqrt(k) times, but in my precomputation I only stored the maximal consecutive lengths and put them in a map. With some basic math you find that the number of entries in the maps are bounded by sqrt(n) and sqrt(m), so my solution ran in sqrt(k)*(sqrt(n)+sqrt(m)).
•  » » » » » 10 months ago, # ^ |   +3 Yeah I did the same during the contest. But after the contest ended I saw so many solutions being accepted without using map and traversing over the entire array. Wasted a lot of time in this unfortunately :/
•  » » » » 10 months ago, # ^ |   +4 it's not sqrt(k)*(n+m), it's d*(n+m) where d is number of k's divisors. i think d can't be more than 1000, that's why this solution fits in 1s.
•  » » » » » 10 months ago, # ^ |   0 Oh yes you're right! Thanks! I need to learn how to correctly analyse the complexity xD
•  » » » » 10 months ago, # ^ |   +3 The upperbound of number of divisor of a number N is considered n^(1/3). So it's not sqrt(k)*(n+m), but it's (k^(1/3))*(n+m)
•  » » » » » 6 months ago, # ^ |   0 But this should get TLE too. In worst case k = 16e10 and (n + m) = 8e5 ==> (k^(1/3))*(n + m) = 5e3 * 8e5 = 4e9, then how is this running within a second? I solved this question by preprocessing both arrays to store count of contiguous 1s only (as mentioned in previous comments).
•  » » » » » » 6 months ago, # ^ |   0 Look at the constraints again, n,m<=4e4 not 4e5. So n+m<8e4 and k<=16e8. Hence (k^(1/3))*(n+m)=1e3*8e4=8e7
•  » » » » » » » 6 months ago, # ^ |   0 Okay got it. My bad
•  » » 10 months ago, # ^ |   +6 There's also a nlogn solution. Link
 » 11 months ago, # |   +18 In D you can also be an idiot, not reverse the sequence, and barely pass in 1980ms like this: 72679047. The complexity is $\mathcal{O}(nm \log m)$, were you trying to cut solutions like this?
 » 11 months ago, # |   0 I didn't quite get the editorial of Div.1A, can someone please explain it to me?
 » 11 months ago, # |   +5 Can someone please explain their intuition and code behind Div2D/Div1B? The tutorial doesn't help me much.
 » 10 months ago, # |   +7 For Div2D / Div1B, I think people counted in a different way as editorial, the number of pairs which have k'th bit set in their sum. Can someone share a better approach?
•  » » 10 months ago, # ^ |   +3 hey could u please explain the logic behind div 2 D problem(present).. i did not get much from the editorial ..thanks in advance
•  » » » 10 months ago, # ^ | ← Rev. 3 →   +24 Sure.Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also. 2e7 is contained in roughly 25 bits. We check for each bit of ans whether it will be turned on or off.For kth bit of ans, we see in all the pair-sums ( $a_i + a_j$ for all i and j), the kth bit of them. So if the number of pairs having kth bit set are even then for the kth bit, their xor is zero, else one. So kth bit of the answer = xor of all the kth bits of the pair-sums.To find the count of pair-sums having kth bit set, we notice that we can mod all $a_i$ by $2^{k+1}$. Why?Because say X and Y belong to input array and S = X + Y. Then X + Y can add up to have their kth bit set which means $S >= 2^{k}$ .But also notice that they can have a carry over from addition which makes numbers in range $[2^{k+1}, 2^{k+1} + 2^{k})$ have their k'th bit not set. So we only care about the kth and (k+1) th bit of all the numbers to check the xor of kth bit.After modding we say that for a sum to have kth bit set, it can take values from $[2^{k}, 2^{k+1}) \ \cup \ [2^{k+1} + 2^{k},$ Max-Value-Sum-Can-Take $]$ (Check the why spoiler to know why)To find the numbers in the proposed ranges, we simply make another array $B$ of modded $a_i$'s and sort them. Then we can assume sum, $S = B_i + B_j$ . Iterate over $i$ in $B$, find maximum bound of $j$ using binary search (built-in lower_bound or upper_bound functions in C++). For example if we want to find $B_i + B_j <= P$ then $B_j <= P - B_i$. So fix $i$ and since array is sorted we find the last $j$ that satisfies the given condition and all the numbers in the range of indices can be added to the count to check the xor.Code : 72719677Let me know if I missed something or made a mistake.
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +12 Got it...thanks a lot brother ...i realy appreciate your efforts ..keep on helping like this ..thanks a lot once again i wish i could give more than one upvote to you ..
•  » » » » 10 months ago, # ^ |   +3 Hi, thanks for the detailed solution. I understood the core part. However, I didn't understand the following: Since the maximum sum of two elements can be 2e7, the final answer can be maximum 2e7 also
•  » » » » » 10 months ago, # ^ |   +1 $1e7$ actually is a notation for $10^7$. Max value of $A_i + A_j$ is $1e7 + 1e7 = 2e7$. Now all the pair-sums can have value $2e7$ and we are xor'ing them. And we know that for two integers, $P\ xor\ Q <= P + Q$Why? Because $P + Q = (P xor Q) + 2 * (P & Q)$
•  » » » » » » 10 months ago, # ^ |   +3 Thanks a lot! And, thanks for quick reply! Keep helping others!
•  » » » » 4 months ago, # ^ |   +3 thx vro
 » 10 months ago, # | ← Rev. 10 →   +3 Is this solution (72639972) to div2B hackable? It's $O(n \cdot numDivisors(k))$, which might be a bit slow with standard Java HashMaps NotesLargest possible highly composite value for $k$ is $1396755360$ (source)Maps $Ar$ and $Br$ are bounded by $O(\sqrt n)$ distinct lengths.Update: This is my hack attempt generator: https://pastebin.com/2wyjDVMB . Local testing seems to indicate that my solution should still pass with it though (about 70ms, excluding input and startup overhead). Maybe excluding out-of-bounds divisor pairs sped it up enough to be unnoticeable with these input constraints, or even improve the big-O bound.Update 2: Yep, was unsuccessful. Thanks anyway
•  » » 10 months ago, # ^ |   0 My solution was also $O(n * numDivisors(k))$. What is the upper bound of this complexity that it passed in the time-limit?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +3 Big-O estimates are by nature an inexact science, but the literal formula evaluates to about $6 \cdot 10^7$, which could be on the edge of 1 second if the constant factor is large enough. I thought using HashMaps might push me over the limit, but I think I might have overestimated the runtime complexity of my solution, considering how fast my thought-to-be-adversarial case ran.I believe that the intended solution is meant to be $O(n^{1.5})$.
•  » » » » 10 months ago, # ^ |   0 Thank you for the response. I am interested in knowing what is the literal formula you're talking about that you calculated it to be $6e7$ ? Are you approximating the maximum number of divisors with some approximation?
•  » » » » » 10 months ago, # ^ |   +3 I did link to a source with a list of highly composite numbers and their corresponding number of divisors, but it was hidden under the spoiler: https://gist.github.com/dario2994/fb4713f252ca86c1254d
•  » » » » » » 10 months ago, # ^ |   0 I see. Thanks :)
 » 10 months ago, # |   +8 For div1 B,you can use two pointers and radix sort,then the time complexity will be n log C.
•  » » 10 months ago, # ^ |   0 Could you explain the solution more clearly? thanks.
•  » » » 10 months ago, # ^ |   0 It is same as the editorial.But for the sorting,use radix sort($O(n)$) instead of quick sort($O(n\log n)$).For the search,use two pointers($O(n)$) instead of binary search($O(n\log n)$).
•  » » » » 10 months ago, # ^ |   0 OK, thanks for your explaination.
•  » » » » » 10 months ago, # ^ |   0 Can you please further break it down? I'm struggling to follow the explanation in the editorial
•  » » » » » » 10 months ago, # ^ |   +1 You can refer to this
•  » » » » » » » 10 months ago, # ^ |   +3 Thanks. I'm having trouble understanding how did we calculate the ranges? Will you be able to elaborate on how your binary search is working in the same context please?
•  » » » » » » » » 10 months ago, # ^ |   +1 We exploit the fact that B is sorted.Let $B = [2, 3, 5, 6, 9]$ and suppose you have to find $B_i + B_j <= 11$ . Now to solve this we iterate over $i$ from range 1 to N (size of B, which is 5 here and B is 1 based indexing).For i = 1, we can take j = 2, 3, 4, 5For i = 2, we can take j = 3, 4And so on..Now to find the last value of $j$, we perform a binary search in range $[i+1, N]$ which finds the greatest index $j$ that satisfies $B_j <= 11 - B_i$ . Google the working of lower_bound and upper_bound to understand how to implement such a binary search.After finding the last $j$, we conclude that all indices from $i+1$ to $j$ can pair with $i$ to satisfy the problem in hand. So we add $(j-i+1)$ to the answer.Before asking questions, you should first google your problems to check if this kind of question is popular enough that people have answered it already. For example here, googling about upper_bound and lower_bound on geeksforgeeks or even C++ documentation, would have helped you :)
•  » » » » » » » » » 10 months ago, # ^ |   0 Thanks. Sorry for not being clear. The ranges I'm confused about is the sum of the numbers in the b_i array in your implementation. Basically how do we arrive at those numbers to ascertain that after binary addition of b_i and b_j, the kth bit will be set?
•  » » » » » » » » » 10 months ago, # ^ |   0 After modding we say that for a sum to have kth bit set, it can take values from [2k,2k+1) ∪ [2k+1+2k, Max-Value-Sum-Can-Take ]I'm not sure how these values came about ^
•  » » » » » » » » » 10 months ago, # ^ |   0 If the most significant bit of a binary number is (k+1), then for a number to have kth bit set, it is necessary to be >= $2^k$. All the numbers from there to the max val of the binary numbers with (k+1) MSB, except numbers from $2^{k+1}$ to $(2^{k+1} + 2^{k} - 1)$, will have kth bit on. Please take k = 2 and draw binary representation of each number to find out why. (I have already explained in the why spoiler in my original comment — it is because of the carry over in addition of binary numbers). If you still have doubts, please personal-message me.
•  » » » » 10 months ago, # ^ |   0 Could you please explain, how to use two pointers instead of binary search?
 » 10 months ago, # |   0 I think the time limit for Div2D is quite tight, I had a O(nlogc*logc) solution using Fenwick Tree but got a TLE
 » 10 months ago, # |   +22 Can someone explain div1D because I can't get much of what the editorial is saying?
 » 10 months ago, # |   0 why 1323 B , gb[k/i] is not giving runtime , i applied same logic but got runtime at tc 5 ... Please someone clarify
•  » » 10 months ago, # ^ |   0 Here is my code... 72659044
•  » » 10 months ago, # ^ |   0 It is probably because k/i goes up to 10^9, which is beyond the size of the array declared. You only need those factors of k which are less than n and m. Basically i <= n and k/i <= m. It should work if you handle this case.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +3 thanks ,i just added this condition and solution got accepted...72713269
»
10 months ago, # |
-36

for question B, Count subrectangles : plz can somebody tell me why following code in giving wrong answer in test case 7??

# define int long long int

using namespace std;

int max(int a,int b) { return a>b?a:b; }

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //cout<<"I must do it...Yeahhh";

int t=1;
//cin>>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;

int a[n],b[m];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
cin>>b[i];

int x=0,ans=0;
vector<int>va,vb;

vector<int>check;
for(int i=1;i<=sqrt(k);i++)
if(k%i==0)
check.push_back(i);

x=a[0];
for(int i=1;i<n;i++)
{
if(a[i]==1)
x++;
else if(a[i]==0 && a[i-1]==1)
{
va.push_back(x);
x=0;
}
else
x=0;
}
if(a[n-1]==1)
va.push_back(x);
/*for(int i=0;i<va.size();i++)
cout<<va[i]<<' ';*/
//cout<<'\n';
x=b[0];
for(int i=1;i<m;i++)
{
if(b[i]==1)
x++;
else if(b[i]==0 && b[i-1]==1)
{
vb.push_back(x);
x=0;
}
else
x=0;
}
if(b[n-1]==1)
vb.push_back(x);
/*for(int i=0;i<vb.size();i++)
cout<<vb[i]<<' ';
cout<<'\n'<<va.size()<<' '<<vb.size();*/
for(int i=0;i<check.size();i++)
{
int x=check[i];
int y=k/check[i];

for(int j=0;j<va.size();j++)
{
for(int k=0;k<vb.size();k++)
{
if(k<=va[j]*vb[k])
{
if(y==x)
{
ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
}
else
{
ans+=(max(va[j]-x+1,0) * max(vb[k]-y+1,0));
ans+=(max(va[j]-y+1,0) * max(vb[k]-x+1,0));
}
}
}
}
}
cout<<ans;
}
return 0;

}

 » 10 months ago, # |   0 How to solve A no using DP ?
 » 10 months ago, # | ← Rev. 3 →   +14 Bonus of 1322B: SolutionUse std::stable_partition as the replacement of $O(n \log n)$ sorting. FurtherBefore solving the k-th bit of the answer, partition ${a_i}$ according to the k-th bit, too. Then, incrementally, ${a_i}$ is sorted modulo $2^{k+1}$.
 » 10 months ago, # |   0 What's the $O(n)$ solution for E?
•  » » 10 months ago, # ^ |   +14 It's quite complicated. Let's call mountain high if $a_{i -1} \le a_i \ge a_{i + 1}$ and low if $a_{i - 1} \ge a_i \le a_{i + 1}$. As we know, changes will happen to consecutive segments of mountains, where for each odd $i$ $i$-th mountain is high and for even $i$ $i$-th mountain is low, or vice versa.Now let's assume that all heights are different. Then let's look for each low height $a_i$ and find, on which positions at some time there was mountain of height $a_i$. It can be noticed that there is a contiguous segment of such positions, and to find it's left border we should look at first low mountain on the left (on position $x$) which is higher than $a_i$ and first high mountain on the left (on position $y$) which is lower than $a_i$, and the left border is middle position between $i$ and $max(x, y)$. The same with right border and for high mountains. Then we can look at 4 different variants of $max(x, y)$ on the left and on the right and using only this information we can find on which positions the height $a_i$ will be in the end. For more details you can look at my code for this problem,
•  » » » 10 months ago, # ^ |   0 Where's your code?
•  » » » » 10 months ago, # ^ |   0
 » 10 months ago, # |   0 For Div1 B, 72638208 doesn't check the sum to fall in two ranges and just uses one pass instead of four passes. Anybody know why?
 » 10 months ago, # |   +8 Can anyone explain Div1D. I have no idea what the editorial is saying.
 » 10 months ago, # |   0 After reshuffling 2 segments of total length 8, we can get a right bracketed sequence:()()((()())it isn't right bracketed.
 » 10 months ago, # |   +1 Can anybody explain how to use two pointers method in Div2 D?
 » 10 months ago, # |   0 Is editorial's proof of Div1C(Instant Noodles) correct on this test? 3 6 //n, m 1 3 5 1 1 1 3 2 1 2 2 3 2 3 3 
 » 10 months ago, # |   0 can someone explain Div 2 B clearly and the code too. please
 » 10 months ago, # |   0 I have been trying to understand the editorial for Div.1 D for a whole day, but I still can't get it.Now I have a question about the problem description: "The show host reviewes applications of all candidates from $i=1$ to $i=n$ by increasing of their indices, and for each of them she decides whether to recruit this candidate or not. If aggressiveness level of the candidate $i$ is strictly higher than that of any already accepted candidates, then the candidate $i$ will definitely be rejected."Does it mean we should first choose the set of participants to accept which $l_i$ is non-ascending then let them do the show and fight against each other? If a participant was defeated, is it still regarded as "already accepted"?