ashmelev's blog

Codeforces Beta Round #66
By ashmelev, 14 years ago, translation, In English
Good afternoon!

Authors of the today's contest are Evgeny Lazarev (Nizhny Novgorod STU) and me (Alexey Shmelev, Nizhny Novgorod SU)

Today you will help a boy Vasya find himself in the world of computer games.

Please note, that the round will be held in unusual format - 6 problems with costs 500, 1000, 1000, 1500, 1500 and 2000 points.
 

The round duration is increased to 2 hours and 30 minutes.


We say thanks to Marya Belova for statements translations, Artem Rakhov and Alexander Kouprin for help in contest preparation, writing alternative solutions and preparing of intricate tests.

Good luck and successful submission!

UPD: We apologize for inaccuracy in problem E and incorrect answers to several contestant clarifications.

Announcement of Codeforces Beta Round 66
  • Vote: I like it
  • +61
  • Vote: I do not like it

Comments Comments (123)
| Write comment?
14 years ago, # |
  Vote: I like it -9 Vote: I do not like it
Good luck to everybody!
→ Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Nice, I like more problems.
→ Reply
14 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
Maybe an English version would be good, I think something like extending the time limit of the contest is worth translating ...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Google's translation:

    Good day! 

    The authors of today's contest are Yevgeny Lazarev (Nizhny Novgorod State Technical University) and I (Alex Shmelev, Nizhny Novgorod State University) 

    Today you will help the boy Basil corientirovatsya in the virtual world of computer games. 

    Please note that the round will take place in non-standard format - 6 objectives of 500, 1000, 1000, 1500, 1500 and 2000 points. 

    Due to changes in the number of task duration of a round increased to 2 hours and 30 minutes. 

    We are grateful to Maria Belova for translation conditions, Artem Rakhiv and Alexander Kuprin for assistance in the preparation of tasks, writing and creating alternative solutions to tricky tests. 

    Good luck and successful delivery of solutions!
    → Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
"Today you will help a boy Vasya find himself in the world of computer games."

Has he lost himself in the world of computer games?
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Oh,No!
I forget to register.

Anyway, Good Luck All.
→ Reply
14 years ago, # |
  Vote: I like it +17 Vote: I do not like it
Why system test hasn't been started yet?

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This is of course a biased opinion since my round went poorly, but I think that the change of statement of problem E midway through the contest should make this round unrated.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it
    Обычно раунды Codeforces делают нерейтинговыми при наличии более серьезных проблем. Если администрация все же решит поддержать это предложение, предлагаю это сделать в такой форме. Создать кнопочку: "Да, проблемы с задачей E сильно повлияли на мой результат, прошу сделать этот раунд нерейтинговым лично для меня". На большинство участников эти проблемы не повлияли, и по умолчанию для остальных раунд останется рейтинговым.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it
      Наташ, а кнопочки для задачи D не будет? :)
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      Yes, that's fine with me, too.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      Да, согласен. Я потратил где-то полчаса, пытаясь понять, где ошибка в моём решении. Более того, перед отправкой я задал вопрос: "Может ли Вася использовать информацию, которую он получил при просмотре некого режима, для открытия нового режима?" -- и получил ответ "Да", так что даже не было сомнений, что я мог понять условие неправильно.
      Но вариант голосования здесь вполне уместен, поскольку действительно повлияло это на очень немногих участников.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Еще раз приношу свои извинения.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Отличный раунд))) Пусть задачи шли не совсем по порядку, но с условием лично у меня проблем не было.. Сейчас читая сильно удивлен что раунд хотят сделать не рейтинговым...
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      лишнее..
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Trouble with problem E affected a minority of coders, though mostly tops.

    An alternative proposal:
    First, ask coders whether they want to be rated this time.
    After the voting is over, run the system test.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      No rate it or unrate it thoroughly.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    How about changing tests, so that they are consistent with original statement? Then if the solution passes first or second set of tests, it is accepted.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What to do with hacks then?
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Simulate everything again but don't change points for hacks.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You know how to solve first understanding?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I don't know, but if there is any coder who solved it, there is no problem. If not, then it's no sense to do the whole operation.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes. Except for some corner cases, a must contain all primes up to x-1.
        If a contains all primes, you can choose mode i that satisfies a[i] == 2 first,　so the answer is at most 2.

        But the problem is that this understanding don't match examples.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Did you mean pretests? It works fine for the examples.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it
            Yes, pretests.

            (I sent a clarification and decided to solve D first while waiting for the answer of the clarification, so I wasn't affected during the match.)
            → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Use a_i=2 first, then you only have at most 2 variants left, requiring you to make one more turn. Thus if answer is not -1 it's equal to 2 in most cases (except a_i=1, x = 2 or x = 3).
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    As I can see (please, fix me if I am wrong) the solutions for both statement meaning (before and after clarification) looks very similar and use same approaches. From the other hand, there were solutions only from two persons who passed pretest 1-4 which do not distinguish different understandings. The first test which has different answers for two understandings is 5. I repeat: only two participants made submissions which have WA on test 5.

    After the clarification it looks it was not difficult to change the solution according new information. So, I believe that the issue in this problem is significantly affected only two persons. We ignored their attempts submitted before clarification and moved their OK solutions to the time of the first attempts.

    Yes, possibly, it will be better to give a choice for participant in similar cases to decide if round should be unrated for them. But anyway it should be done before system testing.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I couldn't solve the first understanding in about 10 minutes, and solved the second one immediately, so I think that this issue has affected me significantly.

      If you knew that the second interpretation is solvable, why did you opt for changing the problem instead of changing the testcases?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        As we know some people understood the problem correctly without clarification. Also, unfortunally, as I know the problem author wasn't around computer.

        Petr, sorry again about this issue.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For problem E, is it only possible if you take the set of prime numbers (unless of cource, the number 1 is in set A)? I cant prove this :S.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes.

    You have to find all the divisors for the numbers 2..x-1. You can safely ignore all the composite numbers, as their divisors will be already present for smaller numbers.

    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes. If the number p, which we are trying to guess, is prime, it can only be distinguished from p+1 if we have p in the set.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well, system test has been started now.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
system testing now.. so will this match rated ?
→ Reply
14 years ago, # |
  Vote: I like it +29 Vote: I do not like it
Lots of people seem to have WA on test 62 on D. Any clarifications about that?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    No one solved it yet, it seems the test case is broken.
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it
      Gassa has "Accepted". It seems the test case is OK, but test #62 is difficult. 
      Sorry, I've wrote it before rejudge.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    I think WA#62 means "accepted" with high probability =)

    let's waiting for rejudge
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    retesting...
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Finally, some accepted solutions on Problem D...
      Only one for Problem F :)

      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Problem D, has accepted solutions now.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hi,

    For problem D, for the testcase:

    100 0 1

    Why is the answer 98 instead of 49?

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Because when you build a new road, two provinces become the only one province, limited with only K tunnels.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Even if you group the nodes in pairs, each pair will be a separate component, so you can add only one tunnel to each (which, of course, makes it impossible to connect the graph)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Argh, this is so wasted. If I took note of that condition I would have solved the problem :S.

        Ah well, thanks for your clarifications!
        → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Same question about test 33 for problem F (although there it may well be true that all solutions are wrong).
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    There is one solution got "Accepted" (solution by Rizvanov).
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I see you have passed this test in upsolving. Do you agree with jury answer now?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Yes, I do.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Ok, thanks!
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          hi man , your problems were nice
          i have a question , do you write any editorial for this contest or not ?
          if yes it is russian or english ?
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I have wrote russian editorial. I'm going to translate it within the next few days.
            → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Rejudge on problem D has just started.
→ Reply
14 years ago, # |
  Vote: I like it +40 Vote: I do not like it
Will this match rated or not?
→ Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
I'd like to support the opinion on making this round not rated.

I was not affected with ambiguities in E, it just hasn't occured to me that it would make any difference. Being less clever is sometimes good.

However, I was affected with two other issues:

1) In problem E, pretest 4 had n = 0 and had no second line at all. According to the statement, there must always be a second line. It costed me 5 extra submits and 25 minutes of lost time. Once I figured out that the problem is in input, I asked a question and I was answered that pretest 4 is okay (which is wrong).

2) This was already raised by KhaustovPavel in russian. In problem D, it is not explained whether the term "province" is static or dynamic. In other words, if we add an edge between two provinces, will it be one larger province or still two smaller ones? People say that the sentence "Maybe he'll have first to build several roads between cities in different provinces to merge the provinces" clarifies this. I can agree that it attempts to clarify the issue, but I do not agree that it clarifies that. Note that in russian version "unite" is used instead of "merge", which makes it even easier to understand the statement improperly.

Overall, it seems that emphasis in this particular round was made on having a lot of challenges. For example, pretests on D and E are pretty weak. I have nothing against such approach, but that should not come at cost of problem statements clarity.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It least Russian statement clearly says that you create road "to unite this provinces"
    About E - I think it is pertty unique. Submissions should certainly be redjudged, but I think it is not enough for unrated
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      "Unite" in the terms of province, or in the terms of connection? Anyway, why author didn't include such cases in pretests?
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      What's so clear about that? Is "unite provinces" something that can be understood in unique way? I don't see anything wrong with understanding "make them reachable from each other via roads". I think even merge is much better than unite (but I read russian version unfortunately during the match), though still far from ideal wording.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I do not know, for me it is clear and I can't get how to understand it in the way you understood
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          There was a 10% chance to understand the statement improperly. I'm really frustrated. Because for me there is no difference which variant to solve, I've got AC after the round. Just one more value to store in heap.
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Since, as I see, it was decided to rate the match (at least my rating has been changed), I'd like to ask admins to add the second line into pretest 4, problem E (and other test cases, where appropriate), and to retest all submissions.

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I do not think anyone solution depends on last empty line. For example, as I see your first attempts was incorrect for n=0. Please, give me submission-id of your or anyone attemp that should pass test [n=0,two lines] but didn't pass [n=0 in the only line].
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I read second line (Java, readLine() of BufferedReader) and then parse it. If there's no line at all, readLine() returns null and attempt to parse it results in runtime error. If there's an empty line, it works fine.

        I'm pretty sure that my first submit (374644) is correct, given that testcases are formatted correctly. I haven't changed anything except input.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thank you for taking care of the issue!
        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          Appeal granted :) Sorry for the issue. I checked all the submissions failed on test#4 and found that your solution is unique which failed because of missing empty line.
          → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it
Admin please respond. We will leave our desk only after knowing whether this round will go rated or not :P

→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it
It's not good, if 5-7 people tell, that they failed this contest because of...., and so all other people won't get their rating change
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Could someone explain what is wrong my code for A:
we have the formula (1+x1)*(1+x2)*(1+x3)
where xn is the cut in the xn koordinate
I iterate over all x1
and do simple calculus for for the maximum value of (1+x2)(1+x3)
f(x2)= (1+x2)(1+k-x1-x2)
f:(x2) = 1+k-x1-x2-1-x2=k-x1-2x2
maximum : (x1-k)/-2

Code in :http://www.ideone.com/yZIqi
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What if the sides are not big enough to have that many cuts?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      x1=[0..k]
      x2=(x1-k)/-2=(k-x1)/2
      x3 =k-x1-x2
      They cannot become to big
      x1+x2+x3=k, this property holds for all values of x1, I think.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        I meant, let's say you have x,y,z (given dimensions of the cube) and x2 >= y or x3 >= z. In that case you cannot make x2 cuts from the side of y.
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Seems like the match has been rated!
    → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
When will editorial come?
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it
Hi. 
I noticed that the input of problem B test 18 is wrong.
There is no new line before "Vasya's racer nick".


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    I think I am affected by the same issue.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What was the approach for B? 
      I tried this: 
      First sort them in decreasing rank and lets say vasya's rank is R. Now for highest position we add the biggest points at position R and next at R-1 and so on. then  sort them again and find the required rank. 
      And for lowest position we add the highest points at position R+1 and next at R+2 and so on. Sort them and find the required rank.

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

        sorry, deleted

        → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        In the highest: what happens with positions 1..R-1 (Assuming that you wanted to say that you add the biggest point value for R than R+1 and so on...)? Also something simillar shoud be done in the lowest case.
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Yes! It's sad but true, thank you. I'd just modified code to check if input line contains something beyond m int numers and got AC now.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Me too affected by this bug in the test case
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It's not a bug. There is no information that the name should be in a separate line.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It is said that "The last line contains Vasya's racer nick.". Yes, it can be interpreted that the nick can be on a separate line or on a line with points, but the problem's statement should be coincise and should not allow any ambiguities.
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Seems that test 18 has been fixed. Problem B rejudged. Thanks admins!
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it
    (deleted)
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    (deleted)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oops sorry for repeating comments. There was some problems with my browser.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    I has changed problem testdata. Now it contains an empty line in case of m=0. I rejudged submissions which was failed on tests (18, 21, 23, 28). Some of them passed system test. Sorry for this issue. It is one more minus for contest writers :(
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it
      Why did you change correct test cases, so that I have worse rating? I disagree with this, because tests were correct and you made a rejudge.
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        These tests were incorrect. There were no empty line while statement said it should be.
        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          Input

          The first line contains number n (1 ≤ n ≤ 105) — number of racers. Each of the next n lines contains si and ai — nick of the racer (nonempty string, which consist of no more than 20 lowercase Latin letters) and the racer's points (0 ≤ ai ≤ 106). Racers are given in the arbitrary order.

          The next line contains the number m (0 ≤ m ≤ n). Then m nonnegative integer numbers bi follow. i-th number is equal to amount of points for the i-th awarded place (0 ≤ bi ≤ 106).

          The last line contains Vasya's racer nick.


          It means there should be at least n+2 lines with Vasya's racer name after m numbers, nothing more. And the tests were correct! If you are changing correct test cases, then maybe you could also change tests for A, with k <= 10^6, so that my solution passes :/ 

          → Reply
          • 14 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it
            Looks like russian and english versions of statement were slightly different=( In Russian version it is said that "ith integer in the following line is equal to ammount of points..." while in English version there is no word about additional line.
            So considering russian statement these tests were incorect as they omitted blank line after m=0.
            → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, any accepted solution remained accepted. I think some users which solution has been accepted after rejudge moved in front of you in the standings. You took 207th place, solved problems B and C and I think it is resonably that you loose some rating poins (-16).
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it -19 Vote: I do not like it
          Maybe it is, maybe it isn't. I didn't notice point values and started with B, thinking it was easier. I didn't notice in problem C that c could be < 0. If I noticed these 2 things I would be in first 100 and had orange colour. Now you are changing correct test cases and some competitors became red, for the cost of my rating. It's their lost that they didn't notice the fact, that Vasya's name doesn't have to be in a separate line. Move me to the first 100 and it will be ok...
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            "The last line contains Vasya's racer nick."
            This is a cite from English statement.
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Case 1#:
              23 34 Vasya
              Case 2#
              23 34
              Vasya


              In case 1 first line is the last line, whilst in case 2 second line is the last line.

              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it +16 Vote: I do not like it
                It's a demagogy.
                I agree that there were several ill-written phrases in today statements, but this time all is correct. In English when you say: the first line contains a and the last line contains b, it generally means that this data is the only data it contains. Following your point of view we can add tons of garbage in every test for every problem because there is no phrase that we shouldn't. Can you imagine test for a+b problem: "sdfa 123414 sd  fa 23". Doesn't it look unnatural?
                → Reply
        • 14 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          Ok, nvm, lets wait for the next contest :)
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
please explain problem D to me.
why for sample #3: "4 0 2" , output is 1, i think it must be 0, because we can add tunnel (1,2), (2,3), (3,4). it's hold the limit for k because for each province at most k tunnel connected to it.
sorry for very poor english!
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    No, we can't. In your example there are 2 tunnels from cities 2 and 3.
    Tunnels are undirected so (1,2) and (2,3) both are counted as tunnels from city 2.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thanks for your answer but i still dont understand why my graph is'nt correct because for city 2 there are two tunnel that connected to it, and the value of k is 2, so i think it's correct.
      where is my mistake?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Statement claims that no town can be connected by more than one tunnel. k is a limit for tunnels from province, not a single town.
        → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it
(deleted)
→ Reply
14 years ago, # |
  Vote: I like it +34 Vote: I do not like it
I think there should be one easier problem.. We got 6 problems and the easiest was still difficult.. You can see so many contestant got 0.. This is all division round, not div 1 only round..
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can not see why some keywords (in, out, get, last, map, from, next, exit, ...) are highlighted in the Java source code viewer!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am puzzled with problem D , if the case is :
5 13
2 3 5 7 11
I think the answer is -1, because 12 and 13 cannot be distinguished. But the answer is 5.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If ai=2 then 12 items will be displayed on 6 pages, but 13 items will be displayed on 7 pages.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi, 
I'm trying to solve problem C with this simple DP:
f(n, m, c) = 0, if n = 0
                  value[v[n-1]][c] + f(n - 1, m, v[n-1]), if m = 0
                  max(value[x][c] + f(n - 1, m - (1 if x != v[n-1], 0 otherwise), x)) for all letter x, otherwise
Where n is the size of the string, m is the number of remaining changes, c is the next letter, v[i] is the i-th letter and value[x][y] is the bonus of xy. However, this DP gives WA on test 45, which is a bunch of negative values. Can anyone spot the flaw?
Thanks.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
why the answer to the test
4 0 2
is
1
in problem D?
1,2,3,4 are separate provinces.
if we add tunnels 1-2,2-3,3-4....then 1 and 4 will be added 1 tunnel,2 and 3 will be added 2 tunnels.no province will be added more than 2 tunnels.
Why answer is not 0?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem E, I don't understand why x must not be verified when it's prime; suppose n = 1, x = 3, a1 = 2. If we only check prime 2 (and not 3 itself), we get that it's possible to solve the problem with 1 element. However, there would still be an ambiguity between 2 and 3, once both have b1 = 1, wouldn't it?
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Wrong branch.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Oh, it makes sense now, from the problem statement I somehow thought it was talking only about the complete pages, e.g., the floor function. Apparently it is the ceil function, although the idea behind the solution keeps the same.
Thanks!
→ Reply