shahidul_brur's blog

Topcoder Single Round Match 699
By shahidul_brur, history, 8 years ago, In English

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

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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/

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shahidul_brur (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +56 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    I think easy was harder than medium. Is there a simple solution without many cases?

    UPD: Sorry, didn't notice the link.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Thanks for the nice contest! Personally, I thought the 250 was more like a 300 and the 500 was more like a 450.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    The hard problem was intense — I coded only first two cases(no overlapping + simple overlapping) and even that part of coding was wrong.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Someone passed 500 with Floyd-Warshall in my room and I losed 25 because of that :(

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solve easy in practice room with meet-in-the-middle on each bit :)

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The editorial link is not working.

    → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It took me time to code easy but I enjoyed working on both medium and easy. They were very interesting.

→ Reply
»
8 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +43 Vote: I do not like it

There was a similar problem with Div.1 Hard in my school contest before. But it's a rectangle version. XD

→ Reply
»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What's the intended solution for Div 2 1000 ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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).

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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?

→ Reply