Topcoder Single Round Match 699 will be held on 26th September 15:00 PM UTC
Lets discuss the problems after the contest finished.
UPDATE: Editorial of the SRM
Topcoder Single Round Match 699 will be held on 26th September 15:00 PM UTC
Lets discuss the problems after the contest finished.
UPDATE: Editorial of the SRM
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
The contest will start in 7 hours.
Like previous SRM, this round has one sponsor: Cisco.
So if you want to discuss with people work there you can join them in the chat in Arena few hours before the contest. Details here: http://tco16.topcoder.com/tco16-sponsor-cisco-hiring-for-international-internship-program/
Auto comment: topic has been updated by shahidul_brur (previous revision, new revision, compare).
My codes and the main part of the editorial is at https://apps.topcoder.com/wiki/display/tc/SRM+699.
What do you think about n ≤ 40 in div1-easy?
What do you think about extremely weak examples in div1-hard? The goal was to show you that they are very weak (only the understanding of the problem was checked). With easier remaining problems we hoped that you will have enough time to test your hard. I don't imagine how someone would solve it without testing with brute force.
I think easy was harder than medium. Is there a simple solution without many cases?
UPD: Sorry, didn't notice the link.
I used a solution that considers very few cases, and I still think easy is harder than medium (consider a single bit -- the division between x[i] that have 1/0 in that bit is exactly the division between t[i] that have 1/0 in that bit, and you only have to choose which division is better).
But that's mostly not because easy is inappropriate for the spot, but because medium is. That being said, I'm happy that cgy tried giving an easier medium for a change, I was constantly solving only easy in SRMs...
I think that difficulty of easys significantly grew in half a year or sth. I recently have pretty often big problems with solving easy and for me that one was easier than typical easy in recent times. On the other hand my hards' acceptance rate #(AC/#contests) in last half a year seems to show that hards became more approachable, but I think that's ok given my usual easy-hard-medium order.
Thanks for the nice contest! Personally, I thought the 250 was more like a 300 and the 500 was more like a 450.
The hard problem was intense — I coded only first two cases(no overlapping + simple overlapping) and even that part of coding was wrong.
Someone passed 500 with Floyd-Warshall in my room and I losed 25 because of that :(
The link redirects me to Topcoder wiki login page. When I try to login with my Topcoder user I get only a confluence system error page.
I had the same problem . Logging in the main website https://www.topcoder.com and then opening the link,worked for me.
I solve easy in practice room with meet-in-the-middle on each bit :)
The editorial link is not working.
It took me time to code easy but I enjoyed working on both medium and easy. They were very interesting.
The test data of div1 500 is weak -- the first of my submitted solutions passes it (in practice room), but the mistake is quite obvious. I'm bad at finding the smallest value which is not equal to -1 in an array :)
With regard to that, I'm pretty surprised by only 27 official test cases in this problem. More test cases wouldn't have harmed, but would've helped to catch mistakes like mine.
I'm sorry for that.
So apparently none of my generators is likely to find a mistake in your solution. I'm sure that there are various easy and complicated types of tests on which your solution breaks but ofc. it's impossible to predict all kinds of small mistakes. I'm sure that more various generators would help but creating them was quite hard in this problem (still, I should have). I don't know if making even 4 times more tests with current generators would help (just with further experimenting with their parameters) — usually it doesn't affect the results. Still, I agree than 27 is a small number and increasing it 2-4 times would only help.
There was a similar problem with Div.1 Hard in my school contest before. But it's a rectangle version. XD
What's the intended solution for Div 2 1000 ?
Maybe the idea is the same as bruteforce one, but without storing the graph. I mean, if you have a vertex X you always can get all adjacent verteces in O(M)
BFS on N vertices. When you are in some vertex v, iterate over all M input pairs. For each pair (a[i], b[i]) if v is divisible by a[i] and this pair wasn't used before, iterate over all multiples of b[i] and add non-visited ones to the bfs queue. Also mark a pair (a[i], b[i]) as used. The total complexity is O(n·m).
Oh, I got it. Thanks a lot!
Hi , for div 2 500 i just used GP formula approach with error range of +-100 . http://ideone.com/NjEMww It failed on test case (837592744927492746) but on ideone it is giving correct answer ! Can any one please explain why ?
Don't write both a comment and a blog. Someone will answer you in one place and maybe someone else won't see it and will waste their time to answer you in the other place.
I have a question concerning the editorial for Div 1 Easy (https://apps.topcoder.com/wiki/display/tc/SRM+699). It says "If N is even, the xor of all x[i] is equal to the xor of all t[i]. If N is odd, the xor of all x[i] must be equal to 0." Would someone be willing to explain why this is true?