Codeforces Round #243

11 years ago, # ^ |

Bruteforce, more or less. Try all possible ranges [l, r]; for each of them, put the numbers from that range into a multiset and the numbers not from it into another multiset. As long as swapping the largest number out of the range and the smallest number in the range improves the result (and you still have swaps available), swap them. Time: $\text{[math]}$ .

→ Reply

Andrei1998

11 years ago, # ^ |

So we have an O(N^2) for choosing the ends of the interval, but how can we do the rest in O(KlogN)?

→ Reply

xennygrimmato

11 years ago, # ^ |

Since you are using a set, elements will be searched in O(log n) and you have to choose 'k' such elements.

→ Reply

nishad94

11 years ago, # ^ |

But inserting N elements with take O(N*logN) in a multiset. I feel the time complexity for this solution will be O(N^3*K*logN)

→ Reply

11 years ago, # ^ |

My solution along the same lines works in $\text{[math]}$ .

→ Reply

adamant

11 years ago, # ^ |

I'm sorry for the offtopic, but how do you get such O?

→ Reply

ondrah

11 years ago, # ^ |

+15

Via \mathcal{O} in

Unable to parse markup [type=CF_TEX]

: $\text{[math]}$

→ Reply

JuanMata

11 years ago, # ^ |

this $\text{[math]}$ looks really cool! :)
and i think $\text{[math]}$ looks cooler than $\text{[math]}$ and $\text{[math]}$ :D

→ Reply

xennygrimmato

11 years ago, # ^ |

My solution's complexity is O(N^2*logN + N*K*logN)

→ Reply

11 years ago, # ^ |

As long as swapping the largest number out of the range and the smallest number in the range improves the result (and you still have swaps available), swap them.

There are at most K allowed swaps and each can be done in $\text{[math]}$ (because multiset).

→ Reply

11 years ago, # ^ |

Any way to solve it without multiset?

→ Reply

11 years ago, # ^ |

Sort the numbers that you'd put into multisets otherwise and do the swapping the same way.

→ Reply

thrashing

11 years ago, # ^ |

Can you provide the link to a properly implemented solution? Thanks in advance!

→ Reply

11 years ago, # ^ |

6490192

→ Reply

Konstantin.Zakharov

11 years ago, # ^ |

Bruteforce all l..r on array (for for), and try to calculate the best value on l..r by swapping worst values with best from 1..l-1 & r+1..n. I did it with sorting, but the best approach I saw is to create two piority queues "in, out" and take r-l+1 values from them (don't take more than "k" values from "out" queue)

→ Reply

ikbal

11 years ago, # |

← Rev. 3 →

+61

Div1 D was same as this ONTAK problem

EDIT : Also it exist at stackoverflow

→ Reply

11 years ago, # ^ |

+45

Yes, it seems that it is a very well-known problem.

→ Reply

adelnobel

11 years ago, # ^ |

Is there any detailed analysis of the complexity?

→ Reply

johnathan79717

11 years ago, # ^ |

The one on StackOverflow does not requires sides parallel to axis.

→ Reply

11 years ago, # ^ |

Yes, but the algorithms described in the answers are very, very slow.

→ Reply

ikbal

11 years ago, # ^ |

At the bottom there is a link to a paper.

→ Reply

11 years ago, # ^ |

+37

Btw, I like how the answer on StackOverflow which is clearly the most valuable has -1 votes :)

→ Reply

niklasb

11 years ago, # ^ |

← Rev. 4 →

+18

Because it just contains a link. Link-only answers are only valuable as long as the link is valid, so they are very susceptible to link-rot. One is expected to at least summarize the contents of the linked resource so that the answer does not lose its value if the link goes dead. Note that this particular answer does not even mention the title of the paper, which could be used to locate the resource later.

Also I feel that pointing to a 23-page paper does not cut it for this problem. At the very least I would expect the poster to point to the page where the actual problem of finding squares is addressed. But I would really prefer to see a paraphrased overview over the algorithm, so that I can quickly examine whether it actually addresses the problem without reading through pages of scientific notation. Remember that Stack Overflow is for regular users not necessarily with a background in Computer Science.

Stack Overflow still has the vision to create an archive of programming knowledge for the future, not just to make a single question asker happy for the moment.

→ Reply

LashaBukhnikashvili

11 years ago, # |

what is the idea behind the problem D(div 1) ?

→ Reply

11 years ago, # ^ |

+34

I had an $\text{[math]}$ solution. A square is uniquely defined by its 2 top (or 2 bottom etc.) points. Split the horizontal lines into large (at least $\text{[math]}$ points on the line) and small (otherwise); then, there are just $\text{[math]}$ squares whose 2 top points lie on a small line, same for those whose 2 bottom points lie on a small line and 2 top ones on a large one.

There are at most $\text{[math]}$ large lines. For each point on one of these lines and each line below it, you can also check if there's a square for which these are 2 right points. There are also $\text{[math]}$ these questions.

How to check the existence of many pairs of points (out of which all lie on 1 horizontal line)? Just make a vector saying if there's a point with some x-coordinate. You can do this for many lines with 1 vector, taking just O(1) time per query + O(N) time amortized for filling and cleaning the vector.

→ Reply

HellKitsune

11 years ago, # ^ |

+18

Or you could use the fact that unordered_set is extremely fast and write something very short like this: click ^_^

→ Reply

11 years ago, # ^ |

Wow, that looks useful. I don't know more about unordered_set than it erasing a $\text{[math]}$ -factor in theoretical complexity (and decreasing the practical one) :D

→ Reply

Emettant

11 years ago, # ^ |

← Rev. 3 →

I really liked next comparation: vx[x[i]].size() < vy[y[i]].size() in HellKitsune's solution.

I believe $\text{[math]}$ hides behind it, does it? How to prove that? :)

→ Reply

boleyn.su

11 years ago, # ^ |

← Rev. 2 →

After reading the code again, I think it is O(n^1.5)

→ Reply

HellKitsune

11 years ago, # ^ |

To be honest, I have no idea how to prove it formally. :(

But informally, we will most likely achieve the highest number of iterations if for each point we minimize the difference between the number of points lying on the same horizontal and the same vertical line with it. It then only seems logical to assume that the worst case scenario for this algo would be when the points form a square, which would give us $\text{[math]}$ complexity.

→ Reply

Emettant

11 years ago, # ^ |

← Rev. 2 →

-8

True.

I got AC on your $\text{[math]}$ approach using unordered_set and got TL on $\text{[math]}$ using set.

Does $\text{[math]}$ makes such a big difference? Or is it constant behind C++ set implemenation?

However, author's approach has no unordered_set tricks. But I could not implement it.

→ Reply

11 years ago, # ^ |

Consider log N a factor of 20. It's a pretty good approximation.

→ Reply

Kianoosh

11 years ago, # |

Paper for problem D and harder versions of it!!!

Link

→ Reply

VArtem

11 years ago, # ^ |

Uhm, this paper is about checking if set of points contains desired figure, not about counting them.

→ Reply

caustique

11 years ago, # ^ |

← Rev. 3 →

But the algorithm can be easily used to count number of figures.

It's proved in the article that there's at most O(N^1.5) squares in the plane and existence of the square is checked using brute force over all possible candidates.

I used this article to solve this problem. Is there faster approach than O(N^1.5log(N))? log(N) is for checking if the point is in set and I think we can avoid that logarithm but what about better estimation than O(N^1.5)?

→ Reply

DanAlex

11 years ago, # |

← Rev. 2 →

How to solve B ? It was awsome. :)) But I did not get the idea.

→ Reply

ultimatemaster

11 years ago, # ^ |

← Rev. 2 →

Deleted.

→ Reply

DmitriyH

11 years ago, # ^ |

← Rev. 2 →

+14

n, m <= k : bruteforce by any possible first row
otherwise : freese one row and calculate min changes in case of this row is unchanged
6492596

→ Reply

RomaWhite

11 years ago, # ^ |

← Rev. 2 →

+26

If n>10 or m>10 there must be at least 1 line that does not change. Then iterate all such possible line. We know one line, so we know vertical partition of initial table and can easily find minimum number of changes.

If n<=10 and m<=10 iterate all possible first lines(2^m) and we know one line again.

→ Reply

DanAlex

11 years ago, # ^ |

+11

I observed that if you have a line fixed you can compute the answer, but I didn't noticed that. Now it seems kind of obvious. Thanks. :)

→ Reply

shopnobaj_raju

11 years ago, # ^ |

"If n>10 or m>10 there must be at least 1 line that does not change"-why?

→ Reply

Damon

11 years ago, # ^ |

because "k <= 10" !

→ Reply

marat.snowbear

11 years ago, # ^ |

because k <= 10 and you can't change more than k rows/columns.

→ Reply

Killever

11 years ago, # |

very strong pretests
low chance for hacks

→ Reply

Qalib_Sarayev

11 years ago, # |

when will the ratings be updated?

→ Reply

hball1st

11 years ago, # ^ |

soon

→ Reply

smallJS

11 years ago, # |

Div.1 B What about this case, what's the answer please? 3 4 10 1 0 1 1 0 0 1 1 1 1 1 1

→ Reply

johnathan79717

11 years ago, # ^ |

← Rev. 2 →

2, it can be turned to 1011 1011 1011

→ Reply

smallJS

11 years ago, # ^ |

what positions should be inversed ?

→ Reply

smallJS

11 years ago, # ^ |

Thx...

→ Reply

bcools91

11 years ago, # ^ |

← Rev. 2 →

Think about your number of rows, and try to figure out the answer from that! (Can odd rows be mirrored)

→ Reply

RedNextCentury

11 years ago, # ^ |

actually they are talking about div1 B not div2 B.

→ Reply

kcm1700

11 years ago, # |

I could not understand the problem C correctly until someone explained to me after the contest. a quote from the problem statement "the element of sequence a with the maximum index among the chosen ones must be equal to the element of sequence b with the maximum index among the chosen ones; remove the chosen elements from the sequences."

If the maximum indices of two chosen values are equal, it means you take same number of elements from the sequence, isn't it? Shouldn't the wording be "the index of sequence a with the maximum value" instead of "the element of sequence a with the maximum index"?

→ Reply

RomaWhite

11 years ago, # ^ |

This means that the last deleted elements must be same in both sequences.

→ Reply

kcm1700

11 years ago, # ^ |

Ah... I think I was just wrong. Thank you.

→ Reply

11 years ago, # ^ |

-8

What's wrong with removing the same number of elements from each sequence? It's a perfectly valid move.

But since taking any more elements than the equal ones seems to be a non-optimal strategy, "maximum value" should mean the same as "maximum index".

→ Reply

kcm1700

11 years ago, # ^ |

That's a clear explanation. I now understand the problem statement :) Thanks!

→ Reply

marat.snowbear

11 years ago, # ^ |

+61

Though I got it correctly during the contest I still don't see why it wasn't smth like: "both prefixes should end with same number", which is shorter and easier to understand. Sometimes formal language is too formal.

→ Reply

11 years ago, # ^ |

← Rev. 2 →

+60

Yes, I feel that sometimes problems on CodeForces are about deciphering the problem statement rather than understanding it and then having insights. Some authors also seem to be really into mathematical symbolic notation :)

→ Reply

vwxyz

11 years ago, # |

+10

why is rating update delayed?

→ Reply

korekhar

11 years ago, # ^ |

-60

Because it's going to be unrated!!!! hahahaha =)))))))

→ Reply

11 years ago, # ^ |

-13

That wasn't very funny, and that you needed to add your laughter at the end didn't help. I guess you're going to be downvoted.

→ Reply

marat.snowbear

11 years ago, # ^ |

Hey, glad you made it back to red.

→ Reply

Lazzaro

11 years ago, # |

← Rev. 2 →

What exactly is the special point of test 22 of Problem B(Div 2)? Many got WA.

→ Reply

11 years ago, # ^ |

← Rev. 2 →

You should check if n % 2 == 0 before each iteration.

Test:

You should output 3, but ouput 3 / 2 = 1.

→ Reply

pachon

11 years ago, # ^ |

← Rev. 2 →

my code works fine with that case, still don't know why WA on 22 :(

my submission](http://codeforces.me/contest/426/submission/6491099)

→ Reply

11 years ago, # ^ |

gives wa on your code

→ Reply

pachon

11 years ago, # ^ |

← Rev. 2 →

answer should be 1 right?

→ Reply

11 years ago, # ^ |

No, it should be 3. You cannot get 3 rows by mirroring one.

→ Reply

pachon

11 years ago, # ^ |

← Rev. 2 →

thank you very much, to correct something I forgot that part xD

→ Reply

.PEIN.

11 years ago, # ^ |

← Rev. 2 →

I think it's all 0's, shows a portion of 100 * 100 grid in the submissions page.

→ Reply

Prestige

11 years ago, # |

+10

Good round, thanks.

→ Reply

yxdb

11 years ago, # |

+14

The problems in div1 are pretty good except problem D. Problem D in div1 is so classic that so many people have solved it before (at least I knew several well-known OJs have problems almost the same). And its time limit is so tight I thought. I first used std::set but got TLE at pretest 13 several times. But I changed my code to use lower_bound in a sorted std::vector, I got accepted. That's why I thought its time limit is too tight somehow. Does anyone agree with me?

→ Reply

Swistakk

11 years ago, # ^ |

No, I don't agree with you. Using operations like lower_bound take log N complexity, so you got complexity O(n^3/2 log n) instead of O(n^3/2) so you shouldn't be surprised that you got TLE. Even more — tests weren't in fact maxtests. They could have been more time-demanding.

→ Reply