include<bits/stdc++.h>

Who'll do it in your opinion?

6 years ago, # |

← Rev. 2 →

-6

Interesting, tourist vs Um_nik.

→ Reply

6 years ago, # ^ |

-8

Can you make 2 buttons for voting? :)

→ Reply

6 years ago, # ^ |

-26

How can I?

→ Reply

6 years ago, # ^ |

-16

There are online voting sites. You can create one and add a link to it.

→ Reply

6 years ago, # ^ |

-16

Done.

→ Reply

6 years ago, # ^ |

-6

Can you make it randomly shuffle these people, so that there is no bias based on position in this list?)

→ Reply

6 years ago, # ^ |

-16

Uh, that option isn't there.

→ Reply

6 years ago, # ^ |

Well, I guess this is ok for the first poll in codeforces ever ;)

→ Reply

6 years ago, # ^ |

-20

Someone is hunting my comments and downvotes them ;)

→ Reply

Um_nik

6 years ago, # ^ |

+166

Easy one for tourist

→ Reply

just_try

6 years ago, # ^ |

+13

and the master of 'O' and '0' jqdai0815 :D

→ Reply

shubhiks1032

6 years ago, # |

+87

Delayed by 15 minutes :v

→ Reply

starbot

6 years ago, # |

+90

what's the problem codeforces every round we get delay of 10-15 mins. at the last moment? :v

→ Reply

6 years ago, # ^ |

To increase the participation :)

→ Reply

6 years ago, # |

Everybody now can watch IPL final for 10 minutes :)

→ Reply

6 years ago, # ^ |

Will you travel to Russia this summer?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

No, but why??

→ Reply

6 years ago, # ^ |

The world cup will be held in Russia.

→ Reply

fastboot

6 years ago, # ^ |

I just forgot about IPL Final I was too busy watching tourist or maybe I just intentionally wanted to do that :P

→ Reply

asif04

6 years ago, # |

+155

→ Reply

6 years ago, # ^ |

+48

That second pic should say "after the contest" tbh fam.

→ Reply

Jeffrey

6 years ago, # |

← Rev. 3 →

I do not participate in the contest but I discovered that the point decrement speed is not adjusted?

This way a problem will only worth 28% of original score at the end of contest.

Edit: just saw the announcement

→ Reply

6 years ago, # |

← Rev. 2 →

+40

That's quite a lot of pretests. I like it (if they aren't mostly trash).

Not like I expect at least my F to pass, though.

→ Reply

hell_hacker

6 years ago, # |

In D why is this approach wrong? (Wa on test 5)

I have dp[begin][end][cuts]

and if cut is 0 it is just the sum of begin to end

Else i can cut it at any of the location from begin to end and see the cuts from begin to cut_position and cut_position + 1 to end.

→ Reply

P_Nyagolov

6 years ago, # ^ |

There is no guarantee that when choosing to cut at some point, the optimal AND value is obtained by the maximum possible values for the resulting two subarrays. Consider the pairs [5,5] and [5,2]. [5,2] gives us a better AND value (7), but your solution would choose [5,5].

→ Reply

dibyadarshan

6 years ago, # ^ |

How to solve D?

→ Reply

WolfBlue

6 years ago, # ^ |

← Rev. 2 →

I did a bruteforcey solution with recursion every time I switch to a new bookshelf. With a few optimizations it passed in the time limit. (Mainly, don't recurse if the AND so far is less than the best cost you've seen so far) Update: Test case #61 begs to differ, got TLE

→ Reply

Len

6 years ago, # ^ |

+11

Start from the 55th bit, let now be 0. If you can get and value equal to now + 2^i, add 2^i to now. It can be done with easy dp.

→ Reply

P_Nyagolov

6 years ago, # ^ |

+21

Find the answer bit by bit. Start with answer equal to zero. Then for i from 60 to 0, check if you can obtain a solution with answer + 2ⁱ. If you can, just add.

Checking if there is a solution with a fixed answer can by done with dp[position][parts]. To compute a state, try to fix a new position and consider dp[newposition][parts + 1] if the sum in the interval [position;newposition] contains the bits of the fixed value as a subset, in other words (sum&FixedValue) = FixedValue.

→ Reply

pk842

6 years ago, # ^ |

thanks for writing a neat and clear code. It help me a lot!

→ Reply

dlwocks31

6 years ago, # ^ |

← Rev. 3 →

What I did:

set<long long> dp[i][j] = The set of possible values obtainable when books are put into first i shelves, where first j books are used.

It is trivial to show that in first i shelves, there should be i books in minimum and i+n-k books in maximum, and so the dp array is only valid in such range. A complete dp[i][j] can be computed by [all values in dp[i-1][i-1~j-1]] & [appropriate range sum of input array].

→ Reply

6 years ago, # ^ |

you got 1000 & 0100 < 0111 & 0001, when both 1000 > 0111 and 0100 > 0001

→ Reply

Join_VNOI_Discord

6 years ago, # |

+25

I think G is too easy to be 3250.

→ Reply

xuanquang1999

6 years ago, # ^ |

← Rev. 2 →

+24

I think the hardest part in solving G is debugging your code.

PS: Btw, can anyone share with me how to debug segment tree code efficiently?

→ Reply

Join_VNOI_Discord

6 years ago, # ^ |

That's right, I forgot to mod the value after doing lazy updates. That costs me a lot of time and points.

→ Reply

6 years ago, # ^ |

how did you solve it?

→ Reply

6 years ago, # |

+13

Can someone explain how to solve E?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+19

Sort all queries and go from left to right. dp[i]- what is the last index where you can obtain i. When you encounter begin of any segment just update dp.

→ Reply

6 years ago, # ^ |

Sort the query by left, and if equal, by right?

→ Reply

6 years ago, # ^ |

By left. dp[x] = max(dp[x], min(dp[x-val_for_segment], end_of_seg))

→ Reply

mango_lassi

6 years ago, # ^ |

← Rev. 2 →

+11

I had a O((N / 64) * Q log(N)) solution with the offline dynamic connectivity strategy ( http://codeforces.net/blog/entry/15296?#comment-203606 ).

Basically you do divide-and-conquer, keeping up a bitset representing the values attainable with currently active segments.

At every step, you first make all segments that cover the current interval active, then recurse to the left half of the segment and to the right half of the segment.

At bottom level, you OR the current bitset with the result bitset.

You can add the points where a interval becomes active to a segment tree. Every interval becomes active at most log(N) times, so a interval becomes active Q log(N) times, so the complexity is O((N / 64) * Q log(N)).

→ Reply

dpaleka

6 years ago, # |

Can someone, please, explain how is updating the current set of active segments done in E? I couldn't reduce the complexity from O(Q² * N / 64) for the whole second half of the contest. Or is the intended solution completely different?

→ Reply

jtnydv25

6 years ago, # ^ |

+19

I did it in $\text{[math]}$ , by dividing queries into blocks and processing offline. Its similar to handling delete queries in graph updating( maintaining connectivity, MST etc on edge updates) problems.

→ Reply

P_Nyagolov

6 years ago, # ^ |

+16

You can get the same complexity by performing a simple sqrt decomposition on the array and keeping bitsets with all possible values for each index.

→ Reply

http://codeforces.net/contest/981/submission/38675426

6 years ago, # ^ |

+16

I did it in $\text{[math]}$ by dividing queries better, like in the RMQ table or an offline segment tree, and going down from there. I tried and tried and couldn't see how to solve it more simply...

→ Reply

gamegame

6 years ago, # ^ |

+11

I have an O(NQ) solution but I'm not sure it's right or not.

But if it is wrong, I would like to know a counter-example/why it doesn't work.

Basically I do DP like how we do it without the ranges.

Then I do sweepline, adding and removing values.

When removing, I sort of undo by reversing the way how the dp is processed.

→ Reply

Gassa

6 years ago, # ^ |

← Rev. 2 →

I basically did the same but with one large modulo instead of two small ones.

Create events "segment starts" and "segment ends", order them by the coordinate, and maintain the knapsack array "f[x] is the number of ways to get x". Inverting the knapsack update loop is straightforward.

If we stored the actual number of ways, this would certainly be a right solution. However, the actual number may be too large, so we store it modulo some number, which makes the solution fast but hackable with only moderate effort. Still, there were only few submissions for this problems per room, so the hacking did not occur.

Edit: And this thread discusses the same solution.

→ Reply

dpaleka

6 years ago, # ^ |

Thanks! Time to actually learn sqrt-decomposition or some data structures, then.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

I did it in o(n*n) with a 2d boolean array to check and a 1d integer array to count

→ Reply

WolfBlue

6 years ago, # ^ |

How can you do it in O(1) if it takes O(Q) just to scan the input :/

→ Reply

6 years ago, # ^ |

Ops, i meant O(n * n), O(1) was for updating

→ Reply

6 years ago, # ^ |

How did you made the update in O(1)?

→ Reply

6 years ago, # ^ |

f[i][j] = true if you can get a sum equal i using value x[j], and d[i] is number of value x[j] take part in creating sum i. So if you remove a value x[j], set f[i][j] = false and decrease d[i] by 1.

→ Reply

6 years ago, # ^ |

+43

My solution is completely different. For each query I stored the value x_i in $\text{[math]}$ nodes in a Segment tree (each node stores a vector of values), and then took the bitset 10000000000... and pushed it downwards to the leaf nodes. The OR of all leaf nodes then tell us which values are possible and which are not.

Complexity should be $\text{[math]}$ .

→ Reply

6 years ago, # ^ |

+24

This is what I did in the actual contest (I didn't wanted to think more, had to code quick) but I think there are much nicer O(qn) solution.

Suppose that all queries have L_i = 1. You can do the following : we don't see DP[i] as a boolean array, but an integer array maximizing the minimum endpoint among all queries that it used. For each i, you can take j iff DP[j] ≥ i. This approach can be extended without restriction on L — do the "sweep" over increasing i, inserting query j when L_j = i. Similar problem is here.

→ Reply

6 years ago, # ^ |

I think I did exactly this approach. code

→ Reply

kolkulator

6 years ago, # ^ |

Looked into your solution, seems to be the same as mine, but with minor differences. Could you explain why is that we have such difference in perfomance? Mine got TLE..

Here's my code:code

→ Reply

6 years ago, # ^ |

← Rev. 2 →

This part is wrong.

for(int el:to_upd[v]){
    to_upd[v<<1].push_back(el);
    to_upd[v<<1|1].push_back(el);
}

Imagine that all Q queries are of the form (1, N, 1). Then you will push the 1s down, so that each to_upd[v] (with v being a leaf node) contain Q elements. And then the runtime will be O(N³) (N elements, each N queries with O(N) work for the bitwise OR).

The idea to speed it up is the following: If to_upd[1] (root node) contains multiple elements, then you can immediately apply them to a bitset. This way you only have to do the operation bs |= bs << x only to_upd[1].size(), and not to_upd[1].size() * n. And similarly with the other nodes. Then propagate the bitset to the two child nodes, and not all values in to_upd.

→ Reply

kolkulator

6 years ago, # ^ |

Thanks, I forgot that the updates are duplicating.

→ Reply

pk842

6 years ago, # ^ |

can you please explain your solution a little bit more.

→ Reply

6 years ago, # ^ |

-7

Check out my solution: 38674330 I think my code should be easy to understand.

→ Reply

pk842

6 years ago, # ^ |

thanks for sharing this :) Btw if possible then can you please explain the second idea also!

→ Reply

radoslav11

6 years ago, # ^ |

← Rev. 2 →

+59

I have $\text{[math]}$ :

Keep dp[x] — count of subsets with sum X mod 10⁹ + 7. Then we can easily add and remove numbers in $\text{[math]}$ .

Here is the code.

PS: It passed so there were no anti-MOD tests.

→ Reply

yassin_

6 years ago, # ^ |

← Rev. 2 →

+13

Why can you delete like that? Couldn't something be added (or deleted) in between that influences dp[i], but not dp[i + x]?

→ Reply

6 years ago, # ^ |

+22

I also had some trouble figuring this out. But now I got it.

You can think of it in this way: dp[i+x] consists of the ways that include the summand x, and of the ways that don't include the summand x. Let's say dp[i+x] = dp_with[i+x] + dp_without[i+x]. The goal is to compute dp_without[i+x], which is dp[i+x] - dp_with[i+x].

Now, dp_with[i+x] is clearly the same as dp_without[i], since we can make a bijection between each combination with the sum i without the summand x and each combination with the sum i+x with the summand x.

Now, notice that dp_without[i] = dp[i] for all i < x, and because radolav11 computes the values with increasing i, he can just ignore the helper array dp_without and store the result directly in dp.

→ Reply

fauzdar65

6 years ago, # ^ |

There were anti-mod tests, though not for 1e9+7. I just let the dp[x] value overflow since it anyways takes mod with 2^31, but it failed on test 75

→ Reply

Svlad_Cjelli

6 years ago, # ^ |

I passed it with 1e9+9. Is there a way to do something similar with no mods?

→ Reply

mango_lassi

6 years ago, # |

← Rev. 2 →

+16

How to solve G?

I tried to do it with O(n log(n)^2) segment tree beats but got TLE'd (pretest 15). Is there a better way?

→ Reply

6 years ago, # ^ |

+24

I don't remember what segment tree beats are (other than that the name evokes someone beating a segment tree with a stick), but my solution was keeping sets for all intervals containing x for each x, using it to extract intervals of multisets to multiply by 2 and intervals of multisets to add 1 to; these 2 types of queries (+ get sum) can be handled with a fairly normal lazy segment tree. $\text{[math]}$ since there are only O(Q) intervals to update.

→ Reply

mango_lassi

6 years ago, # ^ |

+16

Okay, thanks.

I did the same but stored the intervals that have all nodes containing x in the segment tree, not in a separate set -> * log(n) more intervals -> TLE.

→ Reply

ehnryx

6 years ago, # ^ |

Xellos, Could you explain how to deal with the two operations in the lazy segment tree? I don't know how to keep it log(n) per query.

→ Reply

6 years ago, # ^ |

+18

Keep sum, mul and add for each segment.

when multiplying a segment by x, multiply sum, mul and add by x
when adding x to a segment, add x to add and size·x to sum, where size is the number of multisets in the segment
when sending mul and add down to sons, first multiply them by mul and then add add to them

→ Reply

ehnryx

6 years ago, # ^ |

Thank you! That makes a lot of sense.

→ Reply

ankurkaintura

6 years ago, # |

How to Solve 3rd Question , Tree Decomposition .

→ Reply

RubenAshughyan

6 years ago, # ^ |

Only the stars are valid for that problem

→ Reply

6 years ago, # ^ |

If it is linked list — the answer is the list itself.
Otherwise there must be only one vertex with degree > 2. This vertex joins all other paths.

→ Reply

6 years ago, # ^ |

+63

Linked list is a pretty extraordinary expression for path :p (some people call it bamboo, though xD)

→ Reply

ankurkaintura

6 years ago, # ^ |

-12

check the degree of all vertex , if there are more than 1 vertex with degree 2 than No.

→ Reply

arthurconmy

6 years ago, # ^ |

You mean more than 1 vertex with degree greater than 2

→ Reply

starboy_jb

6 years ago, # |

← Rev. 2 →

-13

jtnydv25, name is enough to understand who is he?

one of my most favourite coder...

→ Reply

6 years ago, # |

+36

Why do tasks on Codeforces have to be like this http://codeforces.net/contest/981/problem/G and this http://codeforces.net/contest/981/problem/H instead of like this https://agc024.contest.atcoder.jp/tasks/agc024_e and this https://agc024.contest.atcoder.jp/tasks/agc024_f >_>? Kinda obvious what to do more or less and then codecodecodecodecodecodecodecodecodecodecodecodecodecodecode and carefully work out details

→ Reply

xuanquang1999

6 years ago, # ^ |

← Rev. 2 →

+39

Sometimes I also wonder how problem writers on ATCoder can come up with such creative and original tasks (which is a rare thing on most of other online judge). Can any writers there share your experience?

→ Reply

6 years ago, # ^ |

+32

It's "Code Challenge", you know.

I agree problems were on the easier side, but I don't really agree that they were hard to code.

→ Reply

6 years ago, # |

→ Reply

lessmeaning

6 years ago, # |

Love these statements

→ Reply

6 years ago, # |

Simple O(N²) solution to A is pretty cute. I don't know why author gave N <= 50 and ruined the fun :p

And I really liked problem F. thanks to authors!

→ Reply

6 years ago, # ^ |

+54

Isn't the answer either 0, n or n-1? That would lead to trivial O(n). Or am I mistaken?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Now I see that too. Too cute to be true :)

I wrote it after finding a solution in my room, that only check prefixes.

→ Reply

mmaxio

6 years ago, # |

Is it really necessary to have 130+ tests for A?

→ Reply

Len

6 years ago, # ^ |

Maybe most of them are from successfull hacks.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-8

If there is at least one solution that fails from it, then yes they are neccesary =)

→ Reply

6 years ago, # |

+110

What kind of pretests are these XD?

→ Reply

300iq

6 years ago, # ^ |

+30

LOL

→ Reply

sdssudhu

6 years ago, # ^ |

← Rev. 2 →

+14

I hacked 2 such solutions in my room. I was shocked when I saw these and rechecked the question to see if I had read it right.

→ Reply

vamaddur

6 years ago, # ^ |

+24

→ Reply

xuanquang1999

6 years ago, # |

+41

How to solve F? First binary search, then reduced it to some matching problem with circular segment, then what?

→ Reply

chemthan

6 years ago, # ^ |

+81

I solved it by using Hall's theorem. Check segment instead of subset is enough!

→ Reply

arknave

6 years ago, # ^ |

+41

Here's a more detailed editorial: binary search on the answer. For each b_i, expand it to an interval c_i = [b_i - x, b_i + x]. Now we need to see if there's a matching between the a_i and these intervals c_i where a point and an interval can be matched if the interval contains that point.

If this were a line, it would be easy: sweep through the intervals left to right, pick the first point in the interval. However, we're on a circle, so intervals that cross the origin are tricky. To simplify it, "unroll" the line and double it. If an interval was originally [l, r] with l ≤ r, then add intervals [l, r] and [l + L, r + L]. Otherwise, just add the single interval. Now we have at most 2n points and intervals and run the linear matching algorithm as described above. Hall's theorem tells us that this unrolling is equivalent to a matching on the circle.

→ Reply

ehnryx

6 years ago, # ^ |

+61

Thanks for the details! I don't really get why Hall's theorem says that the unrolling is equivalent. Could you elaborate?

→ Reply

arknave

6 years ago, # ^ |

+34

Sure.

Initially, we have two sets of length n, A = {a₁, a₂, ..., a_n} and B = {b₁, b₂, ... b_n}. Now when we do this unrolling process, we get two new sets A' = {a'₁, a'₂, ... a'_n, a'_n + 1, ... a_2n} and C = {c₁, c₂, ..., c_m} where a'_i = a_i%n and c_i = [b_i - x, b_i + x]. Note that we use m instead of n because b_i might map to two c_i. n ≤ m ≤ 2n.

We have a perfect matching between A' and C. Let's apply Hall's theorem. Consider some set S', which is a subset of these a'_i. Then because we have a matching, |S'| ≤ |N(S')|, where N(S') is the set of c_i that are connected to some node in S'.

Now, to prove that there's a perfect matching between A and B, we use Hall's theorem in the other direction. Choose some subset of nodes in A, call it S. Then what is |N(S)|? Let's define S' as a subset of A' having BOTH copies of a_i for every a_i in A. Then we know by the previous paragraph that |S'| ≤ |N(S')|. Since 2|S| = |S'| and 2|N(S)| ≥ |N(S')|:

$\text{[math]}$

|S| ≤ |N(S)|, so there's a matching in the original graph.

→ Reply

YANORMALNOSUPERGOOD

6 years ago, # ^ |

+22

I think it's wrong proof.

1) Forget about the case, when |C| = 2 × n, because in this case there are no intervals, that crossing the origin and this case can be easily solved, as mention above.

2) But if you have at least one crossing the origin interval, that it means, that |C| = m < 2 × n. After that you are not able to have perfect matching, because the sizes of components are different.

3) So, I suppose you want to say, that you have the matching, where one part is covered by matching full. But again you told: "Consider some set S', which is a subset of these a'_i. Then because we have a matching, |S'| ≤ |N(S')|, where N(S') is the set of c_i that are connected to some node in S'.". If you take S' = A', than you have: $\text{[math]}$ , but $\text{[math]}$ , contradiction.

→ Reply

92anurag

6 years ago, # |

← Rev. 3 →

For ques B

Is this a valid test case ?

If yes

what is the answer for this test case

→ Reply

Vsevolod_Kaplin

6 years ago, # ^ |

The answer should be 31 = 10 + 6 + 7 + 8 = max(10, 1) + max(6, 2) + max(5, 7) + max(2, 8).

→ Reply

92anurag

6 years ago, # ^ |

But in the statement its given that

"There shouldn't be equal elements in the subsets."

In this case both the subsets have 2 elements.

→ Reply

percywtc

6 years ago, # ^ |

That's "equal elements", not "equal number of elements" .

→ Reply

92anurag

6 years ago, # ^ |

Oh, i thought that was stated in first statement of the problem.

I took it for equal number of elements.

Thanks for clarifying.

→ Reply

Vsevolod_Kaplin

6 years ago, # ^ |

Well, this means that we should choose some elements from array a[], some elements from array b[], and no one from chosen elements are the same.

→ Reply

marat.snowbear

6 years ago, # |

+81

modulo 998244353

I see this line and I feel sick. I see this line in two problems and I want to leave competitive programming for another year.

→ Reply

chemthan

6 years ago, # ^ |

← Rev. 3 →

+38

I guess H is FFT problem so author wants to hidden it by letting that modulo in G :)

→ Reply

6 years ago, # ^ |

+97

On contrary, I always pay respect to problemsetters who put this modulo in their problems. By putting it in problems where any modulo is sufficient we obfuscate which problems need FFT.

→ Reply

6 years ago, # ^ |

-35

I think giving 10⁹ + 7 in every single problem, including FFT ones is better way to obfuscate it. No one should use NTT anyway.

→ Reply

jtnydv25

6 years ago, # ^ |

← Rev. 2 →

+24

Giving 10⁹ + 7 makes it harder to give larger constraints like 10⁵

→ Reply

6 years ago, # ^ |

-6

Then the model solution just sucks, author should come up with better algorithm.

I don’t understand how can mod 998244353 ever be a good idea. The author requires large constant factor to solve the original problem, and to overcome it they use some peculiar modulos that is known to be useful for a limited number of audiences. For someone to easily solve that problem, they should knew that “magic number” beforehand, and the fact that they have good primitive roots. Sounds pretty bad to me.

→ Reply

6 years ago, # ^ |

+25

This situation is not much different than simply knowing NTT at all.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

I doubt that. Splitting numbers in two groups is still faster than making computations modulo some number. And it works for every mod.

→ Reply

6 years ago, # ^ |

Karatsuba works for every mod, doesn't need too many modulo operations, has a nice constant, works exactly (no doubles) and if the use of FFT is complex enough — the problem isn't just reduced to a single FFT or one of garden variety D&C+FFT versions — the constraints are often long enough that Karatsuba can pass. Its only disadvantage is asymptotic complexity. Actually, even D&C+Karatsuba has complexity equal to Karatsuba only.

→ Reply

6 years ago, # ^ |

Well, Karatsuba is nice algorithm indeed :)

→ Reply

Errichto

6 years ago, # ^ |

+31

I disagree. Modulo is faster than splitting and then doing computations on pairs of doubles.

→ Reply

izban

6 years ago, # ^ |

← Rev. 2 →

+49

I don't like problems that require FFT with 10⁹ + 7 modulo. Why is it better? Only because simple fractions like $\text{[math]}$ looks nicer? Not a big argument.

NTT has much shorter code, which is important in ACM-style contests, where you don't have any prewritten code, and it works absolutely with same speed. When I tested FFT vs NTT, difference in execution time was about 20%, and one of them was faster on G++, and another was faster on mingw, so they are absolutely equal in my opinion (only FFT requires slightly more memory, which can be critical in some cases).

→ Reply

6 years ago, # ^ |

← Rev. 2 →

I think I'll continue giving 10⁹ + 7 in my FFT problems though :)

It is better because it forces you write more generic solution and doesn't indicate key idea just from mod (giving NTT mod in every problem is even worse, in my opinion). You can use NTT with two primes + Chinese remainder theorem if you dislike that. It's much slower though...

→ Reply

Kostroma

6 years ago, # ^ |

+129

Good thing is that we usually know the authors before the contest

→ Reply

http://codeforces.net/blog/entry/59657?#comment-433649

6 years ago, # ^ |

+21

Yes-yes, you skip every my contest, I know.

→ Reply

percywtc

6 years ago, # |

I saw a possibly incorrect submission (see 38668742) for 981D - Bookshelves, while I have no idea how to hack it during the contest time.

The solution is simple, for dp[index][count], maintain the top 20 bitwise-and sum that ends at index with count blocks. It seems true to me that there exist cases which fail this solution(cases which you need some smaller and-sum in the middle-way).

So, can anyone suggest a way to generate the hack? Or there are some ways to prove that this solution is indeed correct?

PS. I hope these kind of submissions will fail systest... I mean, I hope the systests are strong :D

→ Reply

papa-ka-para

6 years ago, # ^ |

Pls have look at it. I also faced the same issue, with my own solution. I expected it to fail :P

→ Reply

allllekssssa

6 years ago, # |

Can someone explane me how I got WA on test 5 in final testing and someone got WA on test 13 during the contest ?

→ Reply

radoslav11

6 years ago, # ^ |

+19

As far as I know the first couple of actual tests aren't always the same as pretests. Your mistake is "dfs(1,0); -> dfs(last, 0)". I know about some people who hacked with a similar test so the test wasn't in pretests.

→ Reply

allllekssssa

6 years ago, # ^ |

Thanks !

I saw mistake, but situation with testcases was strange to me :)

→ Reply

DonMichaelCorleone

6 years ago, # |

What can be the cause of Wrong Answer for this solution of D ? Link:

→ Reply

ciphereck

6 years ago, # ^ |

Same Problem Also wanna know why my code is wrong. My Solution of D

→ Reply

Aleks5d

6 years ago, # ^ |

you take the max at each step, but it is not the best choose at this step

→ Reply

ciphereck

6 years ago, # ^ |

-8

why how ?? what's the alternative one. and why this approach is wrong ?

→ Reply

Aleks5d

6 years ago, # ^ |

Max(7, 8)&3=0 Min(7, 8)&3=3 in such solutions you need to remember all the answers and update the new answer with them

→ Reply

ciphereck

6 years ago, # ^ |

ohk got it. That's very silly one. thanks

→ Reply

taow

6 years ago, # |

← Rev. 3 →

I have no idea about the complexity of my solution for G. Only that is not bigger than O(n * q)

Link

But I got AC))

I have one main segment tree for calculating the answer and also store additional segment trees for each of the values 'x'.

→ Reply

Elegia

6 years ago, # ^ |

It's not necessary that a range modification had common parts with some modified ranges before, because after the current modification, these ranges would merge together, so the total time complexity is $\text{[math]}$

→ Reply

taow

6 years ago, # ^ |

I thought about this, but they will be merged only in this 'x'.

→ Reply

Elegia

6 years ago, # ^ |

The different 'x' doesn't affect the time complexity. One range modification will only affect at most one range after.

→ Reply

papa-ka-para

6 years ago, # |

+11

Hi everyone.

For problem D , Initially I read like, we can divide 'K' subsets in any order. (Not necessarily contiguous segments of array) .

Is it really possible to solve it ?

In last 25 minutes I read it again, and figured out Greedy-DP solution. which seems like HACK to me. And still the solution passed. I was hoping this solution to fail. Can someone tell me, is it possible to hack this solution ?

Basically I am picking up best 8000 values for each dp[i][j] , where 'i' is index, and 'j' is number of shelf's being used till index 'i'.

→ Reply

Skyscrapers

6 years ago, # ^ |

The same problem as you.

→ Reply

salvois

6 years ago, # |

+29

I enjoyed the problems, even if I didn't well. Thanks to the author.

Out of curiosity, am I the only one who found problem C easier to understand by translating the Russian version to English with Google Translate?

→ Reply

Rpd-Strike

6 years ago, # |

+24

How to solve problem F?

→ Reply

arknave

6 years ago, # ^ |

+13

http://codeforces.net/blog/entry/59657?#comment-433647

→ Reply

y0105w49

6 years ago, # |

+207

No test cases with 1<k<n-1 for H? Top two both fail with such k...

→ Reply

tourist

6 years ago, # ^ |

+182

Wow, indeed :) My solution fails due to an incorrect assert(cur == 0);, removing it fixes the trouble. Perhaps I should be more careful with my assertion checks next time...

→ Reply

http://codeforces.net/blog/entry/59713

6 years ago, # ^ |

WAAAAAAT XDDDD? Oh my holy Mike...

→ Reply

kostka

6 years ago, # ^ |

← Rev. 2 →

-15

Lol, nice catch! Also: xD

→ Reply

300iq

6 years ago, # ^ |

+41

Oops! Sorry, i thought these testcases are useless :/

→ Reply

Radewoosh

6 years ago, # ^ |

+35

Do you know what hour is it? It's rejudge hour!

→ Reply

papa-ka-para

6 years ago, # ^ |

People might feel like u r crazy , because, u want re-judge.

but they don't know, u would have rank-1 , if there would have been re-judge :P .

→ Reply

huham

6 years ago, # |

← Rev. 2 →

-77

can some one suggest whats wrong in this code for D, thanks in advance ~~~~~

include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[55][55];

ll ar[55]; const ll inf=(1LL<<60)-1;

int n,m;

ll foo(int i,int j)

{

if(j>m)

return 0;

if(i==n)
{
   if(j==m) 

   return inf;

   else

    return 0;
}
if(dp[i][j]!=-1)

return dp[i][j];

ll p=0;

ll ret=0;

for(int k=i;k<n;k++)
{
    p+=ar[k];

    ret=max(ret,(p&foo(k+1,j+1)));
}
return dp[i][j]=ret;

}

int main() {

memset(dp,-1,sizeof(dp));
cin>>n>>m;
for(int i=0;i<n;i++)
{
    cin>>ar[i];
}
cout<<foo(0,0);

}

~~~~~

→ Reply

mavd09

6 years ago, # ^ |

+23

When you have a problem that involves AND operation is a bad idea to use max because not necessarily if you return a max number you guarantee a better answer, for example:

11 & 4 = 0
11 & 3 = 3

What happened here? 4 is greater than 3 but if we return 4 we get the worst answer.

→ Reply

-osdajigu-

6 years ago, # ^ |

what about this submission?

→ Reply

ojuz

6 years ago, # |

+39

Your crafting.oj.uz ratings are updated!

→ Reply

dickynovanto1103

6 years ago, # |

Will there be editorial for this contest?

→ Reply

sahilbansal17

6 years ago, # ^ |

→ Reply

dickynovanto1103

6 years ago, # ^ |

Thanks a lot! :D

→ Reply

6 years ago, # |

Can anybody please explain their approach for problem D.

→ Reply

6 years ago, # ^ |

A observation first: We will see if we can obtain in the final sum, every bit from 60 to 0. (We must find some configuration such that every shelf contains in the sum of the values that bit)
If we can obtain a bit, then we add it to the answer, and when we try for a new bit, we always respect the bits that are already found.

I have solved it using dynamic programming dp[i][j][h] -> true or false, if we can put the first i books into j shelves such that each shelve has the bit h in its sum. (And also respects all the higher bits found previously)

→ Reply

6 years ago, # ^ |

I am not clear with this part "And also respects all the higher bits found previously" Can you please explain what do you mean by this line

→ Reply

https://letsdocp.wordpress.com/2018/05/28/codeforces-problem-useful-decomposition/

6 years ago, # ^ |

+14

Let's say for example that you are at bit 5, and you know that you have found good configurations that can have bits 8, 10 and 15. (The answer until now is 2⁸ + 2¹⁰ + 2¹⁵). When computing dp[i][j][5] we have to find some index i2 (smaller than i) such that sum(i2, i) contains 2⁵ + 2⁸ + 2¹⁰ + 2¹⁵, and dp[i2][j - 1][5] is also true (which means that the first i2 books can be put in j-1 shelves such that their total sum contains 2⁵ + 2⁸ + 2¹⁰ + 2¹⁵)

My code: 38668315

→ Reply

towrist

5 years ago, # ^ |

And what is brilliant about your solution, is that you are storing the already set bits in a number, not an array as I thought. Thanks a lot!

→ Reply

kushwah_1

6 years ago, # |

+35

Where is editorial's link ??

→ Reply

sahilbansal17

6 years ago, # ^ |

http://codeforces.net/blog/entry/59713 Use Google Translate.

→ Reply

kushwah_1

6 years ago, # ^ |

Thanks mate !!

→ Reply

I_Love_Diashka

6 years ago, # |

Thanks for great contest!

→ Reply

erge

6 years ago, # |

How to solve H? Where's the solution?

→ Reply

vjvjain0

6 years ago, # |

Editorial for C problem:

→ Reply

prathmesh_01

6 years ago, # |

How to solve D ? Cannot understand the approach listed in the comments

→ Reply

luismo

6 years ago, # |

-13

How about the Editorial????

→ Reply

aryanc403

6 years ago, # |

← Rev. 3 →

-15

Editorial ??

→ Reply

300iq

6 years ago, # |

← Rev. 2 →

+35

Hello

English editorial will be ready in 2-3 days, sorry for inconvenience, i am busy with some school exams now

Now you can translate russian version with some translator like yandex

→ Reply

sark_01

6 years ago, # |

-14

When will the editorials be posted?

→ Reply

sahilbansal17

6 years ago, # ^ |

Editorials are available on http://codeforces.net/blog/entry/59713

→ Reply

low_

6 years ago, # |

Does anyone have an editorial for the problems in this contest :(

→ Reply

vatsal

6 years ago, # ^ |

See 5th comment above.

→ Reply

ak532

6 years ago, # |

← Rev. 2 →

Can anyone please help me find a mistake in my solution for D.

Here is what I did:

dp[s][e][j] — stores the maximum possible beauty of j shelves when they contain books from a_s to a_e

if(j == 1)
     dp[s][e][j] = sum(a[i]) for i = s to e
else if(e-s+1 == j) means j books in j shelves
     dp[s][e][j] = bitwise and (a[i]) for i = s to e
else 
     dp[s][e][j] = max(sum(a[s]...a[i-1]) & dp[i][e][j-1]) for i = s+1 to e-j+2

The answer to the problem is dp[1][n][k]

Here is my code.

Thanks in Advance

→ Reply

mengbierr

6 years ago, # ^ |

← Rev. 2 →

+16

First,s = (s&a[i]);must be s = (s&a[j]);.

Second,This test case:

4 3 11 6 1 3

Answer:3.Your output:0

11&(6+1)&3=3.But in your solution,dp[2][4][2]=4.(6&(1+3)).

It means that it not necessary to use the maximum value in[L,R].

→ Reply

6 years ago, # ^ |

← Rev. 2 →

ninja'd

Btw, there is also a second error in the andd computation. The for loop needs to start j = i.

→ Reply