Topcoder SRM 762 - Codeforces

5 years ago, # |

The link of Stage 4 leaderboard is not working

→ Reply

justforlaugh

5 years ago, # |

+15

There is a typo. Should be 762 and not 761.

→ Reply

souradeep.99

5 years ago, # |

how to solve Strawberry?

→ Reply

dreamoon_love_AA

5 years ago, # ^ |

← Rev. 2 →

I guess it can be solved by polynomials polynomial multiplication with $$$O(n \times k \sqrt{k}))$$$.(reference: link from GeeksforGeeks)

But it definitely is not what the solution of writer...

→ Reply

nhho

5 years ago, # ^ |

+24

I solved with time complexity $$$\text{O}(nk^2)$$$. I guess it is not intended. The practice room system test shows that it passed in 4.9s while the TL is 5s.

→ Reply

saketh

5 years ago, # ^ |

← Rev. 2 →

+53

I tried to TLE you and got -25. :( Then my 250 failed from not seeing the length 200 constraint and now I am last place.

→ Reply

nhho

5 years ago, # ^ |

+18

I also tried to TLE another solution with the same time complexity since I don't believe mine will pass. Then got -25 as well. :)

→ Reply

falanga

5 years ago, # ^ |

+15

I got 5.0s in practice room

→ Reply

Slow_But_Determined

5 years ago, # ^ |

I tried hacking a couple of O(NK^2) solutions but they both failed :(

You can replace the inner dp with fft to get a runtime of O(N*Klog(K)).

→ Reply

saketh

5 years ago, # ^ |

How can you do FFT? $$$10^9 + 6 = 2 \cdot 500000003$$$.

→ Reply

https://github.com/the-tourist/algo/blob/master/numeric/fft.cpp

5 years ago, # ^ |

Well... tourist can help here

→ Reply

5 years ago, # ^ |

Just compute on doubles ;p

→ Reply

square1001

5 years ago, # ^ |

It could be non-obvious, but:

Calculate the convolution modulo $$$7 \cdot 2^{26} + 1, 5 \cdot 2^{25} + 1, 45 \cdot 2^{24} + 1$$$.
Use Garner's Algorithm to retrieve the value modulo $$$10^9 + 7$$$.

With my implementation with using Montgomery Reduction while multiplying in two modints, it passed in about 0.3 seconds in max testcase.

→ Reply

AnandOza

5 years ago, # ^ |

How were the three numbers in step 1 chosen?

Is the idea that the three numbers P, Q, R in step 1 are pairwise coprime, and that PQR is so large that the answer modulo PQR is equal to the actual value of the answer?

Or am I missing some relationship between P,Q,R and $$$10^9+7$$$?

→ Reply

square1001

5 years ago, # ^ |

Yeah, the idea is the same as you mentioned. Here is the condition

At least $$$PQR > (M-1)^2 \cdot N \simeq 1.4 \cdot 10^{22}$$$ should hold, because of the maximum possible value of after-convoluted value. So we need at least three integers if we use 32-bit.
I used the algorithm called Number Theoretic Transform (NTT). This only works in mod $$$p$$$ when $$$p$$$ is the prime of form $$$c \cdot 2^d + 1$$$ where $$$d$$$ is the least integer that is $$$2^d \geq N$$$.

→ Reply

5 years ago, # |

+57

I'll have a rant this time, for a change.

Div1 250 would have been a nicer problem with $$$n$$$ up to $$$200$$$. Test generators in the statement generally reduce problem interest, especially when the problem is not that hard.

Unintuitive and inconsistent test generators (state taken modulo $$$2^{31}$$$ after use in Div1 250, but before use in Div1 500) don't add value to the problemset. Combined with weak samples, they just add frustration for the contestants.

→ Reply

5 years ago, # ^ |

+30

Also in Div1 250:

We have to choose the lexicographically smallest sequence $$$B$$$, and only then prepend the length and return.
We have to reduce the length of $$$B$$$ to 200, but the returned length must be the original length.
There are no examples to check we got the above points right.

All in all, the problem is a minefield, and not in an interesting way.

→ Reply

square1001

5 years ago, # ^ |

But Div1 250 with $$$n \leq 200$$$ can be solved with a very easy $$$O(n^2)$$$ DP...

→ Reply

5 years ago, # ^ |

+26

Sure, but consider two scenarios:

Give the problem as it is.
Give it with $$$n \le 200$$$.

Is then contest in scenario 1 really better than in scenario 2 overall?

If the problem is that much more interesting when only the linear solution is allowed, the author may consider using it on a platform which fully supports it, without the generator in statement and without output truncation.

→ Reply

5 years ago, # ^ |

+26

The linear solution is the reason to have this problem. I'm sorry its beauty got spoiled by the workarounds needed for the platform. Honestly, I dislike having to do them as much as you all do and I really hope we'll finally get to use a decent backend soon.

→ Reply

5 years ago, # ^ |

+43

If you are using test generators, why not to give a big example?

→ Reply

5 years ago, # ^ |

+53

There should have been one, and it's a mistake that there wasn't one. Sorry.

→ Reply

5 years ago, # ^ |

I see how the problem is better when it's $$$O(n)$$$. Just, if the author is not locked into writing for TopCoder exclusively, they could use it elsewhere, and come up with another problem which suits TopCoder format better. There are many problems which lose little, if anything, when they are constrained in "olde TopCoder style", with $$$n$$$ up to 50 or so. Would be a win-win.

→ Reply

5 years ago, # ^ |

I wholeheartedly agree. It's very important to think which platform is best for your problem. Big constraints aren't good for Topcoder. If some statement is very long or it describes an existing process/game/whatever that some people know and some don't, it might be a good idea to use it in a long contest like the 10-day contest in Codechef. In Codechef, I also used some problem with local python interactor that was given to contestants and they could use it without hurry. Subtasks are good for OI-style competitions etc.

It's ofc. easier to distribute problems like that when having some experience but you should still try. In most platforms, it's ok if you just propose one problem btw.

→ Reply

Coder

5 years ago, # ^ |

I think 250 was ok if big example test was provided (but you may have made a mistake in your solution that made you dislike it compared to others), we have seen similar output format before even long time ago.

500 was not ok though. I would buy this "educational" thing a bit if TopCoder was producing any education content (with FFT tutorial for example). But they haven't produced any new content in ages, so better stick with what is common knowledge in Algorithms.

→ Reply

justforlaugh

5 years ago, # |

The missing constraint that the resulting array should have positive integers is an important part of the Div 2 500 problem. It took me a while to figure out what to do with elements that were not included in the restriction and lost some points. Though I earned 250 points for challenging other solutions.

→ Reply

ainta

5 years ago, # |

+52

Wow, return only first 201 elements. What a great technology!

→ Reply

justforlaugh

5 years ago, # ^ |

+23

TC has not change since 2005 LOL

→ Reply

Xellos

5 years ago, # ^ |

-18

Still a better system than Boeing MCAS.

→ Reply

dreamoon_love_AA

5 years ago, # |

+10

After submitting the Div.1 250 pt, I recall that I forget the constraint that we need to just return the first 200 elements as what I do in TCO 18 round 4.

And in the challenge phase, I get 200 points from others by bug about this constraint...

I think the constraint is terrible and affect final rank too much.

→ Reply

5 years ago, # ^ |

Oh no

→ Reply

5 years ago, # |

-35

I was writer for the 5 problems (apart from Div1 Hard). I am sorry for many things. I think this is lowest I have ever felt with my mistakes in preparing tasks.

Firstly Div1 Med,

I should probably have stuck to NTT instead of Karatsuba, But we felt NTT might be harder for people so we went with Karatsuba. And I as a stupid compared times of both my Java n*k*k solution and n*k^1.6 and felt it was fine(instead of using an optimised C++ solution).

Now, Div1 Easy, I missed the condition (Aprefix.length < = n)in checkData, which sadly no one noticed. (:

Hope you liked the questions. Thanks for participating!

→ Reply

5 years ago, # ^ |

+73

Why do you want to set such a straightforward Karatsuba/NTT problem?

→ Reply

5 years ago, # ^ |

-65

You are not the target group for the problem. People who are now learning the technique are. From time to time, straightforward $technique problems are needed for all techniques, so that other people can learn and practice the stuff you already know. If all the problems on $technique use it in complex ways, it makes learning harder.

If you already know it well, the problem should have been straightforward for you to give you more time to try to solve the hard.

→ Reply

5 years ago, # ^ |

+76

OK. So maybe I can send such problems to TC:

given two polynomials, output their product.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-26

That's unfair, and you know it.

This is nowhere near the same situation. Here you still had to do the correct modeling of the process described in the statement, discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately. In order to do that, you need to understand what the algorithm actually does instead of just blindly using a black box.

→ Reply

5 years ago, # ^ |

+163

bad problem for topcoder: multiply two polynomials

good problem for topcoder: generate using given generators two polynomials and after that multiply them

→ Reply

MazzForces

5 years ago, # ^ |

+12

And then print the xor of the coefficients, I think u forgot this

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+10

probably some formula with long long overflow in it instead of xor will suit more.

of course, without any examples on it.

→ Reply

5 years ago, # ^ |

+18

return the length then min(200, size) elements in it XD

→ Reply

ko_osaga

5 years ago, # ^ |

← Rev. 2 →

+56

discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately

This sounds very silly, and I think one doesn't need to be red to think as such. I agree the modeling is nontrivial, but it's still straightforward.

However, I liked the Hard. Thanks to Errichto for a nice problem.

→ Reply

rng_58

5 years ago, # ^ |

+136

I agree that this problem requires some observation. At least we first need to find $$$O(nk^2)$$$ solution (which is d2 hard), and also need to understand that the transition is of the same form as convolutions. Still, we need to compare the ratio between technical parts and observation parts. We can say that a problem with level 1 known technique and level 2 observation is good, but a problem with level 10 known technique and level 3 observation is completely straightforward. I believe 90% of the difficulty of this problem comes from FFT with arbitrary modulo (which is more advanced than a simple FFT) and thus I don't see much difference from sunset's exaggeration.
I also agree that problems that (almost) directly ask the knowledge of advanced techniques are valuable for educational purpose. However, please don't put them in rated d1 contests. There are other places for them — online judges, CF edu rounds, ABCs, etc. (personally I try to make ARCs more idea-oriented.) Speeds on d1 meds have great impact for reds too. What's the main factor of the speed in this problem? Preparedness of your pre-written FFT. (Do you have NTT or just double FFT? or you have a code for arbitrary modulo? Do you have Karatuba instead?) It's not interesting if the ratings of reds are greatly affected that way.

→ Reply

5 years ago, # ^ |

-56

I do not know if I can say it was straightforward NTT (maybe for you it was very obivous). I felt it was a good problem for the Div1 Med level (only some 35 odd people did it (even in them I think there are few optimised bruteforces which passed.)). why do you think if someone found it to be straightforward, try to write optimised bruteforce?

→ Reply

darnley

5 years ago, # ^ |

+14

Because 17 * 7k * 7k = 833m, and you gave us 5 seconds.

Assuming the author is not that good at setting TLs (which turned out to be true), it seemed reasonable to consider this problem just an exercise on modular arithmetics and dp with probabilities, something like a 450-pointer to move on to the hard problem.

If you wanted only a o(n*k*k) solution, you definitely needed larger limits.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+20

Its not 7k, but 14k?

Anyways, I surely agree it was my mistake as I said above.

→ Reply

darnley

5 years ago, # ^ |

+21

Yep, my fault. And still we see both C++ and Java solutions with no smart optimizations passing in 5s.

→ Reply

5 years ago, # ^ |

+13

Cheer up. Mistakes happen. We can use the experience, and ask ourselves how to improve the process so that they can't happen next time, or at least are less likely to happen.

→ Reply

5 years ago, # ^ |

+69

I think a lot of issues would be easier to avoid with some changes made by Topcoder. Changes that we need to wait for. I would like to see better problem setting software where an author can and should have a lot of solutions, not just one in Java. Validator tests would be nice too. Or let's just use Polygon and export problems to TC from there :D

And I'm a fan of platforms with different types of contests. CF can use less interesting (more standard and thus educational) problems in Edu rounds, Atcoder has ARC for that. I agree with misof that problems like this one should exist, but experienced competitors don't want to see them in main contests of any platform (SRM for Topcoder, div1+2 round for CF). It hurts much more in case of Topcoder because of a small number of problems in a round.

→ Reply