PikMike's blog

By PikMike, history, 2 months ago, translation, In English,

1036A - Function Height

Tutorial
Solution (Vovuh)

1036B - Diagonal Walking v.2

Tutorial
Solution (Vovuh)

1036C - Classy Numbers

Tutorial
Solution with combinatorics (PikMike)
Solution with precalc (PikMike)

1036D - Vasya and Arrays

Tutorial
Solution (Ajosteen)

1036E - Covered Points

Tutorial
Solution (PikMike)

1036F - Relatively Prime Powers

Tutorial
Solution (PikMike)

1036G - Sources and Sinks

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it  
  • +44
  • Vote: I do not like it  

»
2 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

I found a strange thing in F. Two ACs codes output different result. Detail in https://codeforces.com/blog/entry/61728. Can anyone help me?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone prove the author's solution for B?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    i thought about this problem lot after the contest.

    what i came up with is that there is 8 cases for m,n,k: odd/odd/odd, odd/odd/even....even/even/even. all cases reduce down to the odd/odd/odd case or the even/even/even case. we can see that it is possible to solve the odd/odd/odd or even/even/even case using all diagonal moves as long as m,n is reachable in k moves.

    for an example of "reduction", the even/odd/odd case reduces to the even/even/even case because you can "spend" one non-diagonal move in the n-direction. [1]

    the author's solution is basically "reducing" down all cases to o/o/o or e/e/e cases with mod. see my coded sol here: 42690270

    [1] in fact, the o/o/o case reduces down to the e/e/e case by spending 1 diagonal move

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can change the problem to this: you should use 1/-1/0 k times totally to get m and n respectively.(remember that m and n are nothing to do with) And according to the problem and greedy algorithm the num of 1/-1 should be as much as possible.

    for m we should at least use 1 m times and if k<m then it is impossible to get to (m,n) if k==m then for m we are done if k>m then we can add the combination of (1 and -1), then the left (m-k)%2(1 or none) should be 0. for n we do the same.

    so now for m and n, the num of 0 should be at least (m-k)%2 and (n-k)%2 respectively. And for the 0 in m, we must use a 1/-1 in n to construct a valid move (0,1) or (0,-1), the same for n. at last there are (m-k)%2+(n-k)%2 moves not diagonal, so the answer is k-(m-k)%2-(n-k)%2.

»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Randomized solution for problem G: here

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cool.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    I will try to explain why this solution works: obviously (unless I missed some bug of course, but from conceptual standpoint the solution seems pretty sound), the solution in question can make only one type of mistake: answer "YES" when the actual answer is "NO".

    When the answer is "NO"? When there is at least one "bad" permutation of numbers from 1 to k. I will show that in this cases there are actually a lot more bad permutations than just one. Indeed, consider the set X from the editorial.

    To explain the main idea lets consider the simplest case when |X| = |f(X)|. Then any permutation that matches elements of X only with elements of f(X) and matches elements {1, 2, ..., k} - X with elements {1, 2, ..., k} - f(X) is a bad permutation: when doing a graph walk starting with some source in X, we will never leave reach any source not from X. Therefore there is at least |X|!(k - |X|)! ≥ [k / 2]![(k + 1) / 2]! bad permutations.

    To deal with the case |f(X)| < |X|, we will take some subset Y of X with size |f(X)|, then and we can similarly show that all permutations that match sources from Y to sinks in f(X) and sources not from Y to sinks not from f(X) are bad permutations. Therefore there is at least |Y|!(k - |Y|)! ≥ [k / 2]![(k + 1) / 2]! bad permutations.

    All in all, if there is one bad permutation, there are at least [k / 2]![(k + 1) / 2]! of them. So the probability of finding a bad permutation randomly is at least in the worst case of k = 20. From the other hand, on my computer, the code in question checks random permutations before timing out. In the end, the probability of failure is something of the order  ≈ 10 - 8, which is good enough.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cool

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasted 1 hour trying to solve a harder version of Problem C. I thought classy numbers were those number which had the number of distinct non zero digits <= 3. And when TC 2 and 3 were not passing, I tried so hard debugging.

After successfully wasting 1 hour, read the question again and BAM!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The data for G maybe too weak? I can easily hack my code.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

The problem A is so easy, but I solved it late because of my poor English and my poor wi-fi.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, Can anyone please give proof of why exactly GCD + 1 value will give integer co-ordinates?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[Deleted]

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/1036/submission/42706346 can someone pls point out the mistake i am making. upd :: got it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem G, it is possible to find for every sources all achievable sinks in a linear time. For this it is necessary to store in each visited vertex an integer (the set of bits of achievable sinks).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the approach behind recursion in problem C?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem F be solved with some precalculations (generations of correct numbers), simular to problem C?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain classy numbers editorial ??

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

there is a easy way to solve problem C with DP :) 42742195

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems to be an interesting approach, but I don't really understand it. Could you please explain it briefly?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      f(i,j) means The i th bit of a number(unit's digit,ten's digit...) and already has j non-zero digits.

      DP uses flag to control upper bound.If it is not the upper bound,we can remember the result of f(x,y).(That's why I initialize f to -1 and update f(x,y) when flag=0).f(x,y) will be accessed multiple times, so we can speed it up by remember it .

      My English is poor( I use the google translate QAQ ).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.I can't understand about how (!flag&&~f[x][y]) works,what's mean ?it's mean if f[x][y] has been calculated ,then return f[x][y]? to be honest i want to use pinyin.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why dont we use -C instead of C? I read in internet that the formula will use -C instead of C? I mean this fragment: long long dx = det(l1.C, l1.B, l2.C, l2.B); long long dy = det(l1.A, l1.C, l2.A, l2.C);

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    By the properties of determinant det(-a, b, -c, d) = det(a, -b, c, -d) = -det(a, b, c, d)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh it is used then when he does: x = -dx / d; y = -dy / d; right?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is Problem A tagged with FFT ? Is there a solution with FFT as well ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

very very good~ !!

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

E has a tag "fft". Can it be done using FFT too? If yes, then how?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem 1036E — Covered Points , can anybody explain what's special with the test 14? I've seen some people failing this test.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain how mobius function could be used in problem F. All I understood is that we are trying to remove the bad elements from the answer. Basically, could someone explain me the formula?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem G, how about a 4-vertex graph: 1->2, 3->2, 3->4 ??? It's obvious that 1 is a source but the set of sink it can reach is just {2}???

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a proof for problem b ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the brute force generation for C