stgatilov's blog

Codeforces Beta Round #47
By stgatilov, 13 years ago, translation, In English

Good afternoon.

One more codeforces format round takes place this evening. I'm the author of the contest problems. Artem Rakhov and Maria Belova helped me to prepare the problems. Great thanks to them and all codeforces "fighters"!

I wish you good luck and funny hacks!

P.S:  This round won't be rated. So your ratings won't change. That's because of severe problems with codeforces server. Read here for explanation.


Announcement of Codeforces Beta Round 47
  • Vote: I like it
  • +49
  • Vote: I do not like it

Comments Comments (111)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please don't to hard for the problem. . . I'm newbie on this. . . ^_^
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
If the problems are easy, the process of problem solving pleasure does not deliver.
→ Reply
13 years ago, # |
  Vote: I like it +68 Vote: I do not like it
sorry to say that but if the server isn't strong enough just limit a registration number : )
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Already plused you, but I just gotta say I have the same feeling: codeforces should limit registrants, until it has enough resources to handle more competitors. May be an stress test would be good....
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why don't you allow to register just before contest ? :( , the site was down for sometime and when its back, registrations closed :-/
→ Reply
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it
It's better to be in tightness, but not in offence
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
the server is not responding.. i m trying to open the problems, but it is saying that competition not started but it has started... WAT TO DO???
→ Reply
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Wait 5 minutes, after that again 5 minutes, and so on...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I cant come in into contest room T_T. . . .
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I registered for the contest, and when the timer got to 0, it gave me the pop-up to enter the contest. I saw the first problem, wrote a solution, tried to submit, and was told I wasn't registered O.o

Indeed, I don't seem to appear on the registration list, but I must have been registered or that pop-up wouldn't have appeared, right?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    No, spectators see popups too. They can read the problems, but can't submit.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Good to know. I'll double-check that my registration has gone through next time.

      And I see a typo on the Score Table on the problems screen. "Successfull" and "Unsuccessfull" should each have only one "l" at the end.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm trying to hack, but I always get "submit already challenged" although I keep seeing the submit! Please clarify this issue.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is because of server unstable work. Sorry.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thx for answering Mike. I guess error is maybe due to the fact that my hack case was quite big(100 thousand chars). I was able to hack using the generator feature, instead of pasting directly my hack case. Maybe this information can help.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
During the contest you can't see it.
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
For some reason I have two passing submissions for problem B, still I have +1 for that problem in scoring. Is this my mistake? My browser seemed frozen, so I submitted again.
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I , too faced a lot of problems from the beginning and during the contest .
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I , too faced a lot of problems from the beginning and during the contest .
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
I think that it would have been better to have postponed the contest on the other day.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Or not rate it
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes but this is a waste of the round. I think that in the future if there are such problems it's better to postpone the contest rather than start it with small delay.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It keeps on crashing! And I am getting compilations errors which are server related problems. Please check...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What does Problem D mean?
I stared at the problem for 1 hour and can't catch the meaning at all.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    We're asked to find such R, that probability of success(i.e. destroying no less then K buildings) will be at least (1000-eps)/1000.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      But how to calculate the probability of success?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        For a fixed R, you can use dp to know the probability.
        Consider a single building: either you destroy it with some probability p, and you still have to destroy k-1 building, or you don´t destroy it(with a probability 1-p) and you still have to destroy k buildings. You can implement it using memoization for an O( n*k ) solution( with R fixed). That's why you see people talking about binary search + dp: you do bsearch over R.
        → Reply
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
cannot view the problems
cannot submit the code
cannot challange others
cannot watch the standing
only i can do ... goto bed at once ...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    This round probably won't be rated.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it
      I hope so. since at the middle of contest , I became unable to submit and hack. I believe my rating may decrease by 200 if this round is rated.
      → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Code Forces is so popular...
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Just wondering why is the duration of next contest 2:30 instead of 2:00?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Lowercase Latin letters? It would be better if it is lowercase English alphabets in the statement. It always gets me ! :(
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What's wrong with that?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • Its not correct!
      • I don't know if they really mean that it is from 'a' to 'z', or if there are special chars involved.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think you can use the whole ASCII code to become the index of an array.
        Just to init an array with length 260 or more.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yeah, next time i will do that!

          One more thing,
          in problem B, if i use printf("%lld\n",ans) it gives me wrong answer but accepts when i use cout<<ans.
          Why?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Test system based on windows, that's why minGW, not real g++ is used. Use %I64d or 
            cin/cout
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Thanks for clearing that! :)

              With one test case per file cin/cout would be a better option :D.
              → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think the point is how to understand the value K and ε
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution to B was hacked. However when I run the same program on my computer with the hack as the input, it gives the right answer! Could this be because of a system error?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I have had a similar problem, aren't you using %lld when printing and submitting it with compiler GNU C++? If so, try %I64d
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I use GNU C compiler....
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It doesn't make change I think, it's just MS C++ vs GNU-family compilers..
        → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The great problem was that "%lld" did not work properly on the server (GCC). I was not aware of this problem (on my computer it works well). This difference caused a lot of hacks in B. Sorry for that...

      Though even is "%lld" worked properly the number of int64 hacks would be huge=(

      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Additional Info: The hack was extremely large, length ~ 10^5;
    I used a long long for storing the answer which was of the order of 10^10.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Maybe you have an 64-bit processor and your int is 64-bit? (The server's int is 32-bit.)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      nope... i used a long long so that wouldnt matter i guess.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        how are you printing it?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          printf("%lld", count);
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Try either: 
            submitting it again and choosing MS VC++ - it'll work fine
            or 
            changing that line to printf("%I64d", count);

            → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        you shold use scanf/printf with %I64d , not %lld
        or std::cin/std::cout
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          ehm.... I have always been doing it as %lld and it never had a problem. What is wrong with doing it as %lld?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Always when test system (i.e with gcc) based on Windows It's better to use %I64d
            → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test 7 on problem D.

I use Greedy + Binary Search, but it seems DP + Binary Search.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and test 10 for problem D please,thanks

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      choose
      My submissions, click for My submission's id and scroll to view tests
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used the second algorithm, but it failed at the same test.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    Yeah, it's a Binary search with DP.

    The binary search in in the radio.
    The DP is the following:

    let p be the probability of the ith building be destroyed with a certain radio.
    let DP[i][j] be the probability of destroying exactly j buildings taking in consideration the first i's (1-based) buildings
    DP[0][0] = 1.0
    DP[i][j] = DP[i-1][j]*(1-p) + DP[i-1][j-1]*p;

    Then you check the sum of DP[n][0...K-1].

    Unfortunately I did this correct but the limits of my binary search were wrong [0-1010] instead of [0-2000sqrt(2)] and got W.A. during the contest and ACC a few minutes later.
    → Reply
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
For problem B, I was trying to hack with a string like 'aaa...' of length 10^5. However, testcase editor was automatically truncating the string to ~34000 characters without giving any warning. It took me 2 unsuccessful hacks before I found this limitation. I think it is not mentioned anywhere what the default limit of the editor is.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Now you can use test generator,
    but I hope,it will fixed
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes, I used generator later. I was not sure how to use it, so I had to re-read the contest rules.

      Another thing for admin's consideration is to put the rules as a separate page instead of a blog post. I have to google every time I want to read the rules.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Add it to favorites/bookmarks:)

        Sorry,I don't know how it's named in english)
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How generator works? There are two things. One is file upload other is generate paramitre.Have to I use both ? and how?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Today I used generator for the first time. In my case, I just send my cpp with code that prints to standard output and that was enough.
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can submit a generator.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

okay....enough talk of server being busy...

can anyone point me my mistake for Problem B:

#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
map<char,long long > c;
unsigned long long int ans;
long long int j;
string s;
cin>>s;
j=0;
while(s[j]!='\0')
{

// if((s[i]<='z'&& s[i]>='a')||(s[i]>='0' && s[i]<='9'))

c[s[j]]++;

j++;
}
ans=0;
for(map<char,long long int>::iterator i = c.begin();i!=c.end();i++)
{
//printf("%d ",c[i]);
ans+=(*i).second*(*i).second;
}
printf("%llu",ans);
scanf("%*d");
return 0;
}



→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    it is having problem with tescase of length 100000(approx) as shown in practice submission.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I dont see the bug, but you can program it without using map - just use an array of long long int with indexes between 0 and 255..
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Plz point out my bug...I wont be sleeping tonight ..If I cant find out.
        EDIT: got the mistake it was %llu ...
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      As has been discussed above, printf("%llu",_) is not working ... try cout.
      → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      you should use either cout << ans; or printf ("%I64d\n", ans), I think.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    %llu & %lld is not correct to use here, read about it on other comments threads
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
WTF? I got correct answer of test case #48 of D in my computer, but wrong answer of case #48 in judge? any one help?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Will this match be rated?
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I got WA on test 21** in the final tests of problem B in the contest. And by changing printf("%lld\n",ret); to printf("%I64d\n",ret); I got accepted in the practice!!!

Anyone please reply if this is fair to get WA in the contest!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You are not first)
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is impossible to get WA in the contest. The maximum cases must be only in final tests.
    P.S In WinGW you must use %I64d for long long and double instead of long double.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Further more, I got three unsuccessful hacks because I didn't know that my whole test case isn't pasted!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Looks like there are two different approaches for problem C. Could anyone explain the ideas?   
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    My approach was to change each point p(x,y) into four points p1(x+1, y), p2(x-1, y), p3(x, y+1), p4(x, y-1). Then run convex hull and result is sum i = 0..|CH|-1 max(|CH[i].x-CH[i+1].x|, |CH[i].y-CH[i+1].y|). CH - convex hull.
    Edit: However I saw much simpler and linear time solutions.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Find 4 points: min by x - y, min by x + y, max by x - y, max by x + y. Convex hull is a rhombus, the answer is max(x + y) - min(x + y) + max(x - y) - min(x - y).
    I thought about octagon at the contest and used 8 points.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve problem E? The submissions look short.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I won't write a full algorithm, but here is the idea:

    First of all let's prove, that if the root is not integer, it's unique (that is, it can appear only once):
    Let x = -b + sqrt(d). In case x is also a root of another equation, there exists such u and v, that x = -u + sqrt(v). Then b - u = sqrt(d) - sqrt(v). That means, that difference between two square roots is integer, however one can prove that it is only possible when d and v are full squares, which isn't true (according to our assumption).

    Now if x is not integer, then let's check if it can be root of some equation.
    Since all roots are negative, for given x, we try to find negative y that
    x+y >= -n
    x*y <= m
    Apparently such y can be 1 for odd x and 2 for even x.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to say, that I think the problem statement D bomb is not so appropriate. Especially the word nuclear bomb. I think in my personal view that war is not a solution and some bombs, which have the capacity of killing millions of people, should never be used.
Howerver, If you would started the description like.
"Vasja is playing a game. In this game he has to drop..."

It would be much more appropriate.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I must agree, i found the problem statement rather offensive. 
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      How is it offensive? It's a programming contest problem, a fictional story, just like any action movie involving nuclear bombs. Don't take it personal.
      → Reply