chrome's blog

Topcoder Single Round Match 640
By chrome, 9 years ago, translation, In English

Hello everyone!

Today, at 20:00 MSK will be held Topcoder SRM 640.

Let's discuss problems after contest!

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

Comments Comments (16)
| Write comment?
»
9 years ago, # |
  Vote: I like it +89 Vote: I do not like it

Thank you for reminding me, you care about me more than TC : pp.

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

    To everyone who missed this SRM because of the reschedule: add the topcoder event calendar to your google calendar, then check "notify me one day before each event". This even sends out e-mails with your local time zone!

    TC emails have never been reliable, but at least Google has never failed me so far.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Hmm, I can't log in.

UPD: Now, I can. Match postponed by 1 hour.

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

According to topcoder event calendar SRM 640 was on sunday, glad I saw your post, thanx.

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

    Something's wrong with the old Topcoder theme events calendar. SRM 640 was on tuesday there some time ago but now it's messed up)
    Looks like new theme calendar is the only choice.

    → Reply
»
9 years ago, # |
  Vote: I like it -11 Vote: I do not like it

An hour delay. Looks like I've no chance to participate =(

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

This java application is the biggest shit that I ever seen.

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

I admit it, problem 550 div1 caused me to waste a lot of paper ,and in the end hasn't solved it!

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

    +1. I wonder how to practise the skills which are required to solve such problems and what the skills are. I tried so many ways to connect the edges and for each of them I realized (not always immediately) that it does not work.

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

      Well, the first thing I realized immediately (this grammatic construction is cool, it has 2 meanings :D): I can draw the first ans vertices on the left, on the right and connect the corresponding pairs.

      Next: one unmatched vertex has to be connected to d matched ones (it obviously can't be connected to unmatched ones), and we can connect all other unmatched vertices to these as well. That's one biclique on each side.

      Similarly, we can make these matched vertices into a biclique with their matching counterparts.

      There are some more steps, like splitting the matched vertices into 2 bicliques, where one of them has d vertices in each part and the other has ans - d, and each biclique has one part connected to n1 - ans / n2 - ans unmatched vertices, and then figuring out that we can make another biclique between 2 parts of these 2 bicliques, but it's hard to explain without pictures. The result is very simple, though.

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

I was very lucky in 550. I made 2 errors in formulas and 2 errors in thought process, but 3 of them "xored" to correct formula and fourth error turned out to be nondangerous xD.

I had sth like  - 2a·ans + 2a2 = a( - ans + a) and I forget to add all edges between two groups of vertices of a and b elements, but in my solution ans = a + b, so difference I made because of wrong formula resulted in having a·(ans - a) more edges and difference caused by forgetting those edges resulted in having ab less edges, but a·(ans - a) = ab, so it all cancelled xD. Moreover I thought that I need to search for a minimum value of quadratic function but I messed up signs and it turned out that it was completely unnessecary, because it was sufficient to check them only on boundaries :P.

But nevermind, got accepted and 6th place :D.

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

Right now, in the practice room on 1000:

Execution Time: 1.288s

Peak memory used: 67.543MB

The code execution time exceeded the 2.000 second time limit.

Uhh... what?

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

Hello,what is the approach to solve Div1 250?

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

    Remove edges between vertices with the same color and count a number of connected components. Subtract 1 and that's your answer.

    → Reply