I was being interviewed 4 hours ago and here it is.
Spoiler
The solution must be O(n) Time.
I was being interviewed 4 hours ago and here it is.
The solution must be O(n) Time.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3844 |
| 2 | Benq | 3792 |
| 3 | tourist | 3719 |
| 4 | VivaciousAubergine | 3647 |
| 5 | jiangly | 3616 |
| 6 | ksun48 | 3595 |
| 7 | Kevin114514 | 3491 |
| 8 | strapple | 3486 |
| 9 | Um_nik | 3376 |
| 10 | turmax | 3371 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Not quite convinced an $$$O(N)$$$ solution exists.
By the way, identical problem is already on Codeforces. https://mirror.codeforces.com/problemset/problem/526/F
.. and I know two solutions both of which are $$$O(N \ log \ N)$$$
The problem you mentioned is of 2900 rating and still its NlogN. I highly doubt google will ask such hard problems in phone interviews. As far as I know with my friends their questions revolves around div2 c,d and max e. mostly its c,d. Also in phone interviews their is a high change of geeting a seen leetcode problem.
about >= 2900 not appearing, you cannot be too sure, right? It's the Google! Considering the complexity of Code Jam, I doubt if their problems are mostly simple.
The only thing that shocks me is this kind of problem happens during a phone interview!!! Maybe he got on the interviewer's nerve, who knows :v !
Nope, he's right. Google interviews are lot easier than Code Jam problems. You can do a quick search for similar problems if you want. I'm not sure about problem ratings but it shouldn't be harder than Div1B in the worst case.
Source is da web, a few friends and my experience.
The $$$O(N\ log\ N)$$$ solution is considered 2900. The $$$O(N)$$$ solution could be considered a paper xD.
Who upvotes just by seeing red color?
This problem is one dimensional and the one in codeforces is 2 dimensional.
Anyway your $$$O(N log N)$$$ is like $$$O(sqrt(N) log (N))$$$ for this problem.
People didn't upvote because he's red. People upvote because he's correct.
A 2d NxN grid with N objects where no 2 objects share a row or column is the same thing as a 1d permutation.
Tip: someone with 800 rating points above you is likely to be correct, don't make such a bold claim without thinking.
My bad. I didn't read further after seeing NxN.
Apparently it is possible to do this in O(n):
Link to one Chinese blog post on this
Chinese slides on this
Can someone explain the main ideas in English?
So it's this all over again?
Can someone explain O(nlogn) approach for this problem?
Edit: The best explanation IMO : https://abitofcs.blogspot.com/2015/05/codeforces-526f-pudding-monsters.html