include<bits/stdc++.h>

6 лет назад, # ^ |

+52

→ Ответить

cdkrot

6 лет назад, # ^ |

+49

→ Ответить

vintage_Vlad_Makeev

6 лет назад, # ^ |

+92

→ Ответить

xen

6 лет назад, # ^ |

+16

→ Ответить

GreenGrape

6 лет назад, # ^ |

-10

→ Ответить

vintage_Grigory_Reznikov

6 лет назад, # ^ |

-24

→ Ответить

el_sanchez

6 лет назад, # ^ |

-17

→ Ответить

rotavirus

6 лет назад, # ^ |

→ Ответить

KAN

6 лет назад, # |

+49

The random t-shirts will be selected as usual with the help of two scripts below and random from testlib.h. Seed is the score of the winner in the upcoming Codeforces Round 485 (Div. 1), the length is the number of participants between the 31-th and the 130-th places inclusive.

python code

import requests

contests = [981]

def is_eligible(contest, party_name, rank, points, problems, last_submission_time):
    return (rank >= 31 and rank <= 130)

def get_party_name(party):
    if 'teamName' in party:
        return party['teamName']
    else:
        return party['members'][0]['handle']

class Party:
    def __init__(self, contest, name, rank, points, last_submission_time):
        self.contest = contest
        self.name = name
        self.rank = rank
        self.points = points
        self.last_submission_time = last_submission_time
    
    def __lt__(self, other):
        if self.contest != other.contest:
            return self.contest < other.contest
        if self.rank != other.rank:
            return self.rank < other.rank
        if self.last_submission_time != other.last_submission_time:
            return self.last_submission_time < other.last_submission_time
        return False

eligible = []

for contest in contests:
    rows_to_fetch = 20000
    r = requests.get('https://codeforces.me/api/contest.standings?contestId=%d&from=1&count=%d&showUnofficial=false' % (contest, rows_to_fetch))
    if r.status_code != 200 or r.json()['status'] != 'OK':
        print('Error: failed to fetch results of contest %d.' % contest)
        exit()
    results = r.json()['result']['rows']
    if len(results) == rows_to_fetch:
        print('Error: results are too long in contest %d, increase limit.' % contest)
        exit()
    for row in results:
        party_name = get_party_name(row['party'])
        rank = row['rank']
        points = row['points']
        problems = 0
        last_submission_time = 0
        for problem in row['problemResults']:
            if problem['points'] > 0:
                problems += 1
                last_submission_time = max(last_submission_time, problem['bestSubmissionTimeSeconds'])
        if is_eligible(contest, party_name, rank, points, problems, last_submission_time):
            eligible.append(Party(contest, party_name, rank, points, last_submission_time))

eligible = sorted(eligible)

for i in range(1, len(eligible)):
    if not eligible[i - 1] < eligible[i]:
        print('Error: unable to sort eligible.')
        exit()

for idx, party in enumerate(eligible):
    print('{} {} {} {}'.format(idx + 1, party.contest, party.rank, party.name))

print('Total %d eligible.' % len(eligible))

#exit() # comment to see winners

winners = list(map(int, input().split()))
print()
print('Winners are:')
for place in winners:
    print('{} {} {} {}'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

print()
print('| List place | Contest | Rank | Name |')
print('|--|--|--|--|')
for place in winners:
    print('| {} | {} | {} | [user:{}] |'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

c++ code

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    if (argc < 4)
    {
        cout << "Command line arguments are: seed length nwinners" << endl;
        return 1;
    }
    int seed = atoi(argv[1]);
    int len = atoi(argv[2]);
    int nwinners = atoi(argv[3]);
    rnd.setSeed(seed);
    
    set<int> winners;
    while (winners.size() < nwinners)
        winners.insert(rnd.next(1, len));
    
    for (auto winner: winners)
        cout << winner << " ";
    cout << endl;
    
    return 0;
}

→ Ответить

xtalclr

6 лет назад, # ^ |

+90

This is unfair; Grandmasters have superpowers and may control her/his seed to choose the winners in favor of their preferences

→ Ответить

xtalclr

6 лет назад, # ^ |

+46

(i'm joking)

→ Ответить

kingofnumbers

6 лет назад, # ^ |

+103

Thanks for telling, we didn't notice.

→ Ответить

orzdjq

6 лет назад, # ^ |

-8

Why using the score of the next round, not this round?

We have to wait for another two days to know whether we are lucky or not.

→ Ответить

radoslav11

6 лет назад, # ^ |

+16

So who are the winners?

→ Ответить

KAN

6 лет назад, # ^ |

+16

So the winners are:

List place	Contest	Rank	Name
6	981	36	snuke
31	981	61	Swistakk
40	981	70	yasugongshang
52	981	82	Xellos
62	981	92	shadowatyy
76	981	106	budalnik
80	981	110	kostka
88	981	118	pb0207
95	981	125	Noam527
96	981	126	xiaowuc1

→ Ответить

Who'll do it in your opinion?

6 лет назад, # |

← Rev. 2 →

-6

Interesting, tourist vs Um_nik.

→ Ответить

6 лет назад, # ^ |

-8

Can you make 2 buttons for voting? :)

→ Ответить

6 лет назад, # ^ |

-26

How can I?

→ Ответить

6 лет назад, # ^ |

-16

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

→ Ответить

6 лет назад, # ^ |

-16

Done.

→ Ответить

6 лет назад, # ^ |

-6

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

→ Ответить

6 лет назад, # ^ |

-16

Uh, that option isn't there.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

-20

Someone is hunting my comments and downvotes them ;)

→ Ответить

Um_nik

6 лет назад, # ^ |

+166

Easy one for tourist

→ Ответить

just_try

6 лет назад, # ^ |

+13

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

→ Ответить

shubhiks1032

6 лет назад, # |

+87

Delayed by 15 minutes :v

→ Ответить

starbot

6 лет назад, # |

+90

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

→ Ответить

6 лет назад, # ^ |

To increase the participation :)

→ Ответить

6 лет назад, # |

Everybody now can watch IPL final for 10 minutes :)

→ Ответить

6 лет назад, # ^ |

Will you travel to Russia this summer?

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

No, but why??

→ Ответить

6 лет назад, # ^ |

The world cup will be held in Russia.

→ Ответить

fastboot

6 лет назад, # ^ |

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

→ Ответить

asif04

6 лет назад, # |

+155

→ Ответить

6 лет назад, # ^ |

+48

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

→ Ответить

Jeffrey

6 лет назад, # |

← 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

→ Ответить

6 лет назад, # |

← 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.

→ Ответить

-emli-

6 лет назад, # |

Как решить D?

→ Ответить

IWillBeRed

6 лет назад, # ^ |

Я решал так:

1) посчитаем все возможные суммы на подотрезках и сохраним их в массив

2) В цикле идем от максимальной степени двойки (2^63) к минимальной (2^0), на каждой итерации находим все суммы, побитовое и для которых с текущей степенью двойки не равняется нулю.

3) Если из выбранных сумм можно получить весь отрезок 1..n тогда прибавляем к ответу текущую степень двойки, и удаляем из массива сумм те суммы, побитовое и которых равнялось 0.

→ Ответить

hell_hacker

6 лет назад, # |

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.

→ Ответить

P_Nyagolov

6 лет назад, # ^ |

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].

→ Ответить

dibyadarshan

6 лет назад, # ^ |

How to solve D?

→ Ответить

WolfBlue

6 лет назад, # ^ |

← 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

→ Ответить

Len

6 лет назад, # ^ |

+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.

→ Ответить

P_Nyagolov

6 лет назад, # ^ |

+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.

→ Ответить

pk842

6 лет назад, # ^ |

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

→ Ответить

dlwocks31

6 лет назад, # ^ |

← 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].

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Join_VNOI_Discord

6 лет назад, # |

+25

I think G is too easy to be 3250.

→ Ответить

xuanquang1999

6 лет назад, # ^ |

← 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?

→ Ответить

Join_VNOI_Discord

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

how did you solve it?

→ Ответить

6 лет назад, # |

+13

Can someone explain how to solve E?

→ Ответить

6 лет назад, # ^ |

← 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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

mango_lassi

6 лет назад, # ^ |

← Rev. 2 →

+11

I had a O((N / 64) * Q log(N)) solution with the offline dynamic connectivity strategy ( http://codeforces.me/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)).

→ Ответить

belkka

6 лет назад, # |

-15

Антипалиндром http://acmp.ru/index.asp?main=task&id_task=491

→ Ответить

6 лет назад, # ^ |

+15

Ну всё, теперь контест будет нерейтинговый... =)) (joke)

→ Ответить

6 лет назад, # ^ |

+13

Hi , so to me seems like a notorious coincidence. Though I have come across a similar technique in a programming article ( it was in Russian ) way back.

→ Ответить

Dalgerok

6 лет назад, # ^ |

справедливо

→ Ответить

belkka

6 лет назад, # ^ |

Ненавижу людей

→ Ответить

dpaleka

6 лет назад, # |

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?

→ Ответить

jtnydv25

6 лет назад, # ^ |

+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.

→ Ответить

P_Nyagolov

6 лет назад, # ^ |

+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.

→ Ответить

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

6 лет назад, # ^ |

+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...

→ Ответить

gamegame

6 лет назад, # ^ |

+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.

→ Ответить

Gassa

6 лет назад, # ^ |

← 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.

→ Ответить

dpaleka

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

WolfBlue

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

+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]}$ .

→ Ответить

6 лет назад, # ^ |

+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.

→ Ответить

6 лет назад, # ^ |

I think I did exactly this approach. code

→ Ответить

kolkulator

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← 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.

→ Ответить

kolkulator

6 лет назад, # ^ |

Thanks, I forgot that the updates are duplicating.

→ Ответить

pk842

6 лет назад, # ^ |

can you please explain your solution a little bit more.

→ Ответить

6 лет назад, # ^ |

-7

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

→ Ответить

pk842

6 лет назад, # ^ |

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

→ Ответить

radoslav11

6 лет назад, # ^ |

← 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.

→ Ответить

yassin_

6 лет назад, # ^ |

← 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]?

→ Ответить

6 лет назад, # ^ |

+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.

→ Ответить

fauzdar65

6 лет назад, # ^ |

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

→ Ответить

Svlad_Cjelli

6 лет назад, # ^ |

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

→ Ответить

mango_lassi

6 лет назад, # |

← 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?

→ Ответить

6 лет назад, # ^ |

+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.

→ Ответить

mango_lassi

6 лет назад, # ^ |

+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.

→ Ответить

ehnryx

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

+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

→ Ответить

ehnryx

6 лет назад, # ^ |

Thank you! That makes a lot of sense.

→ Ответить

ankurkaintura

6 лет назад, # |

How to Solve 3rd Question , Tree Decomposition .

→ Ответить

RubenAshughyan

6 лет назад, # ^ |

Only the stars are valid for that problem

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

+63

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

→ Ответить

ankurkaintura

6 лет назад, # ^ |

-12

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

→ Ответить

arthurconmy

6 лет назад, # ^ |

You mean more than 1 vertex with degree greater than 2

→ Ответить

starboy_jb

6 лет назад, # |

← Rev. 2 →

-13

jtnydv25, name is enough to understand who is he?

one of my most favourite coder...

→ Ответить

6 лет назад, # |

+36

Why do tasks on Codeforces have to be like this http://codeforces.me/contest/981/problem/G and this http://codeforces.me/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

→ Ответить

xuanquang1999

6 лет назад, # ^ |

← 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?

→ Ответить

6 лет назад, # ^ |

+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.

→ Ответить

6 лет назад, # |

→ Ответить

lessmeaning

6 лет назад, # |

Love these statements

→ Ответить

6 лет назад, # |

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!

→ Ответить

6 лет назад, # ^ |

+54

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

→ Ответить

6 лет назад, # ^ |

← 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.

→ Ответить

mmaxio

6 лет назад, # |

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

→ Ответить

Len

6 лет назад, # ^ |

Maybe most of them are from successfull hacks.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

-8

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

→ Ответить

6 лет назад, # |

+110

What kind of pretests are these XD?

→ Ответить

6 лет назад, # ^ |

+30

LOL

→ Ответить

sdssudhu

6 лет назад, # ^ |

← 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.

→ Ответить

vamaddur

6 лет назад, # ^ |

+24

→ Ответить

xuanquang1999

6 лет назад, # |

+41

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

→ Ответить

chemthan

6 лет назад, # ^ |

+81

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

→ Ответить

arknave

6 лет назад, # ^ |

+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.

→ Ответить

ehnryx

6 лет назад, # ^ |

+61

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

→ Ответить

arknave

6 лет назад, # ^ |

+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.

→ Ответить

YANORMALNOSUPERGOOD

6 лет назад, # ^ |

+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.

→ Ответить

92anurag

6 лет назад, # |

← Rev. 3 →

For ques B

Is this a valid test case ?

If yes

what is the answer for this test case

→ Ответить

Vsevolod_Kaplin

6 лет назад, # ^ |

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

→ Ответить

92anurag

6 лет назад, # ^ |

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.

→ Ответить

percywtc

6 лет назад, # ^ |

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

→ Ответить

92anurag

6 лет назад, # ^ |

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

I took it for equal number of elements.

Thanks for clarifying.

→ Ответить

Vsevolod_Kaplin

6 лет назад, # ^ |

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.

→ Ответить

marat.snowbear

6 лет назад, # |

+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.

→ Ответить

chemthan

6 лет назад, # ^ |

← Rev. 3 →

+38

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

→ Ответить

6 лет назад, # ^ |

+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.

→ Ответить

6 лет назад, # ^ |

-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.

→ Ответить

jtnydv25

6 лет назад, # ^ |

← Rev. 2 →

+24

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

→ Ответить

6 лет назад, # ^ |

-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.

→ Ответить

6 лет назад, # ^ |

+25

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

→ Ответить

6 лет назад, # ^ |

← 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.

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

Well, Karatsuba is nice algorithm indeed :)

→ Ответить

Errichto

6 лет назад, # ^ |

+31

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

→ Ответить

izban

6 лет назад, # ^ |

← 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).

→ Ответить

6 лет назад, # ^ |

← 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...

→ Ответить

Kostroma

6 лет назад, # ^ |

+129

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

→ Ответить

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

6 лет назад, # ^ |

+21

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

→ Ответить

percywtc

6 лет назад, # |

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

→ Ответить

papa-ka-para

6 лет назад, # ^ |

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

→ Ответить

allllekssssa

6 лет назад, # |

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

→ Ответить

radoslav11

6 лет назад, # ^ |

+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.

→ Ответить

allllekssssa

6 лет назад, # ^ |

Thanks !

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

→ Ответить

almosh

6 лет назад, # |

Где разбор?!

→ Ответить

DonMichaelCorleone

6 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Aleks5d

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

-8

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

→ Ответить

Aleks5d

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

http://codeforces.me/contest/981/submission/38676475

6 лет назад, # |

Can someone help me find bug in my code question D.

for every possible index idx, and count c I chose a perfect j to maximise the bitwise and sum and forming k subset.

Please help coders....

→ Ответить

taow

6 лет назад, # |

← 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'.

→ Ответить

Elegia

6 лет назад, # ^ |

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]}$

→ Ответить

taow

6 лет назад, # ^ |

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

→ Ответить

Elegia

6 лет назад, # ^ |

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

→ Ответить

papa-ka-para

6 лет назад, # |

+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'.

→ Ответить

Skyscrapers

6 лет назад, # ^ |

The same problem as you.

→ Ответить

TaTaPiH

6 лет назад, # |

Крутой контест! Классные задачи

→ Ответить

salvois

6 лет назад, # |

+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?

→ Ответить

Rpd-Strike

6 лет назад, # |

+24

How to solve problem F?

→ Ответить

arknave

6 лет назад, # ^ |

+13

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

→ Ответить

y0105w49

6 лет назад, # |

+207

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

→ Ответить

tourist

6 лет назад, # ^ |

+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...

→ Ответить

6 лет назад, # ^ |

WAAAAAAT XDDDD? Oh my holy Mike...

→ Ответить

kostka

6 лет назад, # ^ |

← Rev. 2 →

-15

Lol, nice catch! Also: xD

→ Ответить

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

6 лет назад, # ^ |

+41

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

→ Ответить

Radewoosh

6 лет назад, # ^ |

+35

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

→ Ответить

papa-ka-para

6 лет назад, # ^ |

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 .

→ Ответить

huham

6 лет назад, # |

← 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);

}

~~~~~

→ Ответить

mavd09

6 лет назад, # ^ |

+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.

→ Ответить

-osdajigu-

6 лет назад, # ^ |

what about this submission?

→ Ответить

ojuz

6 лет назад, # |

+39

Your crafting.oj.uz ratings are updated!

→ Ответить

dickynovanto1103

6 лет назад, # |

Will there be editorial for this contest?

→ Ответить

sahilbansal17

6 лет назад, # ^ |

→ Ответить

dickynovanto1103

6 лет назад, # ^ |

Thanks a lot! :D

→ Ответить

6 лет назад, # |

Can anybody please explain their approach for problem D.

→ Ответить

6 лет назад, # ^ |

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)

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

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

6 лет назад, # ^ |

+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

→ Ответить

towrist

4 года назад, # ^ |

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!

→ Ответить

kushwah_1

6 лет назад, # |

+35

Where is editorial's link ??

→ Ответить

sahilbansal17

6 лет назад, # ^ |

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

→ Ответить

kushwah_1

6 лет назад, # ^ |

Thanks mate !!

→ Ответить

I_Love_Diashka

6 лет назад, # |

Thanks for great contest!

→ Ответить

erge

6 лет назад, # |

How to solve H? Where's the solution?

→ Ответить

vjvjain0

6 лет назад, # |

Editorial for C problem

→ Ответить

vjvjain0

6 лет назад, # |

Editorial for C problem:

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

→ Ответить

prathmesh_01

6 лет назад, # |

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

→ Ответить

luismo

6 лет назад, # |

-13

How about the Editorial????

→ Ответить

aryanc403

6 лет назад, # |

← Rev. 3 →

-15

Editorial ??

→ Ответить

6 лет назад, # |

← 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

→ Ответить

sark_01

6 лет назад, # |

-14

When will the editorials be posted?

→ Ответить

sahilbansal17

6 лет назад, # ^ |

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

→ Ответить

low_

6 лет назад, # |

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

→ Ответить

vatsal

6 лет назад, # ^ |

See 5th comment above.

→ Ответить

ak532

6 лет назад, # |

← 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

→ Ответить

mengbierr

6 лет назад, # ^ |

← 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].

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

ninja'd

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

→ Ответить