kostka's blog

By kostka, 17 months ago, In English

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

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

| Write comment?
»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Yes

»
17 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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

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

Why is it so hard ?

»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

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

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

      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
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to construct s using strings p,q

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

          now that you have pair from p and q in a multiset, you can traverse through s and check what character you should put in answer string for that character in s. here is my implementation.

          https://p.ip.fi/-w-i

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

    How to solve with Flows?

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

      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.

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

    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.

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

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

      Solution
»
17 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
17 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

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

    Can you explain how the answer is of that form?

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

      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.

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

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

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

          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.

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

        How to solve problem A ?

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

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

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

        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.

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

      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
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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.

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

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

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

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

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

      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 :(

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

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

    Spoiler
»
17 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

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

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.

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

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

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

      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?"

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

        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.

»
17 months ago, # |
  Vote: I like it +15 Vote: I do not like it

for me A was harder than D.

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

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)

»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

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

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

    C was just some recursion .

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

      your rank is just +3 of mine :)

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

        Any tips for a beginner, it was my first time..

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

          Try CSES problemset and Atcoder Beginner Contest , your skills will improve exponentially with time.

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

        Yeah , It wasn't a good Kickstart for me , :( , but still it's fine .

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

    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.

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

      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.

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

        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.

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

          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.

»
17 months ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

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.

»
17 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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