cerealguy's blog

Codeforces beta round #41
By cerealguy, 14 years ago, translation, In English
Hi everyone.

The today's contest is presented by us: cerealguy and yaro. We used to study in school together and Volodya studied there with us. So he will be the contest's hero: Volodya is going to cook in a kitchen, visit a museum, try to crack a safe, travel to an unusual city and even use his magical abilities.

We are grateful to the Codeforces team and especially to Artem Rakhov who helped us to prepare the contest and wrote alternative solutions.

We hope problems will suit your taste.

Good luck!

Update: Solutions
Announcement of Codeforces Beta Round 41
  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (46)
| Write comment?
14 years ago, # |
  Vote: I like it -18 Vote: I do not like it
Good luck to all!!
→ Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
I wanted to register for the contest 11 minutes before start and registration was closed. Why did you close it so fast? It would be better if it is closed 5 min before the start.
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
How does one stop getting email/delete their account at codeforces.  I am not interested in any of the permitted languages, and am getting tired of the email.  There is no setting to turn off email, and no contact information.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
in the problem B,The black king might be able to take opponent's rooks at his turn,what is the meaning?is it that the black king can only take the opponent's rooks at his adjacent cells or he can take any rooks?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it
    king only moves to the adjacent cell. it was in the statement.
    also in chess you cant kill a piece with a king if it is defended by another same color piece.
    → Reply
14 years ago, # |
  Vote: I like it -78 Vote: I do not like it
its bull shit codeforces is sheer bull shit i wrote a solution to the problem that got accepted and in a moment i am told that mysolution is hacked y the fuck no measures are taken against the stealers i am ruined and i m not intrstd in solving any further
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    what a pity!just go go!don't fuck,just work more hard and hack others!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Maybe you did not understand what "hacking" means. It is part of the contest. "Your solution was hacked" means that your solution was wrong and that someone found a test on which your solution fails and inputed it. This is part of the contest. So now, why are you angry that you got hacked, your solution would have failed the System tests eventually...
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    "The round will be held on the rules of Codeforces, so read the rules beforehand."
    → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Anybody has some ideas for Problem B?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    did your solution failed on pretests?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I have no idea for it, so I didn`t code it.so.....
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        OK,I'll try to help u.
        U should simulate rook's moving until u meet some white figure and mark all the points as bad.But DON'T mark the point,that ur rook\king starts from.Then mark all the points that ur king can beat.Then check the points,that black king can go to and the point that he starts from.If one of them is good one,then "OTHER" else - "CHECKMATE"
        I hope it will help u ;)
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What happened with problem B, it was massive slaughter in the system test.
Are there maybe wrong tests in it?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes, it is strange(although probably fault is mine and not of the systest as always). Maybe some of you knows what the test 7( not pretest) is? I failed on that one.

    If someone has test 7 for problemC(yes, 7 was my unlucky number today) It would be great.

    Thanks in advance, and thanks to the setters for the nice problems!!!!
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I dont know the seventh one exactly,but i know some another good tests:
      c2 b3 h8 a1 OTHER
      h1 a8 h8 a1 OTHER
      a2 b1 a3 a1 OTHER
      gl
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thanks for the cases! Anyway, I pass all of them. I'm sure this suggestion has been made before, but.....wouldn´t it be better to have the test cases made public after the contest?
        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it
          try this one
          b2 b3 d5 d3
          the answer is CHECKMATE for sure
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            Your challenge was succesfull.

            Thanks for taking the time man. I guess I should have spent that last ten minutes testing trying to hack myself instead of trying to hack others :).
            → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Well you had to add the magical part, Harry Potter is releasing soon!
→ Reply
14 years ago, # |
  Vote: I like it +16 Vote: I do not like it
Even CF couldn't avoid overflow:
http://mirror.codeforces.com/profile/tourist
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to do problem C ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My solution got failed, but anyway I'll describe it( maybe someone can challenge it).
    I think greedy works here.

    -If you have an even number > 1 between two odd numbers -> -1
    -If you have an odd number > 1 between two even numbers -> -1

    If you don't then you must either:
    1)do a division, or
    2) a sum and a division
    for any pair of numbers that need it.

    repeat this until you end with 1 1 1 1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      It is always possible to find an answer. For 1 2 1 1, the answer could be:
      +1
      +2
      /1
      /2

      I finished my code 20 seconds to the end but screwed up when submitting, thanks to my mouse pad.
      → Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it
    Generally, you could first greedily decrease some of numbers to 1 few times until numbers that are left are very small. ( I decreased the maximal value until it was not greater than 10. Other possible variant is to decrease each of values to 1 just 3 times ). After that you should just use BFS on different combinations of numbers in code.  I also checked that I don't reach positions with values larger than 30 in my BFS (And for all tests I gave my solution number of moves was always less than 200 so maybe that check is not so important ). Main advantage of this approach is that it is unconditional and you don't need to check cases.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Here is the greedy I used (passed, but I proved it by bruteforce):
    While you have a number different from 1:
    1) Find the maximal number.
    2) If it is even and has an even neighbour, divide. Otherwise, if it is odd and has an odd neighbout, increase them both, otherwise increase and any of it's neighbours.

    Why does it work: Each time before you divide, the total sum increases by 4 (after you make 2 additions, you're guaranteed to divide). So, with each division the total sum decreases (compared to the sum after the previous division) unless the biggest number is 4 and is surrounded by 2 odd ones. Those are not many cases, I just wrone the program and tested all of  them - received answers on all. If anyone can give a better proof, you're welcome.
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    I had such an approach:

    while there is a number not equal to 1:
            if there is a pair of two even numbers:
                    divide them by 2;
            elseif there is a pair of two odd numbers(and at least one of them is no equal to 1):
                    increment both;
                    divide them by 2;
            else
                    find a pair with two different odd/even numbers(i.e. one is even, the other is odd or viceversa); 
                    increment both ;

    My solution failed tests because of the mistake in the last else statement: I wasn't looking for two numbers, instead just incrementing the first two so the test-case '1 1 1 2 1', or alike, killed solution. Afterwards I've changed it in the way as in the pseudocode, it has passed with flying colors.
    → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
I'm not sure I understand the concept of "hacking" here. Apparently in today's match tourist hacked MBabin's solution to problem B. But it shows that it also passed system tests, and he ended up getting full score for it, while tourist also gets score for the hack. What actually happened?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Bad System Tests? Maybe hacking tests aren't added to the System tests and that, along with a bug(Codeforces Beta - Contest alfa) gave the result?
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    MBabin didn't lock his solution, so after tourist had hacked it and got the score, MBabin just found the bug, fixed it and resent his solution.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    You can resubmit solution after hack (if you haven't locked it already). So MBabin noticed that his solution is hacked, fixed bug and submitted new version.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
any one can tell the 20th test case of problem B .

Thanks in advance
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    a6 a8 c2 a1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How do you get to know that? I still don't know how things work around here very well.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Forget about it, I just saw that you are the problem setter.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the algorithm for Problem D ? Seems like some small but nice idea ..
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    The idea is to assign some numbers ai to vertices and the lengths ai + aj to edges. Then the condition about hamiltonian cycles will be fulfilled. To ensure the condition about different lengths, just choose the numbers ai one by one so that it was always true that ai + aj ≠ ai' + aj'. In other words, when you choose a new number, it mustn't be equal to ai + aj - ak and ai - aj - ak, for any already chosen ai, aj and ak. It turns out that if n ≤ 20, this process never needs numbers more than 500, so all edges have lengths less than 1000.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    We've put a link to the problemset analysis.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why can't testcases be made available after a contest is over ?


→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You can find detailed analysis and source code of problem C & D here - 

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

Borscht aint Russian traditional soup. It originates from Ukraine

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

    Russia and Ukraine still have no cultural border.
    There are more differences between eastern and western Ukraine then between eastern Ukraine and Russia.

    → Reply