meret's blog

Codeforces Beta Round #11
By meret, 15 years ago, In English
Let me warmly welcome you to Codeforces Beta Round #11. I am the main problemsetter for this contest. I hope you'll have fun solving the prepared tasks :-)

Thanks to Mike Mirzayanov for making this possible and to Ania Piekarska for testing the problems.

Good luck,
Jakub Pachocki
Announcement of Codeforces Beta Round 11
  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (65)
| Write comment?
15 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Thanks in advance to Jakub for the prepared problems and thanks Julia for translating of everything that it was possible to translate. =)
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    ))) That was not me, who translated the problems this time. They were originally in English, and Mike translated them into Russian ;-) I have nothing to do with the coming contest. But thank you anyway for being so kind )))
    → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Thanks for arranging this event.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks for the round!

I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Problem B is wonderful :)
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I wonder what was your problem with B that leaded to so many incorrect attempts.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I'd tried to know what is 4th test by debug-submits. When I knew it, I'd tried to know what is correct answer for it. It takes about 15 submits.
        → Reply
        • 9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          after 6 years of you comment i want to said to you that i facing the same problem :D

          → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ouch! Not being able to read bold text correctly for 40 minutes is something I experienced for the first time.
→ Reply
15 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Problem E is very nice :) I've got it accepted 3 minutes too late. The final solution is really short and cute, but it took a long time to get to.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    About other problems: I believe problems B and D were too well-known :(
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I invented B, D and E by myself (the other tasks were Mike's), so I'm surprised to hear B was well-known. As for D, it does look a bit classic, but I've never personally seen it in any contest, and I figured it requires a nice enough idea to deserve a place in the contest :)
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        With the idea being?

        I'm trying to find previous occurrences of B.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          Finding all cycles containing a vertex v in O(2^n * n^2), then removing v from the graph and repeating, so that the total number of operations is about is 2^n * n^2 + 2^(n - 1) * n^2 +... = O(2^n * n^2), instead of O(2^n * n^3) achieved by a simple DP approach.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it
            Oh yeah, that's a good point indeed. I take my words about D back :)
            → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            can you give some insight for how to solve E?  Thanks.
            → Reply
            • 9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There seems to be no editorial for this round or description of how to do this problem, so I will post my solution here.

              Solution
              → Reply
            • 6 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              does petr reply only to red coders ?

              → Reply
      • 15 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Perhaps many people found A140358.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Hmm. Conjecture? Interesting... That's why I didn't cope to prove the idea during the contest :)
          → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yes ;-)
          → Reply
        • 15 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it
          I'm surprised it's just a conjencture on OEIS. The proof goes as follows:

          Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.
          → Reply
15 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Where can I read about problems like D? (Counting cycles, Hamiltonian paths etc)
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Rus:  где можно почитать про число гамильтоновых циклов и путей?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      нашел что то отдаленно напоминающее
      http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77
      и разбор:
      http://informatics.mccme.ru/moodle/mod/book/view.php?id=489

      а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        и все таки не могу найти что почитать на эту тему оО только разве что порешать.

        самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)
        → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have problem in my head or codeforce has problem in its head....

my contest code of B got WA in test 4 using scanf and printf

but in practice same code got AC using cin and cout?

is there any explanation anyone can give?

here is my WA in test 4 code

http://pastebin.com/cbBH5nzz

if u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<<i<<endl; it gets AC ...

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!

    Or you can just make all variable int (it's enough) and use %d.


    I tested it just now.

    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm wrong. (c)

      From 2005 version VS supports both %I64d and %lld.

      → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Try to replace scanf("%lld",&num) with scanf("%I64d",&num) and printf("%lld\n",i) with printf("%I64d\n",i).
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Beaten :)
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I submited my code in GNU C++,,GNU supports long long ,right?
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        As you see, no.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          then its a shame to me...I have been coding knowing that GNU C++ supports long long ...I haven't faced any problem except this.even in my windows pc GNU C++ compiler(CodeBlocks) supports long long well....If codeforce's GNU C++ doesn't support long long ,,then I have nothing to say. :)
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Codeforces uses MinGW, which DOES support long long, but DOES NOT support %lld. %I64d should be used instead. Or you can simply submit using MSVC compiler, in most cases it will be fine.
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Thanx. this thing really pissed me off in the contest time. I should have known it earlier.
              → Reply
          • 15 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            AFAIK, gcc actually uses the OS's C library to make the call to printf. That's why  on Windows the format for long long is %I64d because the Windows C library uses that format, even though the compiler is gcc.
            → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If anyone wants to see my both code but cant see from the provided link..I will paste it here.
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Btw 2008 VS works with %lld. So don't be uncertain.
    → Reply
15 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Do all hadn't a respond from the site at the start of a contest?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    I couldn't open any page for about 5 minutes, but judging by the standings page, many people submitted A at 0:03-0:04...
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It's strange.
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Same problem here.  But I guess that doesn't really make a big difference.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        I think it does make a big difference. If you lost 5 minutes in the beginning and solved N problems then you'll get 5*N extra penalty time. 

        If I could access the site immediately from the beginning I'd be 1 or 2 positions higher in the ranklist, and will probably be red today.
        → Reply
15 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Thank you, Jakub, for interesting problems. It is an essential aid for Codeforces. I'm very glad to work with you.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Does anybody want to share the solution of problem D and E?
→ Reply
15 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the problems, but I'd like to pay attention to some inaccuracies in them. 

1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1, 1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go either back or forth with each jump."

2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.

3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square?

4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?

Thanks.

→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think the authors should explain the examples for all the problems in the contest.

    For example: the authors should explain why the result is 1 for the 1st  test case, 2 for the 2nd test case... for the problem C. 

    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You mean explain withit problem statement?

      If yes, I'll agree with you.

      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        yes, this is exact what i want. Hope the problem setter will do it next contest.
        → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Did anyone solve problem B using DP solution?
I want to do but I can't...
I hope someone show me the code.
Thanks.
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't know a DP solution.

    For example. If you want to reach 10^9 position, in some you'll be near it. Let it be a 10^8 position (of course the real position place will be close to 10^9, you can prove it yourself). So we need to compute 10^8 cells. It takes more than 1 sec time. :(

    And you need about 120 MB to store billion length bool array.

    Maybe there is a much better DP solution, and maybe even it got AC, but i solved that with little formula and very little bruteforce (most of participants use only brute).

    If you request a code you can get it there - http://mirror.codeforces.com/contest/11/status/B?order=BY_ARRIVED_ASC
    → Reply
    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am new to programming. The people have solved problem D quite easily as it is quite trivial for them. I am not able to understand how they are solving using DP. what is the subproblem. I have spent 3-4 days trying to understand the solutions but no success. Can anyone help ? I will be grateful for the same

      → Reply
      • 11 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        The comment removed because of Codeforces rules violation
        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve B? I saw people using logic while (sum<x || (sum-x)%2==1) {ans++; sum+=ans;}, what is the logic behind (sum-x)%2==1?

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

    Let us suppose you take j jumps to reach some point y where y >= 0. Let us suppose you took some forward and some backward jumps. Clearly, we can write : 1. (sum of forward jumps) — (sum of backward jumps) = y ...equation(i) 2. (sum of forward jumps) + (sum of backward jumps) = j(j+1)/2 .... equation(ii)

    Combine both to get: j(j+1)/2 — 2(sum of backward jumps) = y

    The above equation is the key. [Note : sum of backward jumps -> is the sum of some elements from the set {1,2..,j} which can take any value between 0 to j*(j+1)/2 ..not too difficult to prove]

    Hence, if (j(j+1)/2 — y) is even and (j(j+1)/2-y)/2 lies in the range [0,j(j+1)/2] then clearly we can reach y in j moves. Hope it is clear!!

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

I will try my best to explain the my approach on problem 11D without using sum of subsets dp. Denote d[last][mask] as the number of ways to form a chain consists of every elements with its bit on in the mask, the first bit (first_bit) in mask is the head of the chain (we are fixing the order of the cycle) and last is the last element in the chain. The transition is easy, take every possible next bit that satisfies next > first_bit, next doesn't appear in the current mask, next and last share an edge and d[next][mask^(1 << next)] += d[last][mask]. Check through every dp state that there is an edge between last and first_bit and add them to the final answer. Finally divide the answer by 2 as we repeated the calculation in the last step.

My submission: 79403398.

→ Reply