nic11's blog

Topcoder SRM 620
By nic11, 11 years ago, translation, In English

Strange that nobody posted this, but on 10th of May, 20:00 MSK SRM 620 will take place

GL&HF?

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

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It coincides with TOKI14 run 2

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

Unable to parse markup [type=CF_MARKDOWN]

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it 
    required from ‘class std::vector<int, int>’ CandidatesSelectionEasy.cc:14:21: 
...
 error: ‘int’ is not a class, struct, or union type

    Казалось бы, действительно, int — так себе аллокатор.

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

    Me too so my score in 250 is low just discovered that function name is sort :D
    so I make another function outside it called SRT then i add sort function inside it :D
    actually I don't know why the writer use sort as a function name :( :(

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

      Good example showing that using namespace std is not an appropriate statement in C++ program developing (though almost every contestant does it)

      When you're going to use multiple libraries in some project, you will figure out that using namespace really harms your program

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

For Div2 500, I thought that for a solution to exist, c = pa + qb, d = ra + sb, should be satisfied where p,q,r,s are integers. So, after searching I came to know that Linear Diophantine Equation is related to this. How exactly can I solve this problem using the concept of linear diophantine eqn? I know that we can solve the same problem in different ways, but I want to know if it can be solved using this algorithm, as it was the first thing that came to my mind.

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

Any idea on Div1 800? I thought about some dp[i][j][k] = number of solutions given the parity of the columns (i = bitmask), the current line (j) and k = the current square free part of the product (k should be compressed). Didn't find a good way of compression or a fast enough recurrence. Am I on the right path or am I overlooking something? Thanks in advance.

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

    It's classic exercise for Gauss elimination.

    You have n2 variables, 2n rows to fix parity of number of selected numbers in each row/column and then we have one additional row for each prime number which occurs in the input.

    After you solve the system, you will either get contradiction or number of free variables. Answer is 2 to this number.

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

How to solve Div2 1000)?

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

    I have an idea, but I don't know if it's correct. I'll try to code it, and will post UPD with results

    Let's find the answer for n = 4 first. Now we can use inclusion-exclusion principle to calculate probability for at least one event (connected component with >= 4 verteces) happen.

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

    It is more convenient to answer the complementary question of what is the probability that all connected components are of size at most 3. This can be done with a one-dimensional dynamic programming with the state being the number of vertices. To build the transitions observe that there are only three possible choices for Vertex 1: it may be in a component by itself, it may be connected to exactly one other vertex and form a component with it or it can be in a component of size 3.

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

any idea for div1 500?

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

    We can use greedy algorithm, If some skill not contradict, we take this skill to sort. Take skills while it is possible. :)

    → Reply