Topcoder SRM 736 - Codeforces

6 years ago, # ^ |

-15

If the problem had a catch that made it irreducible to "evaluate these formulas", sure. Like this, it's too easy. I found the iteration-based solution (while graph is valid and has > K vertices: remove 1 vertex, K-1 edges, if you got an invalid graph then the answer is ALL) almost immediately, told myself it can't be that easy and spent some time proving it, then converted it into an equivalent ternary search-based solution.

I feel like I missed the main point, wasted a lot of time being cautious and still solved it. Non-achievement complete, so to speak.

→ Reply

chemthan

6 years ago, # |

Hard is straightforward to use FFT. But I made a mistake in parsing polygon :(

→ Reply

6 years ago, # ^ |

+20

Well, at first I tried to do something in sympy because it's obvious that there is a closed formula

screenshot

→ Reply

Djok216

6 years ago, # ^ |

Oh, would you mind sharing the qwe.py file ?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+10

click

#!/usr/bin/python3

from sympy import *
i, j, c, k, n = symbols("i j c k n")

print(summation(((c * (n - i) - c * (c - 1) / 2) * (c * i + c * (c - 1) / 2) / 2 - (n * (c * i + c * (c - 1) / 2) - (i + c) * (i + c - 1) * (2 * (i + c) - 1) / 6 + i * (i - 1) * (2 * i - 1) / 6) / 2 - 
	  summation((i + k) * ((n - i - k) * (c - k) - (c - k) * (c - k - 1) / 2), (k, 0, c - 1))) * (2 ** (4 * n - c - 1) - 1), (c, 0, n - i - 1), (i, 0, n - 1)))

→ Reply

6 years ago, # ^ |

I don't know what is sympy, how it works and how you used it to this problem (I suppose you got AC hardcoding this formula after adding modulos?). Can you briefly explain it?

→ Reply

6 years ago, # ^ |

+11

I haven't got ac

You can read how to use sympy here. Very shortly, it works with variables like with variables, simplifies things, factorizes things, expands brackets et cetera.

I tried to do the following:

divide all 4n vertices into 4 groups as if we drew vertical and horizontal symmetry axis, enumerate vertices in each group from 1 to n, say, ccw.
our answer is (number of possible polygons) * (area of the whole polygon) minus $\text{[math]}$ (area of a subpolygon with vertices p[i], p[i + 1], ..., p[j]) * (count of polygons with edge i-j).
first, consider the case when these vertices are in the same group, the first of these multipliers is a sum of some polynomials which is foldable, the second is simply a power of 2 minus one, all this thing is foldable, as the screenshot approves.
two other cases weren't considered by me since I realized that I didn't have enough time

→ Reply

6 years ago, # ^ |

+10

It's just straightforward as it is, without any fancy stuff like FFT :P.

→ Reply

jqdai0815

6 years ago, # |

+20

Isn't the trick used in the hard problem a well-known trick in the rolling hash?

→ Reply

ivan100sic

6 years ago, # ^ |

+10

Yeah, that's how I did it, no need to use FFT

→ Reply

6 years ago, # ^ |

+14

Well, that is the trick that many contestants used. I must admit that I was not aware of such solution.

→ Reply

teja349

6 years ago, # ^ |

+11

Some link to the trick you are mentioning?

→ Reply

6 years ago, # ^ |

1234 = 123 * 10 + 4 is basically everything you need to know here. or maybe 72345 = (23456 - 6) / 10 + 7·10⁴. You want to evaluate such cyclical sums but in binarish system with digits x[1], ..., x[n]

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+13

I don't know if it's much of a trick, but I used the expression for area of a polygon $\text{[math]}$ as the sum of signed areas of triangles $\text{[math]}$ for i = 1..K (with cyclic indices) and an arbitrary origin point $\text{[math]}$ — point (0, 0) in my case. For the sum of areas of all subpolygons, we know that $\text{[math]}$ is an edge of 2^{j - 1 + 4N - k} subpolygons if k > j or of 2^{j - k - 1} subpolygons if j < k, because we have to omit all points from $\text{[math]}$ to $\text{[math]}$ and can include all other points in any such subpolygon.

We can write an area of a triangle $\text{[math]}$ in the form x_jy_k - x_ky_j, each of these 2 terms can be summed up separately for j < k and for j > k — there are 4 cases in total, I won't list out the exact formulae, but it can be simplified like $\text{[math]}$ , and this can be computed easily by adding up the sum $\text{[math]}$ and adding b_ks_k to the final answer. This works in linear time for an arbitrary polygon.

→ Reply

jqdai0815

6 years ago, # ^ |

+24

You can consider it in a much simpler way.

There is a string y₁, y₂, ..., y_n, y₁, y₂, ..., y_n, You want to compute something like $\text{[math]}$ . You can view it as the hash value of substring y_j, y_j + 1, ... in the base 2.

Then you can solve it if you know how to use the string hash technique.

→ Reply

6 years ago, # ^ |

-15

That's not simpler, you just omitted several "why?" and "how?" steps. There's no way reduction of geometry to hashing is simpler than writing down the basic formula and doing some arithmetic on it.

→ Reply

6 years ago, # ^ |

You can consider it in a much simpler way.

consider =/= reduce geometry to hashing

simpler [for understanding because of dealing with familiar concepts instead of writing stuff down]

→ Reply

6 years ago, # ^ |

If you want to focus on the word "consider", I'll just point out that one can consider basically anything. You can consider red-black tree balancing a trivial algorithm. You can also consider me the best competitive programmer in the world. So what?

One thing I notice quite a lot is that when I explain concepts I consider familiar in such a simpler way, people who haven't solved the problem (or solved it in a completely different way) don't follow... it turns out I often see these things as simple because I've put a lot more thought into them than what I describe afterwards. You can notice how a lot of scientific articles start with an "introduction" section that explains concepts which people for whom the rest of the article would be useful really should know — the same principle applies.

→ Reply

6 years ago, # ^ |

people who haven't solved the problem don't follow

I read "so basically we need to count something in this form", here I think for a second and realize that yes, something in this form, "which is actually a binary hash", and here I understand the point of view of the guy these words are written by. I know how your "don't-follow" model works, but in my opinion this isn't the case. I read your comment with some calculations and jqdai0815's comment and his one was simpler to understand for me, because I didn't need to dive into calculations and try to understand the logic behind them (even if you've described it). I've just read "hash" after $\text{[math]}$ and that's enough.

start with an "introduction" section

Do you mean abstract? It's not about concepts, it's more like a brief overview. Concepts are more about the "keywords" section.

→ Reply

6 years ago, # ^ |

No, I don't mean an abstract, I mean "section 1, introduction".

I think I'll be able to demonstrate my point if you explain in detail what's the sequence y_..., how to get from sum of areas of subpolygons to it and what's the index j in the sum. I'll ask further questions in that if necessary.

→ Reply

6 years ago, # ^ |

-10

That's the point, no need to explain what the sequence y is and other details. We're not talking about a complete description of some technique, and even if we were, how we apply it here doesn't have anything common with the technique itself. The question was what the technique is, not "please write an editorial using your solution here"

→ Reply

6 years ago, # ^ |

← Rev. 2 →

My first comment there wasn't "this is the trick", it was "idk about tricks, I solved it like this".

That's the point, no need to explain what the sequence y is and other details.

Someone asks you to explain something because it's not clear and you reply "no need"? What?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-10

Someone asks you to explain something because it's not clear

Don't see this.

My first comment there wasn't "this is the trick"

I didn't say a lot about your comment

Well, I feel that I wrote here the same things about 3 times, so I don't want to take part in this discussion anymore. I don't mind if you miss my point and remain like "that way with using common concepts instead of writing down calculations with a detailed explanation of how we came to them is not simpler to understand", I still don't share your opinion. And please don't ask me to describe someone else's comment in details just because. It has nothing with why that simpler-to-understand comment is here.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

I really can't see how someone can arrive at hashing a string as anything but a side note in my solution. Yes, when I look at my solution, I can see that there's a similarity, but jumping to the hashing idea without the same arithmetic I did? How?

Someone asks you to explain something because it's not clear

Don't see this.

You don't see that a solution that's clear to you might not be clear to someone else? Or you don't see not understanding something as the natural reason for asking you to explain it? No, your knowledge or opinions are not self-evident and you can't dismiss everything by acting as if they are. (Yes, you are acting like that.)

I didn't say a lot about your comment
The question was what the technique is, not "please write an editorial using your solution here"

That sounds like a jab at my first comment.

And please don't ask me to describe someone else's comment in details just because. It has nothing with why that simpler-to-understand comment is here.

No, it has everything to do with that. If it's easier for you to keep arguing (and go on a massive derail) why you shouldn't explain a solution in detail than to just do that, it's not simple. But ok, I can see that you're putting a lot of effort into talking about everything except the possible solution(s), so I won't waste my time.

→ Reply

6 years ago, # |

← Rev. 2 →

+26

Note: Graphs with introduced property of locally k-denseness is exactly complement of graphs widely known as (k-1)-degenerated

→ Reply

Heart_Blue

6 years ago, # |

← Rev. 2 →

I see the following code in the editorial.

vector<Field<998244353>> W(N, 1);

how to use Field, I google it, but cannot find anything

→ Reply

6 years ago, # ^ |

I wrote it myself. It was quite simple and I find it very convenient: link

→ Reply

neal

6 years ago, # |

← Rev. 2 →

+41

Thanks for writing majk! I enjoyed the problems, and I liked the difficulty distribution. The solve percentages in Div 1 this time were roughly 80% / 30% / 10%, which is much more reasonable than previous rounds.

I will say that N <= 500 on the 250 seemed unnecessarily high for the desired complexity of N³. Either N <= 300 or N <= 400 would have been better IMO. I saw a few N³ solutions that timed out, as well as others who went out of their way to implement the N² because they expected N³ to be too slow. My guess is it was set this high in order to stop N⁴ solutions from passing even with good constant factor (e.g., N choose 4). But 400 choose 4 is still 1.05 billion, which should be plenty; plus I don't think it's a huge issue if someone manages to spend a lot of time getting a heavily-optimized N⁴ to pass, as they won't get a great score anyway.

→ Reply

6 years ago, # ^ |

+23

Thanks!

Yes, I was also surprised to see so many people seeking $\text{[math]}$ time solutions. There are $\text{[math]}$ rotations, which is just over 20 million. That sounds doable, even if there are bunch of modular divisions. On the other hand, not even too optimised $\text{[math]}$ passes the TL with n = 350.

→ Reply

neal

6 years ago, # ^ |

+10

Could you share the code for the O(n⁴) solution you had in mind? I'm surprised to hear that it can run so fast.

→ Reply

6 years ago, # ^ |

+25

This runs 1.66 seconds for n = 350. Even without that optimisation by precomputing S[i] - '0' it takes just 2.02 seconds. Also note that the modulus in the main loop is not needed as quick maffs show this can not overflow.

→ Reply

Um_nik

6 years ago, # ^ |

+12

On the other hand, I've finished all three problems in under 45 minutes, and I wasn't the first one to do it. So for strong competitors coding phase ends somewhere in the middle of the contest, and then I should return to challenge phase after half an hour. It is not very convenient. Maybe with new arena (some day) TopCoder will have more than 3 problems in one round...

→ Reply