Topcoder SRM 704

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Before contest

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

15:34:12

Register now »

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

15:34:12

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3797 |

2 | Benq | 3618 |

3 | Radewoosh | 3525 |

4 | Miracle03 | 3460 |

5 | ecnerwala | 3419 |

6 | Petr | 3408 |

7 | peehs_moorhsum | 3384 |

8 | ksun48 | 3377 |

9 | ko_osaga | 3352 |

10 | maroonrk | 3344 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 205 |

3 | Um_nik | 196 |

4 | Errichto | 182 |

5 | awoo | 179 |

6 | sus | 177 |

7 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | -is-this-fft- | 170 |

10 | SecondThread | 167 |

Topcoder SRM 704

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/28/2021 02:00:48 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I cannot login to arena.topcoder.com and this is the only way I can compete.

Does anyone has the same problem?

I got a login page, and then I tried to log in. Now, I'm getting never-ending redirections on https://www.topcoder.com/my-dashboard and https://accounts.topcoder.com/#/member?retUrl=https%3A%2F%2Fwww.topcoder.com%2Fmy-dashboard%2F. Therefore, I can't browse TopCoder's website anymore.

Are you getting the same problem ?

Yes, exactly the same.

Same problem but you can access the arena. Click. But I think this works only if you are already signed in.

Update: this round will start in 16 hours.

Topcoder have an unusual method of submission. It is very difficult use

Just learn it, It will become the easiest service you will ever use for CP.

Take a look: fusharblog.com/apps/testerdream/

or if you prefer

That is why you topped coding round?

Because I don't like TC Arena :P? I don't think disliking Arena was the most important factor xD.

Why we can't change handle in new year in topcoder ?. Admin of topcoder please enable this.

Just mail them.

How to solve Div1 B?

I think it's DP. dp[pos][gcd(current product, K)]. DP for n — 1 elements. The last element will be chosen!

Could you please explain more on your approach? It seems to be very different from what I saw in solutions of various coders (mostly used CRT).

K has at most ~ 1000 divisors. So total state is at most 50 * 1000. Assume

gcd(a_{1}*a_{2}* ... *a_{n - 1},K) =r. Thena_{n}will only depend on r and v.What is the difference between D1 300 and AGC 5 problem C?

Well here you have to actually provide tree, so it is harder?

Harder? By returning string("yes/no") instead of tree itself? xD.

I mean the other way around, here being the topcoder round, sorry for ambiguity :)

no no no, i understood u, i meant for me these problems r equal and i think i would solve atcoders's problem the same way as todays toproder's problem.

Is there a problem with div2 medium because all solutions in my room failed system test ?

Yes there was an announcement of this.

How to solve Div2 C ???

I had an idea using inclusion-exclusion as the number of divisors of numbers uptil 100 would be very small. Didn't have enough time to code it up.

Is there an alternate solution?

Didn't try this but i think this might work .

DP[i][j] — number of sequences of length i whose product mod k is j .

can be computed using matrix exponentiation i think .

Length can reach 10^9 !

convert this into matrix obviously . that's why i mentioned matrix exponentiation .

Here, your biggest hint is that

nis very big andkis small. Keep an answer array ofkvalues, the number of ways you can form 0, 1 2, etc so far (modk). Now, to compute it for a certainn, you find the matrix you need to multiply it by to transformnton+ 1 (actually, you need to construct this matrix in your program since it depends onk), and exponentiate this matrix and multiply it by the initial answer array(should be just 1's). It'sO(k^{3}logn)can you explain more clearly? i didn't understand ...

How to solve div2. C?

So there was an issue with div1 systest also? i was 110th after 1 systest, but after resystest i became 100th.

That's because people who failed systests have their score wrong(see negative scores). I went from 82nd to 73rd :D

That's because people who failed systest get negative score instead of zero ;)

I can't join SRM because I'm busy in today, but it seem that I lost big chance to up my rating. (I'm writer of AGC005, and actually Problem C is constructing problem first, so I have source code to constructing ... XD)

Is it rated?

i think it will be!

Actually D1 300 is completely the same as problem D of NEERC Western 2014 (except data range is 50 instead of 100000.)

This does indeed appear true, here is link to the solution of somebody to that problem, however does anybody have link to full set of problems from that contest, and / or a place to submit? I can only find standings, not problems.

https://github.com/zimpha/acm-icpc/blob/master/archived/2014-NEERC-Western/problems.pdf

Lol thanks, I somehow missed this in the repository that I linked to :)

Edit: I guess we can also thank zimpha for this, if he had competed in TC round today I am sure he would have done well.

When I try to log in at arena.topcoder.com, I am redirected to topcoder.com/my-dashboard, which redirects me back to arena.topcoder.com :D This circular dependency is not allowing me to login :(

Is any one else facing the same issue?

Login into topcoder.com first. Then hit arena.topcoder.com

I can't login to topcoder.com. It has the same issue.

I use google login. No issue for me.

I mean, I can't even see the main page.

Erase the cookies from topcoder

Doesn't help for chrome, but managed to get inside with internet explorer.

If they are reading comments here, I'll leave the detailed

Browser infoHow to solve Div1 500?

http://codeforces.com/blog/entry/48850?#comment-333916. It passed.

Let

K=p_{1}^{e1}...p_{s}^{es}. The answer to the problem is just the product of answers to the prime factors (CRT) so WLOGK=p^{e}.Observation: if and . then answer for

v=xandv=yis exactly the same.So we just want to compute how many

n-tuples has product divisible by exactlyp^{f}.Consider the polynomial

W(x) = (p^{e}-p^{e - 1})x^{0}+ (p^{e - 1}-p^{e - 2})x^{1}+ ... + (p- 1)x^{e - 1}+x^{e}.i.e. coefficient at

k-th power ofxis number of remainders from [0,p^{e}) which are divisible exactly byp^{k}.Now what we want is just more or less

W(x)^{n}, (powers greater than x^e should be replaced by x^e). Now if andp^{f + 1}doesn't, the answer isf-th coefficient ofW(x)^{n}divided by (p^{e - f}-p^{e - f - 1}).Can you clarify a bit more: for instance, K = p

_{1}*p_{2}, how do we combine solutions a_{1}*a_{2}*...*a_{n}= v mod p_{1}and b_{1}*b_{2*}...*b_{n}= v mod p_{2}to get solution for K?I understand the CRT part and how you got the polynomial. Can you please elaborate on the part after it? How exactly is the polynomial used in finding the final answer?

Thanks.

Actually, (following the notation,) when

f<e, the answer iswhich finishes all cases

v≠ 0. The casev= 0 can be then computed.How to solve Div1 300?

https://en.wikipedia.org/wiki/Centered_tree says a tree is either centered or bicentered (with adjacent centers)

Besides that, all I can think of is a brute force approach. When we need to place a node of eccentricity e, try all possibilities of nodes of e-1 and place the node where it does not affect the eccentricity of already placed nodes.

You have the center, it is the node/nodes of minimum eccentricity (there can be only 2 centers at most). Now about the ones that have eccentricity higher you can note a couple of things:

They always come in frequencies of 2 or more. Why is this? Think about the point where the excentricity is max. There's a path that's the maximum path and it obviously ends in a leaf so you can note that this leaf also has maximum eccentricity. For the ones in the middle of the path you can think the same way, just note that the maximum length path goes through the center.

A point closer to the center has lower eccentricity.

Now to construct the graph just order the input, if there are 2 centers you connect them and connect the vertices to some vertex that has a immediatelly inferior eccentricity making sure that there are at least 2 branches while checking if there's a number with freq<=1 (that means it is impossible). Check if this is a real answer (the numbers could be higher than possible for example) and it's done.

There seems to be still some issues on the results. Result

According to this result, everyone doesn't get decreased on their total scores, even if they got Failed System Test. Also I can guess rating is calculated by this wrong result. (See 40th place filip.bartek. His total score should be -25pts overall, but his rating is increased by 290.)

You are right, I was wondering how my rating went down, and this somewhat explains it, failed submissions are apparently as good as correct ones these days! If I had known I would have submitted the 500 and 900 for max points and had my rating go through the roof!

You have to pass Challenge Phase though!

You are right, I suppose I would not have. Also here is link to the results in the Algorithm Browser. And the one challenge that Swistakk had was so unfortunate :(

Yes, we are looking into it.

Sorry for the issue, it was caused by my mistake (there is a bug in checkData() for Div2-Medium, so someone submitted an invalid test case in challenge phase.)

This should now be corrected, just waiting on cache to expire so it shows up properly online :)

Some people still have got points for their submission after system test fail and hence rating increase. :3