Блог пользователя kostka

Автор kostka, 3 года назад, По-английски

Join our online coding competition and tackle fun problems designed by Google engineers! ➡️g.co/kickstart

Round E starts in less than 12 hours (on August 22nd at 03:30 UTC).

  • Проголосовать: нравится
  • +82
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Yes

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Why am I getting TLE for problem A for an O(1) solution.

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Why is it so hard ?

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Who else solved problem A (Shuffled Anagrams) using max flow?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    What kinda overkill is this, I got ac with O(n^2) algo

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Edit : It is same to the analysis solution.

      Ok I will share my nlogn solution to A as I can't see any better approach than O(n*n) in this blog. This solution can be made to work even in On with some optimisations which I won't discuss, but will give hints to :P

      Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to solve with Flows?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      Let $$$c$$$ be the maximum of unique characters ($$$c = 26$$$ in our case). Create a graph with $$$n = c + c + 2$$$ vertices (assume $$$0$$$-indexed). Let $$$\text{source} = 0$$$ and $$$\text{sink} = c + c + 1$$$.

      For every character $$$\text{a, b,...,z}$$$ create two nodes $$$2 \cdot i + 1$$$ and $$$2 \cdot i + 2$$$ (nodes from $$$1$$$ to $$$2 \cdot c$$$). here $$$i =$$$ rank of character. i.e. $$$0$$$ for $$$\text{a}$$$, $$$1$$$ for $$$\text{b}$$$,..., $$$25$$$ for $$$\text{z}$$$.

      Add an edge of capacity equal to the frequency of that character from $$$\text{source}$$$ to particular character on the left side ($$$2 \cdot i + 1$$$).

      Add an edge of capacity equal to the frequency of that character from character to the right ($$$2 \cdot j + 2$$$) to $$$\text{sink}$$$.

      Add an edge between characters from left ($$$2 \cdot i + 1$$$) and right ($$$2 \cdot j + 2$$$) of capacity $$$\infty$$$ iff they are not equal ($$$i \neq j$$$).

      if the maximum flow is $$$< |S|$$$ then answer is $$$\text{IMPOSSIBLE}$$$.

      If maximum flow is $$$= |S|$$$ then you can easily construct any valid anagram using the flow passing through each edge.

      Link of the code for more details.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, me.

    I was unable to find a proper greedy. So, I had to use it. I had never implement flows correctly before in a contest (iirc) and using it in A made me more reluctant but still, it went smooth for two green ticks (tho I had 2 penalties trying to find a proper greedy :( ).

    BTW it would be good if you could explain the time complexity. I thought it was higher degree polynomial time.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      My greedy solution. Not sure how O(n^2) didnt get TLE tho.

      Solution
»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Dude what the heck was that difficulty curve?? For me, B was the hardest problem.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Solution for the problem D "Increasing Sequence Card Game" test set 3 (N > 10^6): https://www.quora.com/What-is-the-sum-of-the-series-1+-1-2-+-1-3-+-1-4-+-1-5-up-to-infinity-How-can-it-be-calculated

It was by far the easiest problem of them all. Which awarded the largest amount of points.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how the answer is of that form?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Just implemented a simple straightforward bruteforce solution for N <= 10 and looked at the results:

      Spoiler

      Based on these results, it's obvious that the answer is 1 + 1/2 + 1/3 + ... + 1/N. And this makes it a pure math problem, which is generic enough to be searchable on the Internet.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Wow, really need this kind of observation skills by looking at result. :))

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          It's not just looking at the result alone. For N=1, the answer is 1. Then if we add one more card, it can go either to one side of the deck or to the other side and thus adds 1/2 to the expected score, making the formula 1 + 1/2. Next looking at N=3, we can see that ~0.3333333333 gets added to the answer and makes it 1 + 1/2 + 1/3. Further checking cases N=4,5,6,... confirms that this pattern continues. The top rated answer from quora provided the $$$H_n=ln(n)+0.5772156649$$$ approximation for large $$$n$$$ and it does the job. Here's a link to my submissions for this contest.

          Looking at the editorial, appears that the expected solution was supposed to be a bit more complicated.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        How to solve problem A ?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Just open one of the solution. You’ll learn more than from pure answer. If you’ve got WA its probably because for string like ‘abc’ you are doing ‘ba’ and can’t put ‘c’.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's always dangerous to say that something is obvious. You should try to prove if you think you found a pattern. For this problem I think there may be a simple proof by induction. I demonstrated in other way by first solving test set2 with dp and then replacing the dp definition of the previous states.

        As an example of how this kind of thinking may mislead you, I give you the following classical problem find the Maximal number of regions obtained by joining n points around a circle by straight lines. The sequence starts with 1, 2, 4, 8, 16, ... So it's obvious that the next number is 32? But it's actually 31 A000127.

        Many times the attempt to prove that your assumption is true may lead you discover that you were wrong and save you time implementing the wrong solution.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      Using Errichto "contribution Technique" — The $$$i^{th}$$$ card from the top will have contribution in the final answer $$$<=>$$$ all previous card appeared are smaller than it. and probability of this is $$$1/(n-i+1)$$$. So you just need to do $$$\sum_{I=1}^{i=n}1/i$$$

      Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Easy for those who could find the appropriate link by googling...nightmare for others !!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Not really. You could code O(n^2) solution for test n = 10. And observe that dp[i] depends on sum of dp[1:n-1] and you could precalculate with accumulator. This would make your solution linear and n = 1e6 would pass.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I tried doing problem C(Palindromic Crossword) using some dfs kind algorithm(I stored nearest blockages for each row and column) and kept getting runtime error, can someone point out the mistake in my logic? Thanks link: https://pastebin.com/Xx3KHbGU

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Try to run it for a 1000x1000 grid filled with '.'

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks man, turns out I was not setting the columns in result grid and was trying to access columns without setting them, it was a stupid mistake :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I did that too. I calculated horizontal and vertical palindrome equivalent positions of each non blocked cell.

    Spoiler
»
3 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

I have a much different solution to $$$D$$$ that allows for a more general statement that makes the problem slightly more interesting (and definitely harder).

Using one-indexing, if we try to find the number of times card $$$i$$$ is at position $$$j$$$ and ends up in the final hand, we find that this number is $$${i-1 \choose j-1}(j-1)! (N-j)!$$$. In short, this is choosing $$$j$$$ cards lower than $$$i$$$ and placing them in front of position $$$j$$$, then permuting everything but card $$$i$$$ and position $$$j$$$. To find the total number of times a single card $$$i$$$ is in the final hand, sum over all positions $$$j$$$ and expand. This nets you $$$\sum_{j \le i} \frac{(i-1)!}{(i-j)!(j-1)!} (j-1)! (N-j)!$$$. Simplify to get $$$(i-1)!\sum_{j \le i} \frac{(N-j)!}{(i-j)!}$$$. Notice that the subtraction of numerator and denominator removes $$$j$$$ from the summation, so we can try turning the fraction into a binomial coefficient. $$$(i-1)! (N-i)! \sum_{j \le i} \frac{(N-j)!}{(i-j)! (N-i)!} \rightarrow (i-1)! (N-i)! \sum_{j \le i} {N-j \choose i-j} \rightarrow (i-1)! (N-i)! {N \choose i-1}$$$ where the last transformation is by a binomial identity. Simplifying this expression trivially we, we find that the contribution is exactly $$$\frac{N!}{N-i+1}$$$, but the entire expression will be divided by $$$N!$$$ so the contribution to the expected value of card $$$i$$$ is exactly $$$\frac{1}{N-i+1}$$$

The problem could have given a set $$$S$$$ and asked to find the expected value of the intersection between the final hand and $$$S$$$ or, if you want to keep the $$$H_n$$$ approximation, you can ask for the intersection between the final hand and all cards not in $$$S$$$. Even so, it's easily bruteforceable if one knows about the linearity of expectation, but the statement no longer screams to be brute forced.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for last problem Why I was getting WA for 3rd test case when I was trying to solve this recurrence $$$f(n)=f(n-1)+1/n$$$ by matrix exponentiation.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Matrix expo allows for adding $$$constant \cdot n$$$, not $$$ constant / n$$$. Either you made a breakthrough or your matrix doesn't make sense :D

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

      Thanks! I was not aware of it and wasted hours. Can you please provide any reference or some reason for "why it doesn't work with double?"

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        It works with doubles. You can add 0.3*n. It doesn't support division. Because how you would do that? You choose matrix coefficients and they get multiplied by something, not divided.

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

for me A was harder than D.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

For D problem, I found a solution easier than analysis solution. Suppose that we found answer for n-1 (base case is n=1 which is 1). Think all of the permutations from n-1, increase every number with 1. Now, we should just insert 1 into somewhere into them, there are two cases: 1. Insert 1 at the beginning, it gives us (n-1)!, because there are (n-1)! permutations. 2. Insert 1 at anywhere expect the beginning, it won't be included in any increasing subsequence. So it gives us for every answer from n-1, (n-1) times of it + from the first case there is 1 more f(n-1) too. So f(n)/n! = (f(n-1) / (n-1)!) * n + (n-1)! / n! = f(n-1) + 1/n. Then for n <= 1e6, brute force, otherwise use formula for harmonic sums, which is f(n) = ln(n + 1) + (Euler–Mascheroni constant =~ 0.5772). (edit: fixed plagiarism)

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

It was a nice round! I secured rank 1085 in it

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is C some form of a well-known problem ? I noticed a lot of people do C but fail at D.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    C was just some recursion .

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just as the editorial explains in the "Test Set 2" part, it's a graph problem. I solved it by constructing an adjacency list and then doing DFS. Relatively few participants submitted a partial solution only for Test Set 1 and this makes sense, because it's actually easier to treat it as a graph rather than doing something ad-hoc.

    I think that Codeforces offers awfully few graph problems among Div2A-Div2D, so I recommend participating in AtCoder beginner/regular contests to improve your skills at solving this stuff.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why ad-hoc? I don't think a lot of people solved it as a graph problem. It's a usual board/matrix problem which is more common/simple. You can save all # indexes in a row/column and traverse them with your board and get next jump in constant time or make [up/down/left/right]-matrices, or [horizontal/vertical]-matrices and do the same. Bfs — or — dfs, doesn't really matter. This approaches seem more common and widely used to me then graphes, not something special or ad-hoc.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I checked your solution and it looks like you essentially used a fancy problem-specific data structure for storing and retrieving information about graph edges instead of something more conventional. I used a plain and boring adjacency list in my solution. The other differences are pretty much cosmetic/insignificant. As for which approach is more simple, I would say that mine probably better followed the teakettle principle and it was a more reliable way to get a guaranteed result (even at the cost of more lines of code).

        In my opinion, we both solved it as a graph problem. You may disagree, but that's similar to saying "it's not a graph, it's Takahashi's kingdom with towns and roads". Graph is a useful abstraction with useful properties and useful algorithms. Sometimes graph edges are given to us directly as a part of input data. But in this particular problem C, it was a graph with a little bit of disguise.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          IDK, maybe. We really can find a lot of graph abstractions around. Maybe it's just hard for me to call anything a graph problem if it doesn't involve working with path's, cycles, flows and dijkstra-bellman-ford-floyd-warshall things.

          PS. Oh, now I've got it, your adjacency list is not cells with common edge — it is cells which must have same letter in it. Yep, got it.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +25 Проголосовать: не нравится

For me is a wonderful contest experience, although terrible at first.

At first I failed both problem A and B from time to time, and cannot pass a single test set in the first 1 hour 10 minutes. You can imagine how desperate I was when contest pass almost half and my score was zero!

Then I pass the small test set for problem B, and then problem C (A typical DFS problem), my ranking rise from 2000+ to 600+, then I pass problem D due to my clever observation, and my current ranking rise to 250+.

Finally I look back on problem A, first I use brute force to pass small test set to guarantee 4 points, then I pass large test set 8 minutes till the end of the contest.

My final score is 87/100, with the ranking 205, which is the highest ranking of all times. So guys, never give up until last minute in competitive programming.

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

For anyone interested, here's a link to my screencast. I've also recorded solution explanations at this link.