arius1408's blog

Need help on an USACO 2021 problem
By arius1408, history, 3 years ago, In English

Well, I've been trying to solve this problem from USACO January Bronze Division. I think this is a LIS-related problem, so I tried using Dilworth's theorem. The thing is, even if I can calculate the length of the longest anti-chain according to the Cowphabet sequence (using binary search like any other LIS problem), I keep getting these annoying Wrong Answers ... Can you tell me where did a make a mistake ? I can't even figure out under what circumstance my approach would fail, but apparently it seem to be a false solution.

P/S : Yep, this problem can be solved using an O(N^2) approach, but I'm trying to do it with a O(NlogN) ... Anyway, help pls.

EDIT: Uh, and just to clarify, by LIS i mean Longest Increasing Subsequence.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The following is my simple lookup-table based solution of the problem.

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

My solution in python.

# Uddered but not Herd

cowphabet = input()
cowphabet = list(cowphabet)
string = input()

times = 1

for i in range(1, len(string)):
    if cowphabet.index(string[i-1]) >= cowphabet.index(string[i]):
        times+=1
        
print(times)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you sure that's O(N)?

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

      index() method runs in linear time.

      So it's O(N^2).

      Thanks.

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

This is a USACO Bronze problem, which means it is solvable without the use of any advanced algorithms or challenging mathematics; just basic implementation and some logical thinking. If you are thinking about LISs and Dilworth's Theorem, this is a clear indicator that you have seriously overcomplicated the problem. (General lesson: always keep in mind the difficulty level of a problem when thinking about how to solve it.)

There is a very simple $$$O(n)$$$ solution described at the bottom of the official editorial. The basic idea is to just try to hum each character in the input one by one, and, whenever we have to "go backwards" in the cowphabet, we have to increase the answer by 1.

Hope that helps.

→ Reply