IlyaCk's blog

Problems A and G from SEERC
By IlyaCk, 13 years ago, translation, In English
Problem A statement (eng.) https://docs.google.com/document/pub?id=1ie3NIzfcXYPbvmUrj9VW112nwkdnWj2eKw-3gVRGT98

Problem G statement (eng.) https://docs.google.com/document/pub?id=1gvx2yZ7O-L0SeY0VOQD4R4rmPjrWXhnx6KuvOS5yPio

Explains for A and G (eng., укр. -- Ukrainian text is just translation of English text) https://docs.google.com/viewer?a=v&pid=explorer&srcid=1f3XsMQ_4mKzL05Gqpo38LiV8Kantw_Oc4PuZrZ4qJI3GmU_itLo-6M71xIAx

Statements may vary slightly from the final, distributed directly on the competition. For example, just at the contest I saw on paper phrase "zoom ration" (???), though in the older (this) version it was "zoom ratio", as it should be.

I'm interested in feedback on these tasks, because I prepared them (of course, special thanks to Ukrainian methodical commission who helped me much).

Particulary, I'm very interested that the problem G was solved, and it is rumored that a significant part of solutions principally differs from my solution. Vasyl[Alphacom] (Vasyl Biletsky) told me few words about how to use RMQ here; but, alas, yesterday I realized that misunderstood him :(
  • Vote: I like it
  • -1
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I liked problem A. Is there a chance it will be available on an online judge? I had a different idea from yours and I'm curious wether it would TLE or not.

In problem G I think the part "which is strictly better by any one property and not worse by another" was unnecessarily complicated and led to a lot of WAs. Also one of my teams used the first idea from the solution and the got WA instead of TLE.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Unfortunately, I have no own on-line judge ;) Speaking more seriously -- I need to receive permissions from official SEERC judges and from somebody who have on-line judge.

    One more aspect is that so happened that I sent tests, and some time after made some small, non-principal changes, and sent changed tests. I don't know exactly which of them were finally officially used. AFAIK, both tests sets are correct, but... I don't want to say "these are the same problems with the same tests" when I'm not sure.

    "complicated part" -- well, I'm listening to propositions how could I formulate it better. I did not want to use programming-language expressions or mathematical expressions which are too alike to programming-language ones.

    What do you mean by "the first idea"? Ignoring possibility of different propositions with the same number of pixels and the same zoom ratio? But if so, why do you wonder it was WA?

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      "which is strictly better by any one property and not worse by another" to me says, that I can have either (>, >=) or (>=, >). Maybe simply going for one case (>, >) or (>=, >=) would have been better - but also easier, which maybe you wanted to avoid.

      If I understood correctly, they stored the cameras in a set, found the upper end of the region by one criteria (pixels or zoom) by lower_bound, then iterated over every element in the region and chose the ones with the appropriate value from the other criteria.
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        (sorry for using word "propositions" in previous post, it should be read as "offers")

        I still think that criterion "either (>, >=) or (>=, >)" was a good choice.

        (>=,>=) -- surely no. It's unnatural to prohibit different offers of the same model (equal both pixels number and zoom ratio), so I did not want to do it just for simplify the problem. And it's extremely unnatural to say that such offers makes this model outdated.

        Considering "outdated iff (>,>)" -- principally possible, but as far as I can see,  complicates a lot my solution, and (as I found just now, after contest) makes practically impossible solution posted (in Russian) in this blog by Fcdkbear. (not sure)

        About the last paragraph of your post -- I'll try to reply you later. If anyone else can reply smth clever -- you are welcomed to join discussion.

        Maybe tests published at acm.ro will be helpful. But, from other side, I can click on the link "All problems including input and output data", but download doesnot actually start... Maybe we need to wait. It was a temporary problem, some minutes later I downloaded them at good speed.

        → Reply