map's blog

Codeforces Beta Round #63 (Div. 2)
By map, 14 years ago, translation, In English

Hello!

Today I am the author of all tasks. At the contest you will be asked to help students from Chelyabinsk in solving their non-trivial problems.

I want to thank all those who helped me to prepare the round: Anton Garder for his invaluable assistance in the preparation of sets of tasks, Demid Kucherenko for assistance in the preparation of conditions, Artem Rakhov for coordinating the activities and patience J, Maria Belova for translating and  Mike Mirzayanov for a great system.

 Good luck!

Winner - Solo

Analysis - http://codeforces.me/blog/entry/1571

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

Comments Comments (47)
| Write comment?
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Good luck and have fun!
→ Reply
14 years ago, # |
  Vote: I like it +29 Vote: I do not like it
Just solved first problem from android powered mobile, although it took little bit extra time but at least provide me mobility :-)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the 4th test case for problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    for me, i was using a set instead of a multiset, maybe you did the same (or something concerning ordering?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I am sure I am handling the ordering. But you never know. Hope someone gives me the 4th test case to test on. Such a long implementation, only to find it fails. :/ 
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        All the test cases are available after system testing is finished.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Oh, cool. Didn't know CF makes all test cases available now. That's great.
          → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I just can't understand Problem D. For sample 1, "In the first test, Anton goes to the vector (1;2), and Dasha loses", why Dasha loses? Any explanation is appreciated.

Overall, I think it is a nice problemset, but the problem descriptions are not that good. E.g. problem B could be much more concise.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because Dasha, can't make any move according to the vectors (you don't have to check reflections at all -> see english analysis).
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Nice contest!
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I've really enjoyed this round.
Congrats on the excellent problem set..
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Nice contest! But I have made two STUPID mistakes :( In problem B, i have set initial min value to 1000 instead of 1001 :( And in E, i have forgotten to add line m[a[j]]++; - with these changes, all my code passes :( It's pity nobody hacked my B :(
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That's why div1 and div2 contestants write together in shared contests.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My idiot D solution wasn't hacked too.(in div 1 room)

      No matter
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        This is div2 contest - div1-participants have less motivation for getting points.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For C and this input:
1 1 2 2
a
b: a 2
c: a 1
1 a
1 a

Why is the answer:
1
c 2

We can make b since b needs 2 a's, and ally #1 has 2 a's. So I don't understand why the answer isn't:
1
b 1
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it
    Because after getting first 'a' you have to make artifact 'c'.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Why? The problem statement says:
      "It is guaranteed that after the i-th purchase no more than one opportunity to collect the composite artifact appears. If such an opportunity arose, the hero must take advantage of it."

      But if we make another a, then doesn't that mean that we had *more than one opportunity to collect the composite artiffact", which seems to contradict the problem statement?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        According to the statement: "If such an opportunity arose, the hero must take advantage of it." You must make 'c', and remove 'a' (all basic artifacts, used to make composite artifact, disappear). Then you have no 'a', you get second 'a' and have to make second 'c'.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yes, it seems I just didn't understand the problem statement, although I think it would have been much clearer if the statement I listed below in my reply to philolo1 would have been there.

          But anyway, thanks to the writer for a nice set, keep up the good work!
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    this is because the rule is, that you check after every purchase, whether you can build a component.
    So when we have a we build c. b will never be build.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it
      I don't see that rule in the problem statement. The only rule I see is the one  I just mentioned, which makes me think that the composite artifact can only be made once. Anyway, maybe I just didn't understand the problem statement, although I read it about 10 times.

      It would have been much clearer if they had said:

      "As soon as you purchase an item, you have to make whatever composite item you can (if any) at that point in time".


      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it
        But it is described here:
        "It is guaranteed that after the i-th purchase no more than one opportunity to collect the composite artifact appears. If such an opportunity arose, the hero must take advantage of it."
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          My whole point is that I didn't find that part of the statement very clear.
          → Reply
14 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it
What would the result be with these input?
For B:
4 4
1 4 20 10
1 4 20 5
3 3 4 30
3 4 4 20
and
4 4
1 4 20 5
1 4 20 10
3 3 4 30
3 4 4 20
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    70
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I found a program that outputs 60 for the second example , but didn't succeed the challenge.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes, answer for second example is 60. Sorry I missed your second example. So for first, it is 70, for second, 60.
        → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
How long does it usually take to update the ratings?
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
The problems were really made to suit div 2. Thanks to problem setters. 

But  problem statement D was  confusing for me. 
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And Of course handle of the today's problem setter is "map" :)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it
    did you watch indian film : "3 idiots"? And one of them takes after you! it's my own opinion. Our opinions can be non-intersected. But, if you didn't watch, I really recommend you!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Captain never sleep
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How do I see all the test cases for a problem? I tried in practice, and it only gives me a little of test case 4 for problem C, followed by "..."

Anyway to get the complete test case and expected output?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    now it's impossible
    but, maybe, it'll be possible soon, because the suggestions of that has been already told to СF administration
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh, someone told me earlier that test cases are available after systests.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I wonder why my solution in Python for problem 'E' is getting TLE. [ http://pastie.org/1701659 ]

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I've solved E using STL set and map. What is the best approach for this problem? Is there any good dp solution which don't use hash table?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Maybe, but it is harder...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I've solved E using segment tree.. wasted coding time.. LOL
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Unfortunately I missed the contest, but I enjoyed E so much. Thanks
→ Reply