witua's blog

Codeforces Beta Round #91
By witua, 13 years ago, translation, In English

Hello!

Wellcome to Codeforces Beta Round #91! This time, the author of the round will be me, Herasymiv Vitaliy (witua). Thanks a lot to Artem Rakhov (RAD) for helping in round preparing and Maria Belova for problems translation. I hope you will like problems.

Good luck!

Thanks all! And here are the winners:

Division 1:

  1. tourist
  2. 2222
  3. PavelKunyavskiy
  4. Petr
  5. vepifanov
  6. dzhulgakov
  7. e-maxx
Division 2:
  • Vote: I like it
  • +125
  • Vote: I do not like it

Comments Comments (66)
| Write comment?
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Looking forward to it. Nice tag :) 
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
I suggest to name this contest after John McCarthy's 91 function.
→ Reply
13 years ago, # |
  Vote: I like it -17 Vote: I do not like it
why your tag is 77+7+7 just write  91  to help us when we search by tag :) :)
btw,nice tag :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Maybe it's a hint for a problem in the contest. :P
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      Or just show that 91 is also a lucky number :-)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        It is not lucky number. It's only almost lucky number :)
        However, there are 4 7s in 77 + 7 + 7 which make 91 seems luckier than many other real lucky numbers. Nice one.
        → Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Short statements, hands-on!
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I hope I will increase my rating as well by positive "lucky" number.

→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
I'm sorry for the off topic question, but I could not find any other place to ask. Is there any tool, that is capable of generating the problem skeletons with a stub for the implementation method and test cases? Something similar to CodeProcessor on topcoder?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    If you use IDEA for Java, plugin from Egor can help you
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Thanks, but unfortunately I do not use IDEA (I write in cpp).
      Is there any place here, where noobs can ask stupid questions?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it
        Unfortunatelly, no.
        May be your blog is a such place, but if care about your "contribution" you'd better to ask Google first :)
        What IDE/OS do you use?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it
          I don't really care about the contribution in particular, because I do not know what is it good for, which is in turn due to the fact, that there's no description of any sort on this matter :)

          I am using Visual Studio on Windows. It would be fun to write such a tool, I am up to it, unless it is not implemented yet (which would surprise me actually).
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I haven't heard anything about such plugin.
            You're welcome to implement and share it :)
            → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
thanks for your problems in advance :D
→ Reply
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it
Website response seems slow to me. Are you feeling same? :(
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    No, all seems to be OK. Internet connection problems?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Sometimes connection fails. And slow response time too. Other sites are OK. Same problem from both office and home :( ,,, If CF is OK, then probably some kind of gateway problem has occurred :p
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Check ping timeout for ya.ru 
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yes sometimes the connection was slow (I couldn't send B for a few minutes, because when I clicked "submit" the page freezed). In particular, in the last 2-3 minutes I wanted to hack: "unable to connect to ..." :(
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      By the ways, thanks for reply Mr. anonymous ;)
      → Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I loved your previous contest :D Hoping to feel the same today :D
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
thanks

this problems are easy and good!
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Why are digits 4 and 7 considered lucky? Is it a Russian tradition?

Partly because I'm very sleepy, I don't like those `lucky number' problems, by the way.  I shouldn't have participated :-(
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    It's witua's tradition, not Russian :)
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    No, such problems are often apears on TopCoder too.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I bet, such tradition appeared after one of TC contests (403 or 404, can't remember, maybe even earlier).
    And after that many liked that idea and so on...

    This time there wasn't any special properties of such combination, so them could be almost any different pair as well. But why one should break such a good tradition? :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      I didn't know that.  It seems I need more SRM practice ...

      The idea of four being a lucky number sounds a bit odd to me, because where I live the number four (in fact even numbers in general) is considered to be very unlucky.
      → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    This is tradition from Lviv, Ukraine.

    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

So many lucky number contests, almost bored of lucky numbers.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice problemsets again, thanks witua!

BTW, what's the corner case of DIV2 A? So many people got hacked.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used 222. It is divisible by 74.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    Many people think that lucky number just 4 and 7. in fact there's a lot lucky number under 1000 = 44, 47, 74, 77 ect. . . And I got hack because of that T_T
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it
      Even don't think about this. After I found A was a source of fierce hacking, I thought probably no wrong solution would be lucky enough to survive, so I did't attempt to hack.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good problem set. 
→ Reply
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
This is the first time I'm in the DIV1.But I am so nervous that I made many silly mistakes.To sum up, I learn a lot.Thanks the author!
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Can someone give me the logic to solve problem D.looked into the accepted solutions but unable to get the logic behind the code.Thanks in advance:)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You basically loop through the array once and perform the described actions until you either reach the end of the array or run out of moves.

    The case to look for though is when you reach a part of the array that looks as follows: a[i-1] = '4', a[i] = '4', a[i+1] = '7', and i is even. In this case this part of the array will switch between 447 and 477 for eternity :) So if you have an odd number of moves left it will end at 477, otherwise 447, and this uses up all your remaining moves.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Search for 4-7's from starting. Now There are 2 crucial observations:

    1. When you find the a 4-7 in a odd position
            >>If there is only one 7 in front of it than just replace the 7 with 4 and continue searching.
           >> If there are more than one 7 like(124777) you'll stuck in a loop(124777-->124477-->124777)

    2. When you find the a 4-7 in a even position
             >>If there is a 4 behind the 47(like 6447) you'll stuck in a loop.(6447-->6477->6447)
             >>other wise you can just replace and continue searching.

    in case of  "replace and continue" i increment "step" by 1. When i stuck in a loop i just check how many steps left and determine the final string from it. The complexity is just o(n).
    Hope this helps.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I assume you mean div 2 problem D. The idea is, that once you encounter the string "447", where the second 4 is at an even position it will keep looping with 447 -> 477 -> 447.

    If a such string is not present the amount of operations that can be done is O(n).

    You thus run through the string and when encountering a 47 you check if it's in odd or even spot. If it's in an even spot you check for the terminal condition (above). If this isn't a terminal 47 we can just do the operation and either move one step forward or one step backwards depending on odd/even.

    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Nice contest,div 1B/div 2D was really an interesting  problem. Hope editorial will be available soon.  I now have experience of getting +0 point both in tc and cf.

Can anyone share idea of div1 C?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    You must know how much last elements, lets say x, you have to swap. It will be at most 13, because 13! > 10^9. If x > n you print -1. Otherwise you get k-th permutation and you set last x elements according to this permutation. Then you check for each element if this element and it's position are both lucky numbers.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    It's well known, that number of permutations of first N numbers is equal to N!. Therefore, we can say when we shall print "-1"  - if N! < K. Of course, we shall check this only for N <= 12 as 13! >= 1000000000.
    Let's assume SIZE as the biggest integer for which equality SIZE! >= K holds. Now we can definitely say that changes are made only to last SIZE numbers- they are N - SIZE + 1.... N. 
    Now we simply generate K-th permutation for SIZE numbers ( we can do this using O(SIZE) memory and O(SIZE * SIZE) time). 
    Let's generate all lucky numbers up to 1000000000. Each number less or equal to N - SIZE stays on position that is equal to this number. As we have no more than 511 numbers, we simply iterate over them and count them. The last thing to do  is to work with our generated permutation. If position (N - SIZE + i) is lucky and (N - SIZE + perm[i]) is lucky we increase the answer.
    Here you can see my code. Please, feel free to ask questions if any.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain how do you generate the k-th permutation of SIZE numbers using  O(SIZE) memory and O(SIZE * SIZE) time? 

      Thanks.


      EDIT: I found it.
      → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    Notice that 10^9-th permutation can shift no more than 13 last numbers.

    First, count number of happy numbers that could not be shifted - they all stay on their places, happy places.

    After that, generate K-th permutation, apply this permutation to last numbers and find indices of happy numbers among last numbers.

    upd: so many replies)

    → Reply
13 years ago, # |
  Vote: I like it +28 Vote: I do not like it
This is one of the best problem-sets I've ever seen in Codeforces. Thanks!
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Nice problemset!

But what's the point of having hacks if there are trick/corner cases on pretests?

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

    Not only on pretests but also on the examples. However it depends on the author which corner cases he decides to reveal. Sometimes the difficulty of the problem can vary a lot depending on the pretests and the examples.

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

UNFORTUNATELY , i had a stupid mistake and got wrong answer on 30th test . I have never written any contest with no silly mistakes  thats why i am in 2nd division again :(((

→ Reply
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Impossibly weak tests for DIV 1 E!

I saw at least two accepted solutions that don't pass basic max test like one generated by code below.

#include <cstdio>

int main() {
  int n = 100000;
  int m = 9999;
  printf("%d %d\n", n, 2*m);
  for(int i=0; i<n; ++i) printf("1 "); printf("\n");
  for(int i=0; i<m; ++i) {
    printf("add %d %d %d\n", 1+i, n-i, 1);
    printf("count %d %d\n", 1, n);
  }
  return 0;
}
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    Your test will be added to testset in practice. We are sorry for that. Of course, every test case can not be considered, and it is impossible to rejudge accepted solutions after the end of the contest.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Problems were nice, hope you've learnt the lesson to make tests as good too.

      Not adding basic max tests is beyond my understanding considering you were trained by Vasyl.

      Some ideas for even better tests: 50000 add queries, which make all numbers take all possible values in the process, with random count query after each.

      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I want to know Why O(n^2 logn) can pass the text? Is it actually the complexity is less than it?
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Some examples?
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      For problem E in div 1, is block-array solution expected to pass? My code in the contest had some minor bugs, however I modified and it worked in practice (for example, 809913)

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

    Right after the contest, I submit my code with O(nlogn) for adding and O(logn) for counting (using BIT) and get AC, that's really surprising!
    5' ago, I resubmitted the same code and got TLE on test 62.. :(

    → Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

The complexity of block-array solution seems to be O(m*sqrt(n)*log(sqrt(n)*2^10)? I don't know whether it can solve this problem without enumerate every lucky number

→ Reply
13 years ago, # |
  Vote: I like it -12 Vote: I do not like it
Even the numbers of winners in both divisions are lucky numbers (7 and 4). It was odd to me that the number of winners in div 1 is different from div 2. Now I know why. lol
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is 799 almost lucky? (122A)

→ Reply