Top Comments

Hi, I wrote problems B, C, E. Thank you all for your participation!!

On xuanjiLongest Strike 2, 26 hours ago
+63

Why is it that every time I see a blog like this, it has existed for 9 hours, unanswered, last comment in 3 hours. Then when I start writing my response suddenly there are already 2 comments explaining the solution.

If we consider directed edge (i->xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != -1, then each component will have at most one cycle if there are any.

No. of connected components = No. of vertices — No. of edges + No. of cycles

Initially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead.

Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = -1. We only consider the component with xi =-1 as we are interested only in cycles.

Let the size of components be A1,A2...AM where M are the number of component which have xi = -1

Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k-1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(M-k).

Thus for component set {A1,A2...AK} we have (k-1)! * A1 *A2...*Ak * N^(M-k)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k.

Hello there, I'll try my best to give a clear explanation about the solution.

first of all, let's assume that the given array contains no -1 (in other words, all edges are given). By looking at a single component of the graph, you can see the number of edges in it are equal to the number of nodes, since as given in the input there is a single edge having a starting point at each particular vertex.

Therefore, for every graph built in the same manner as the problem asks, it is enough to count the number of it's cycles and add these numbers up to form the answer. So from now on, we forget about the main problem and solve the new one, which is counting the number of cycles of all the graphs that can be built.

Array A may contain values equal to -1, let's see how the graph will look if we forget about these edges. There will be a bunch of components, each one having at most one cycle since there is at most one vertex in each with no edge starting at it.

Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. Think of a cycle which there are T other values equal to -1 in A other than those used to make the cycle. Then there are n^T graphs containing the cycle. So if there already exists a cycle in a component of the given graph, just add n^(the number of -1s) and forget about these components.

What is left, is a group of components, each looking like a tree, with exactly one node in them that you can add an edge from it to any other node to make your cycles. Consider a cycle using components with size B_1, B_2, ..., B_x. Then there are exactly

(x - 1)!(B_1 * B_2 * ... * B_x)

cycles that can be formed since you can put these components around a circle and then connect each component to the next one. So now you just have to calculate sum of the given expression for all components, which can be done using dynamic programming.

Here's also my code for better understanding of the solution

Code

I hope this helps :)

On xuanjiLongest Strike 2, 27 hours ago
+49

If all array elements occur at least $$$k$$$ times, then the answer is $$$n-1$$$. Otherwise there is an element that occurs less than $$$k$$$ times and we will "split" the array into subarrays that don't contain that element and recursively solve those.

Store all indices of all array elements in a map<int,vector<int>> loc; that we can use binary search on to calculate the frequency of an element $$$x$$$ in an interval $$$[l,r]$$$. Let's write a function $$$count(x,l,r)$$$ that does this.

We will write a function $$$solve(l,r)$$$ that calculates the maximum answer on the subarray $$$a[l,r]$$$. We will use a 2-pointer trick with divide and conquer to achieve a good time complexity. Move the $$$l$$$ pointer to the right and the $$$r$$$ pointer to the left until we find an element that occurs less that $$$k$$$ times, and recurse if necessary. The code will look something like this

int solve(int l, int r) {
  if(l > r) return -1;
  int L = l, R = r;
  while(l <= r) {
    if(count(a[l], L, R) < k) {
      return max(solve(L, l-1), solve(l+1, R));
    }
    l++;
    if(count(a[r], L, R) < k) {
      return max(solve(L, r-1), solve(r+1, R));
    }
    r--;
  }
  return R-L; // all elements occur >= k times
}

if we recurse on index $$$i$$$, then the recurrence relation is

$$$T(l,r) = T(l,i-1) + T(i+1, r) + O(min(i-l,r-i)*log(n))$$$

The solution to this recurrence is $$$O(n*log^2(n))$$$, which is the overall time complexity.

On xuanjiLongest Strike 2, 27 hours ago
+41

Yes, this problem can be solved in $$$O(n \log n)$$$.

First, let's assume we have a function that tells us whether a given subarray $$$l \ldots r$$$ is suitable and if not, tells us the position of an offending element, i.e. one that appears in this subarray more than 0 but less than $$$k$$$ times. Later we will discuss how to implement this efficiently, i.e. in time $$$O(\log n)$$$.

To solve the problem:

  • Try the entire array.
  • If this does not work:
    • Find a position of a value that appears more than 0 but less than $$$k$$$ times.
    • Clearly this position can not be in the solution at all.
    • Cross it off, you're left with one or two subarrays.
    • Recurse on these subarrays, return the longest solution found.

The complexity is $$$O(n \log n)$$$: every element is crossed off at most once as the subarrays you recurse on are always distinct.

Now let's discuss how to check if a subarray is suitable. First, we calculate values $$$\mathrm{need}[i]$$$: suppose $$$a_i$$$ is the $$$j$$$-th occurrence of $$$a_i$$$ in the array. Then $$$a_{\mathrm{need[i]}}$$$ should be the $$$j-k+1$$$-th occurrence of $$$a_i$$$ in the array. If $$$j < k$$$, then set $$$\mathrm{need}[i] = -\infty$$$. In other words, $$$\mathrm{need}[i]$$$ is the rightmost possible left endpoint of the subarray if $$$a_i$$$ is included and it is the last of its value in the subarray. How to calculate $$$\mathrm{need}[i]$$$ is left as an exercise to the reader but it is straightforward.

Now we build a persistent segment tree that stores pairs, supports range minimums and point updates. Initialize it with everything set to $$$\langle \infty, \infty \rangle$$$.

The $$$i$$$-th revision of the segment tree is built as follows based on the $$$(i - 1)$$$-th revision:

  • Set the $$$i$$$-th element of the segment tree to $$$\langle \mathrm{need}[i], i \rangle$$$.
  • Let $$$j$$$ be the last occurrence of $$$a_i$$$ before $$$i$$$ (if there is none, skip this step). Set the $$$j$$$-th element of the segment tree to $$$\langle \infty, \infty \rangle$$$.

To check if subarray $$$l \ldots r$$$ is suitable, take range minimum on the segment tree on the range $$$l \ldots r$$$ and revision $$$r$$$. If the first element is $$$\ge l$$$, the subarray is suitable. Otherwise, the second element tells you a faulty position.

+37

the base case is you getting so bored that you close the tab

On andr1yHelp Ukrainian Olympiads, 45 hours ago
+23

And here the government ?? What kind of brainwashing Ukrainians ?? We live here, we see without the government what is happening in our country, we see which "peace and freedom" russia brings. So if the russians really support their country, they in turn support the killing of children, women, and thousands of innocent civilians. No adequate person will support this, they are just all brainwashed and they believe that russia is a "liberator". You can say that Ukraine is throwing hundreds of fakes and all this is a lie, but in addition to the "Ukrainian government", there are thousands of foreign military journalists in Ukraine. Most of them have also seen all the horrors of the "russian peace". So if you still believe that the whole world is wrong, and russia alone knows what to do — I wish you to follow the ship)

Thank you so much for creating such great problems.

Problem B is a nice practice for greedy algorithm, and I think there are several corner cases which one should take care of.

As for Problem C, I missed the simple solution in editorial and used a more complicated one, but anyway, I have learned a lot of exciting ideas from your problems, thanks a lot!

B and C maybe a bit simple for me. Thanks for Problem E. I took really much time in it in the contest (sadly didn't solve D or E), and was happy when I could explain and proof the solution clearly.

Really a nice construction round, thank you again. ;)

gaurav172, vivace_jr, shaanknight, Asia West, India, IIIT Hyderabad

We are the team for Purdue University: Kuroni, Monogon, richzli

Is there any particular reason that some submissions run faster in C++14 compared to C++17 on the judge ?

MatheusLealV, NaimSS, tdas, Latin America, Brazil, UNICAMP

On maybesomeoneUSACO TRAINING PAGE, 32 hours ago
+12

i think you are the one who needs to solve problems.

Everything will be OK bro, just don't worry enough, I know it hurts, but You have not come this far to come this far.

You learnt to learn and learnt to problem solve. Web development is relatively easy in comparison. You'll be able to learn it much faster than those who only learnt that and then you'll surpass them in no time.

On hxu10Google Code Jam 2022: Round 2, 3 hours ago
+12

Man. I get the whole visible/hidden thing adding excitement but this was a contest that just rewarded giving up on large solves. I was bitten in the backside for sticking too long with B large because it appeared highly likely I'd need it; turns out I could've just brute forced C small and been fine. I don't feel like brute force solving should be deciding things at this stage in the competition (though I wish I had done it).

Thanks Jacob! Looking forward to it!

you overcomplicated the code for ifel

you can just do this

Spoiler

My situation is exactly same but I will continue doing CP because I didn't start it for job. Was also not able to clear coding rounds of many companies because there were people who simply copy pasted from online.

I can't do better with a square board, but I think $$$625\times 650$$$ is possible. Identify the labels with elements of the finite field $$$\mathbb{F}_{25}$$$, the rows with ordered pairs $$$(u, v)\in \mathbb{F}_{25}^2$$$, and the columns with tuples $$$(a, b, c)\in \mathbb{F}_{25}^3$$$ where $$$(a, b)$$$ is restricted to the set $$$\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$$$. Then the label at the intersection of $$$(u, v)$$$ and $$$(a, b, c)$$$ is $$$au+bv+c$$$.

Let's choose distinct rows and columns $$$(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$$$ and suppose that the corners all have the same label. If $$$(a_1, b_1) = (a_2, b_2)$$$ then $$$c_1\neq c_2$$$, so $$$a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$$$, i.e. the corners don't have the same label. Otherwise, $$$(a_1, b_1)\neq (a_2, b_2)$$$ so then $$$(u_1, v_1)$$$ is uniquely determined by $$$a_1u_1+b_1v_1+c_1$$$ and $$$a_2u_1+b_2v_1+c_2$$$. However, $$$(u_2, v_2)$$$ is determined by the same constraints so we would get $$$(u_1, v_1) = (u_2, v_2)$$$ contradiction.

Also, by a counting argument, $$$625\times k$$$ is not possible for $$$k > 650$$$.

got it thanks :D

I had not participated in it. Was it some open contest like Codeagon? I went through the problems, here are my observations/approach, please correct me if I am wrong:

Problem 1: Observe $$$B<=15$$$, so from $$$(B+1)!$$$ all the numbers will be divisible because they will have at least B as a common factor.

Problem 2: Find the diameter and then $$$\sum\dfrac{cnt_i*(cnt_i-1)}{2}$$$, where $$${cnt_i}$$$ is the count of nodes in the subtree of a child of the node which lies on the diameter.

Problem 3: You can do a knapsack kind of dp, $$$dp[i][j]$$$ denotes whether for the first $$$i$$$ elements, the sum $$$j$$$ is possible or not. Then iterate for $$$dp[n][j]$$$, for minimum $$$j$$$ which is possible, and subtract it from the total sum of bad luck mentioned in the problem to maximize it.

I paid 3 lakhs per year just to jump from Buildings

oh man you're paying way too much for bungee jumping, who's your bungee jumping guy

On Stratonov_16Why DP??, 44 hours ago
+8

fibonacci can be done faster

there's also a closed form (Binet's Formula)

Thanks Rishi! Looking forward to it!

Thank you so much for your detailed reply and paticient help, and I have learned a lot from your words.

I think I have missed at least two important observations that prevent me from solving this problem.

The first one is, if we ignore all -1, the left nodes will form several connected components, and each of them either contains a cycle or looks like a tree. If it already has a cycle, then we don't need change it, while if it is a tree, then we should add one more edge to it, and this is what we should compute.

The second one is, as you said, "Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. ". This is an important "transformation" of the original problem which makes the calculation available, and this is very tricky!

Thank you so much again for your help, and hope that one day I could handle such problem on my own.

On GeothermalThoughts on Reaching Cyan?, 18 hours ago
+8

I solved ~330 tasks from acmp.ru and after that i became cyan.

with Treeset, there isn't besides doing linear, however you could implement our own binary tree and use binary search to localize the element. Another option would be use FendWick Tree

I got it, Thanks my friend for helping me ^_^.

If you don't know segment tree, you can also solve it by just using set ( one for column and one for row ) , let the set store the rows for which cnt[i]=0 , so if we remove a rook with {x,y} , we can add x back to row set if we have 0 rook in x row , and if we add a rook to set , we can erase x from row set , same goes for column set .

On Stratonov_16Why DP??, 29 hours ago
+5

Se da un sir de cifre separate prin operatori '*' sau '+'. Avand voie sa faci maxim K interschimbari intre operatori, aflati valoarea maxima a expresiei.

On andr1yHelp Ukrainian Olympiads, 4 hours ago
+5

I hope the "support" of Ukrainian IOI participants translates to you donating to them.

As for the other point, there would be millions of people willing to discuss with you privately whether bombing civilian and spreading blatant lies and imprison people with opposite views is wrong or not.

+4

Actually, unordered_map gives us an amortized constant time insertion and look-up. Notice that I've highlighted the term 'amortized'. It means that it doesn't always take O(1) to insert and look elements up, it's just that in the vast majority of the cases this is so; that means that there are cases — although very rare — when it doesn't take O(1) to look-up. In such cases, it can actually take upto O(n) to look elements up.

map, on the other hand, gives us a worst case time-complexity of O(log n) in any possible case.

So, what seems to have happened is that you've hit the extremely rare case when unordered_map takes something like O(n).

Hope this answers your query.

:)

Results of this match: Both players managed to solve problems A and B, but Arun_bro1 beat Omar_Hafez by placing 647 ranks higher and solving problem C, which Omar_Hafez failed to solve. Although Arun_bro1 received quite a few Wrong answers on problem A and B at the beginning, he made a comeback by solving problems B, C, and then finally problem A about 70 minutes after the contest. This definitely gave Omar_Hafez some room to make his own comeback by solving problem C, which may have given him the lead due to his lower penalties.

Winner of this match: Arun_bro1

Anyone solved all the 3 problems??

On xuanjiLongest Strike 2, 26 hours ago
+4

Haha, I thought the same! At least the solutions are a little different

I think almost everyone in India who was too devoted to CP and expected something out of it without putting time anywhere else ended up in a similar situation (including me). For a while, I did share similar sentiments but to be honest I never did CP really for jobs. (It was a nice side benefit to have companies ask us in online assessments but I think CP is just like a challenging game to me. (even though it gets stressful at times)

To put some weight on my point I actually play a game called osu! even during college (which has a huge skill curve too and while it's very challenging just like CP I play it for similar reasons.) I could have invested that time into improving my web development for sure.

What I mean to say is all challenging tasks are fun in a way and you shouldn't feel bad about doing CP. (maybe it was a mistake to devote too much time to it and yes you could have put your time into doing 'industry relevant' stuff but why do you think you can't come out of this peril. You made it to expert and 5 stars, they are not insignificant accomplishments. Just steel yourselves and fight your way out and you will get somewhere for sure.

Sorry for the slight motivation rant in the end but I can relate to the blog too. Also don't consider dev to be a burden, I know it's pretty ironic considering my profile but if you put in sufficient time you will find it to be equally fun and challenging in its own way.

YES WE DO.

On hehezhouInvitation to 4th Turing Cup, 41 hour(s) ago
+3

Please see the posted tutorial, thanks!

Refer to this

Thank you very much. It really helped.

"Ek hi to Dil hai Ivan Ji kitni baar jeetoge" it means in english "There is only one heart. How many times will you win? " <3

Thank you so much bro

On beethoven97python array vs list, 25 hours ago
+3

Seems the bug has been fixed now.

1718 include problems solved in gym section and private mashups but 1698 does not include them. You can also change the settings to show all the problems solved including mashups.

Auto comment: topic has been updated by loser_iitian (previous revision, new revision, compare).

On LastTryDirected Acyclic Graph (DAG), 19 hours ago
+3

if I am correct you reversed the topological order for iterating the DP states in correct order

Yes, you are correct. This way of iteration of states is also known as "bottom up".

Will not the answer be same without reversing the ordering.

It is also possible to solve it in a way called "top down" but I felt it was easier to understand and explain the bottom up approach.

On LastTryDirected Acyclic Graph (DAG), 17 hours ago
+3

Wow, did you just come online from the big hiatus of codeforces due to this comment or do your frequently lurk?

On GeothermalThoughts on Reaching Cyan?, 14 hours ago
+3

I suggest practising the ABCD problems in the Atcoder Beginner Contest

On LastTryDirected Acyclic Graph (DAG), 13 hours ago
+3

Thank you very much ivanilos, you replied to a blog written 6 years ago. I was not hoping but really thanks for taking out your time and clearing the doubt.

Did you have hands 20 days ago?

Care for the disabled, start with you and me.

it helped a lot...thanx.. your solution show that d=a for ever..why in editorial he didnot show that??

I get AC but with different sol it based on filling diagonals

``

afaik number of spots are not fixed.

On GeothermalThoughts on Reaching Cyan?, 25 hours ago
+2

I usually need motivation to play a game...

On ayhan23EJOI 2022 when,where?, 23 hours ago
+2

As a problem setter, I would encourage everyone to read and think on every problem, as they are very interesting.

All the best!!

But it is not a knapsack, if you closely observe. Even if it is, tell me the weight of the knapsack and also tell me the type of knapsack it it pls.

On andr1yHelp Ukrainian Olympiads, 39 hours ago
+1

I hope Ukrainian students can take part in IOI. God bless Ukrainian people.

On maybesomeoneUSACO TRAINING PAGE, 31 hour(s) ago
+1

there is no way

On GeothermalThoughts on Reaching Cyan?, 28 hours ago
+1

Interesting take. I found math courses, competition math (I wasn't ever good at it), and solving competition programming on CF and Project Euler trained me to think for hours or days on one problem.

Yes

Any hint on how the total number of problems for a given user is computed?

I've used Codeforces API to check some stats and according to my computation I have 1718 solved problems but according to the stats on my profile I have only 1698 solved problems (i.e. 20 less). Of course, I did deduplication not to take into account problems that were ACed more than once.

Can you please elaborate on what problems or contests might be disqualified from being counted in the overall stats?

On ayhan23EJOI 2022 when,where?, 23 hours ago
+1

I got it, thanks. But, if war ends (I hope) is there any chance to be onsite?

+1

I don't know why this post was downvoted, I think that Rookie SRMs are a great initiative for beginners by Topcoder + you can win cute prizes

On wocagavHelp in codenation problem, 2 days ago
0

I too had same idea but how you handled the farthest node and largest one, can you please share code?

In Problem E, I can't understand how the optimization is working. Can anyone help me.

The optimization of DP We can find that the g(k) is in [2,3,4,5], so we can use fenwick tree to optimize it. There are n fenwick trees, the i-th is called C[i].

For each i,j:

  • Add 25×f[i][j] to the (i+1)-th element of C[j+2], and subtract it to the (i+10)-th element of C[j+2].
  • Add 25×f[i][j] to the (i+10)-th element of C[j+3], and subtract it to the (i+100)-th element of C[j+3].
  • Add 25×f[i][j] to the (i+100)-th element of C[j+4], and subtract it to the (i+1000)-th element of C[j+4].
  • Add 25×f[i][j] to the (i+1000)-th element of C[j+5].

Did anyone get any prizes , or was anyone contacted ?

Can anyone help in this question? I actually tried so hard in this but stuck with TLE in DP solution, may due to stack overflow. Please help me with question.

My TLE solution:

int f(int i,int move, vector<int,int> &arr, unordered_map<string, int> &mp)
{
   if(i== arr.size())
   {
      if(move<0)
         return INT_MIN;
      return 0;
   }
   string s = to_string(i) + " | " + to_string(move);
   if(mp.find(s) != mp.end())
      return mp[s];
   return mp[s] = max(arr[i][1] + f(i+1,move-1,arr,mp), f(i+1,move + arr[i][0], arr,mp));
}

On TheBrukDiv 5, 47 hours ago
0

Ahahah

Yes, clearing the map takes $$$O(N)$$$, but it isn't $$$O(N+NQ)$$$, because sum of all sizes of map can be at most Q (at most 1 element can be added to map during each iteration). That is why this solution works in $$$O(N+QlogQ)$$$.

No, Thank you, Scooby-Doo!

lis05

If you can get $$$625 \times 650$$$, you can also get $$$625 \times 625$$$ by cutting the board (?)

Video Solution for Problem D.

Here are some problems which are quite similar to problem D from this round:

EDU 128 C

EDU 126 C

On wocagavHelp in codenation problem, 43 hours ago
0

Um, actually the states are a bit wrong. If we do it in this manner we will end up with a TLE since the total time left can be of the order 4e6 so instead take out the minimum possible sum of bad luck due to chosen gems and subtract it from total bad luck.

In this approach, the 2nd state will initially be at max 2e3 since we can have at most 2e3 non-chosen items.

Transitions :-

$$$dp[idx][notchosen]=min(A[idx][1]+dp[idx+1][max(notchosen−A[idx][0]-1, 0)],dp[idx+1][notchosen])$$$

base case is if notchosen $$$ == 0$$$ at idx == size return $$$0$$$ else return Infinity.

Hopefully this is the proper solution.

I have a similar solution 157331395 with the following differences:

When generating rectangles for $$$c$$$, we can do a small tweak so no two rectangles intersect with each other, this will make the count easier. We use $$$(x1, y1, x2, y2), x1 \le x2, y1 \le y2$$$ to represent a rectangle.

We do a sweep line over the $$$x$$$ axis, move $$$X$$$ from $$$1$$$ to $$$n$$$, we use two 1D segment trees:

$$$F$$$: Count the cover of rectangles that are fully inside the current region, i.e. the rectangle's $$$x2 \le X$$$. Let $$$F_y = $$$ the number of covered cells $$$(x, y), 1 \le x \le X$$$. We just use the traditional "range add, query sum" segment tree.

$$$G$$$: Count the cover of rectangles that are partially inside the current region, i.e. $$$x1 \le X \lt x2$$$. Each leaf node $$$G_y$$$ maintains:

  1. $$$x$$$: $$$x1$$$ of the rectangle covering column $$$y$$$, or 0 if it is not covered.

  2. $$$cnt$$$: 1 if column $$$y$$$ is covered, or 0 if it is not covered.

Non-leaf nodes maintain the sum of $$$x$$$ and sum of $$$cnt$$$. It is a modification of "range set, query sum" segment tree. We need to add an extra field to indicate if the column is covered.

For every rectangle whose $$$x1 = X$$$, add it to $$$G$$$. For every rectangle whose $$$x2 = X$$$, remove it from $$$G$$$ and add it to $$$F$$$.

To calculate the number of covered cells inside rectangle region (1, 1, X, Y): Let $$$g$$$ = $$$G$$$.query(1, $$$Y$$$). The count = $$$g$$$.$$$cnt * (X+1) - g$$$.$$$x + F$$$.query(1. $$$Y$$$)

Auto comment: topic has been updated by jacob.b.zhang (previous revision, new revision, compare).

exciting!!

Thanks it was informative

Here is my solution with ternary search.
157125272
I think the solution can be improved and may be done more clearly.

Yeah...got a delivery agent suddenly deliver the smartwatch one day without any prior intimidation..

Thank you for the advice

same, but i get absolutely terrified when delivery agent start intimidating me.

Auto comment: topic has been updated by dukhi_insaan (previous revision, new revision, compare).

Can anyone post the editorial for C in easy words?

Here it is Editorial.

No, sorry. It is unfortunately somewhat annoying to go between Kattis and CF/Polygon problem formats.

If there is a query box with width W and height H, then to cover each cell there must be at least one rook in each row in the box, or at least one rook in each column in the box. So, if there is a row and a column in the box which don't have a rook in them, then there is a cell that is not covered. Otherwise, all cells are covered.

We can do two(one for columns, one for rows) Segment Trees with checking, if there is a zero in the segment. If we add rook, we add +1 to the column and row in the trees. If we remove rook, than we add -1.

Thanks Rishi! Looking forward to it!

s=A1&A2&A3&A4......&An

i dont understand why we need to make all element equal to s? any proof?

https://codeforces.com/contest/1679/submission/157366338 can anybody tell me why this code is is giving WA For problem C

Let's say if array is partitioned into $$$k$$$ parts,where each part contribute to each number in the final array, and bitwise AND of each part is $$$a$$$ (values in the final array). Bitwise AND of the whole (original) array is basically the bitwise and of all $$$k$$$ final numbers, which is $$$a$$$($$$a$$$ & $$$a$$$ $$$=$$$ $$$a$$$). So that is why we have to make all elements equal to $$$s$$$.

Thanks Rishi! Looking forward to it!

Try this snippet

if(($1) || ($2))
{
  if(($1) && ($2))
  {

  }
  else
  {
  	if($1)
  	{

  	}
  	else
  	{
  		
  	}
  }
}
else
{

}
On hehezhouInvitation to 4th Turing Cup, 34 hours ago
0

Can someone elaborate upon this how to calculate dp g(u,v,x) as defined in tutorial of problem F(Trees)(Subtask 5) in quadratic time? Or any other quadratic solution to the problem. Best I could come up with was O(n^2logn) solution with help of convolutions.

nvm I was using FFT for convolutions but starighforward all possible pair multiplication too leads to O(n^2) complexity overall removing the logn factor. gr8 problem thanks :)

The board $$$625\times625$$$ can be achieved just by placing $$$x_1x_2+y_1+y_2$$$ almost like in the editorial, but picking $$$x_{1,2}$$$ and $$$y_{1,2}$$$ from $$$\mathbb{F}_{25}$$$ instead of $$$\mathbb{Z}_{23}$$$. The question is, can you do at least $$$626\times 626$$$?

On Suika_predatorZJCPC2022 in the Gym!, 33 hours ago
0

Done.