stgatilov's blog

Codeforces Beta Round #47
By stgatilov, 15 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?
15 years ago, hide # |
 
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
15 years ago, hide # |
← 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
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
     
    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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it
It's better to be in tightness, but not in offence
→ Reply
15 years ago, hide # |
 
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
15 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it
Wait 5 minutes, after that again 5 minutes, and so on...
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I cant come in into contest room T_T. . . .
→ Reply
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
     
    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
    • 15 years ago, hide # ^ |
       
      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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
During the contest you can't see it.
→ Reply
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
    ← 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
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      But how to calculate the probability of success?
      → Reply
      • 15 years ago, hide # ^ |
         
        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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Code Forces is so popular...
→ Reply
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    and test 10 for problem D please,thanks

    → Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    I used the second algorithm, but it failed at the same test.
    → Reply
  • 15 years ago, hide # ^ |
    ← 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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
15 years ago, hide # |
← 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
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Will this match be rated?
→ Reply
15 years ago, hide # |
← 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
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    You are not first)
    → Reply
  • 15 years ago, hide # ^ |
     
    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
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
  • 15 years ago, hide # ^ |
    ← 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
  • 15 years ago, hide # ^ |
     
    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
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
How to solve problem E? The submissions look short.
→ Reply
  • 15 years ago, hide # ^ |
     
    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
15 years ago, hide # |
 
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