simp_pro's blog

NEED HELP: WA
By simp_pro, history, 2 years ago, In English

Problem link: https://codeforces.net/contest/1472/problem/E

Submission link: https://codeforces.net/contest/1472/submission/165709605

Tags help, wa
  • Vote: I like it
  • -21
  • Vote: I do not like it

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

I can't really understand what's the purpose of cj. a[i] != a[i - 1] is always true, because all pairs in a also contain their index in initial array.

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

    Probably got its meaning. You need to check if a[i].fi.fi != a[i - 1].fi.fi and also you don't need to always update cj. You also need to check if a[cj].fi.se > a[ci].fi.se when updating. I changed it in your code and it got accepted.

    165772947

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

      Why is this necessary? ci is always containing the least value so we can directly update cj to ci if we can. Can you provide some test case or argument why was this necessary?

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

        First of all, I need to ask you smth. Am I right, that cj contains the index of the smallest by width box that has height which is less (not less or equal, but less) than the current? (if we sort our boxes by height).

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yup, you are right, my bad. Checking whether ci is better than cj is not necessary.

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

          Yes, that's the correct meaning of cj. But why is your code giving AC but mine is giving WA?

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

            The point is that, as I said, that you are not really checking what you want. a[i] != a[i - 1] is always true, as a[i] is a tuple {h, w, id} and id is unique for every a[i]. You need to check that a[i - 1].h != a[i].h. I changed got so it does (and also added useless check a[cj].fi.se > a[ci].fi.se) and it got accepted.

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

    P.S: Please work on your codestyle :)

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

Alt of adityagamer?

→ Reply