Aksenov239's blog

Codeforces Beta Round #56
By Aksenov239, 14 years ago, translation, In English

Hi, all!

I'm the author of today's contest. On today's contest you will meet with a big amount of funny persons (or not only persons; :-)!), who had problems, and you should try to help them.

This Round was prepared with help of Rakhov Artem and Maria Belova.

Solutions.


I wish you high ratings!

Announcement of Codeforces Beta Round 56
  • Vote: I like it
  • +153
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I hope these people don't have very "mathy" problems. Good luck to all :)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it
    But I hope these people have very heavy "mathy" problems. It's better that the problems about long code:)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it
      There are many problems which aren't very "mathy" nor very "cody". Not every non-heavy-"mathy" problem is "cody"...
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it
        Yep. I didn't see another. Only brutal code, heavy math(or logic==math) and unusual algorithm. Maby because I haven't good practice? But I don't think so.
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The contest is pretty "Mathy".
    But "Mathy" is not bad.
    The problem set is really good. :)
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Finally I'll compete again in a CF contest after a long time! I hope we'll have fun today!
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
I tried to hack a solution of problem A. In the solution an array was declared as a[1000] and the element a[1000] was accessed. It was an unsuccessful hacking attempt. Shouldn't it cause segmentation fault?

And I did realize if i write something with leading spaces for hacking(i.e without using generators), all leading spaces are automatically removed. It took me two unsuccessful hacks to know that :(
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    С++ solutions often don't crash when try use elements out of array. It was dicsussed some contests later. You can find it with Google.com 
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sure, any hacking attempt should be a valid test. If not, either it's made valid automatically (as with leading/trailing spaces) or your hack should result in an "Invalid test" message.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      "or your hack should result in an "Invalid test" message." would have been more useful
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it
For the problem E.
It's said "It is preffered to use cin "
But I used it and Timed out.
I add this one and get AC:
ios::sync_with_stdio(false);
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Me too. I got TLE (in  problem E) with cin, and later in practice AC with scanf. This is bad.
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Any hints for problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    LCM(a,b) = (a * b) / GCD(a,b)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      So, using this we would know the product of numbers for each pair of nodes having an edge..that would still leave us with a large state space right?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        My bad..didn't realise that choosing 1 number would uniquely determine(if possible) the other numbers in a connected component ..
        → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      ... I noticed it and still didin't manage to solve.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    gcd(a,b) = p1^a1 * p2^a2 * ... * pn^an
    lcm(a,b) = p1^b1 * p2^b2 * ... * pn^bn

    you can notice that either a or b will have p1,p2,...pn as prime factors (even when their powers are zeroes) and their powers would be either a_i or b_i (different values from these would make gcd and lcm's values different), and the number of possibilities to each would be something close to 2^7
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    For each connected component, you can pick a node and try all the possible values. That would determine the values of the whole component.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I'm new in this site. I'm trying to solve this problem in the practice room and I get WA on 13rd test case, as most people. I cannot see the full test case(it's truncated). Is there a way to see this test case completely? Or what is the trick in this test case? Thanks!
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      No, you can't see full test at this moment
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        When precisely can they be seen?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Sometimes ago MikeMirzayanov anounce possibility to download all test and checkers but it is not availiable now.
          → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      WA on 13rd test case occurs when you don't check co-primality of integers. (that was mine)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Sorry, I thought this problem is D - so my reply is irrelevant.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Strange, but in my submission result all test cases are duplicated - test 1, test 1, test 2, test 2, etc..
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is time limit for problem D a little strict? My C++ implementation used std linked list for the adjacency list and got TLE. When I implemented my own linked list using array, it passed the time limit.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    std::list, as well as LinkedList in Java, is extremely slow. Consider not using it, except for very rare cases.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I cannot find out, what I am doing wrong on C test case 13. I test for gcd and lcm.
http://www.ideone.com/WIBXx
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    Looks like you do not clean every sol[i] (of the currently judged connectivity component) when a certain iteration fails. In Trysolve, you set "sol[index] = -1" for a neighbour that caused the failure, but not the previous ones (and not their subtrees). The next iteration finds the sol[i] set by the previous one, which gets it confused.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you, I am very grateful. Now I solved the problem. I only set one children to -1 and not all of them..
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In D:
I can't figure out, How the following test case answer is 1 ? 
2
3 5
3 5 is not a beautiful triple, so how can the answer be 1. 
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Hi all,

Can I know what's wrong with my solution for E?

My code is here: http://pastebin.com/AQdbqw4E

My idea is:

Let the array be S with elements from 1 to N. Let f(x) be the sum of all elements after k moves.

Then f(x) = 3*f(x) - (S[1] + S[N]); f(0) = sum, where sum == summation of all elements in S.

The solution to this recursion is sum * 3^X - (S[1] + S[N]) * (3^X - 1) / 2

We can use this to calculate what happens in the first X moves. After that, the elements will be sorted. The leftmost element, the smallest element, will still be S[1]. However, we need to find what the rightmost element, ie the largest element, is. After some testing (proven by bruteforce XD, can anyone share a formal proof?), I realised this.

Let g(x) be the largest mushroom after x turns. Then g(x) = g(x-1) + g(x-2). Define g(0) = S[N] and g(-1) = S[N-1]. It is sort of like a fibonacci sequence.

After getting the leftmost and rightmost numbers in the new sequence, we can use the same idea in the first part and plug it into new_sum * 3^Y - (S[1] + g(x)) * (3^Y - 1) / 2. Then we can get the answer.

However, I get WA :(. One error I can think of is that in my solution to the recusion, I am doing division by 2. However, it seems that division in modulo does not work very well. I am not sure how to solve this problem. Can someone help me? Or does anyone have a better solution?

Thanks in advance!
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
First I thank CF team, preparing a nice contest.

I participated several recent CF contest and I got one suggestion.

IMHO, problems of every contest in CF is quite good but I found a descriptions of some problems wasn't clear to me. I hope CF team will take more consideration for problem descriptions( grammar or typo, etc... ).
→ Reply