Nedy88's blog

Codeforces Beta Round #26 (Codeforces format)
By Nedy88, 14 years ago, In English
Hello everybody,

Codeforces Beta Round #26 will be held on Monday, the 16th of August, at 19:00 MSK. It will be Codeforces format round, and if all goes well it will be rated. Authors of the problems are Artem Rakhov and me. Thanks to Mike Mirzayanov and Dmitry Matov for help in organizing it. Also thanks to Julia Satushina for translation of problems.

Good luck, see you on the round!

UPD: The contest is over, thank you to everyone for participating.

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (38)
| Write comment?
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Hey , if u don't mind can i ask one personal question?

Were u guys working on the Testing Process or Development of Codeforces Format round these days? Or it was just bcz u are busy with ur works.?

I am eager to know bcz i have with been the codeforces since its 3rd round.


Thanks
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I asked a question, but I think I more or less understand the problem. Each attempt costs 50 points. After I made successful one, next unsuccessful attempts costs nothing, but what happens after I made next successful one? Will all attempts before the last successful be counted as -50?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    I believe the answer to that will be "Yes".  See Codeforces format description 8:
    You may resubmit the solution at any moment, but it may reduce your score. It happens if resubmission is successful (i.e. passes all the pretests + previous hacking attempts). In this case, the previous successful attempt would be considered as a reason for penalty (see item 3).


    → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Can someone throw some light on how to work out D. Tickets?  I see from ACed solution that the formula is 1.0 - (n! m!)/((m-k-1)! (n+k+1)!).  But, why?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    It can be solved similar to calculating Catalan numbers by method of refelection. (see wikipedia)
    → Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Oh!
I really loved it
when is the next round?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can any one explain how to solve problem C? i tried to solve it using brute force appraoch but it gives me time limit?can any one explain the solution and thanks in advance.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Split the problem in cases:
    n = number of rows
    m = number of cols

    * n and m are odd -> No solution
    * n is odd -> Fill the first row using pieces of type a -> now, n and m are even
    * m is odd -> Fill the first column using pieces of type b -> now, n and m are even
    * n and m are even -> Fill the matrix using blocks of size 2 * 2 (two pieces of type a, two pieces of type b or one piece of type c). If you are in the cell (i, j) you have to check the cells (i - 1, j), (i - 1, j + 1), (i, j - 1), (i + 1, j - 1) in order to calculate the chars you can use for the current block (remember that if you're using a block of two pieces of type a or b, you will have to use 2 different chars), now use one available 2x2 block  (if there is no available block -> No solution), update the pieces and go for the next non-filled cell.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks so much. i solved it.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Interesting.  Why does this approach always gives a solution whenever possible?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        • The first case is trivial: Pieces with even area and the total area is odd.
        • The second case: n is odd. We can't fill any column using only pieces of 2 x 1 and 2 x 2, because, at end, always, there will be 1 non-filled cell. So, in any moment we will need a 1 x 2 piece, then, used in the first row and fill all cells in that row (one 1 x 2 piece fill two cells, and the number of cols is even) if we have more than m / 2 pieces.
        • The third case: almost same explanation that the second case.
        [In both cases (second and third) we get a matrix where m and n are even.]
        • The last case: n and m are even. n * m = (2 * n') * (2 * m') = 4 * n' * m' (for n', m' >= 0). The area of the matrix is multiple of 4, then, we can filled it using pieces of area 4 (2 x 2, 2 x (1 x 2) or 2 x (2 x 1)) if we have enough (a / 2 + b / 2 + c >= (m * n) / 4).
        adamax wrote a tutorial about beta round 26. You can find it here -> http://mirror.codeforces.com/blog/entry/610
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anybody give me test case 5 of problem E?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry. Did a silly mistake. Got Accepted.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can Anyone explain me the solution of problem C? I tried it but didn't get the correct approach... :(
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint on test 9? Must have an implementation bug.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    i replaced your detCh function with mine:

    char detCh(int i, int j){
        return (char)((i+5*j)%26 + 'a');
    }

    and received AC.
    you should check all neibours in 5x5 square :)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I got AC to. But still I think there is a problem I don't understand.
In the problem example, the output
aabb
aabb
bbaa
bbaa
is correct. How come? There must be smth else that I'm not taking into consideration.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I've thought about it some more and I found that by checking only N,S,W,E neighbours there is a testcacse I would fail(also taking into consideration that by checking a 5*5 square I would AC).
The test is 2 4 2 2 0. So I need to check SW also. Actually with a little bit more attention I concluded that I only need to check N, W neighbours when I place a or c type boards and when I place b boards I need to check N,W, SW neighbours.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Me again, sorry for overposting. Could you help me with problem E's  Presentation Error on test 35?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    In case of W>=2 and N>=2 solution always exist.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      This comment is weird.
      I get a comment with no author and an author without a comment :))
      If for w>=2 and N >=2 always exists solution, then what is the answer for
      N=3
      W=10
      ni: 2, 4, 3
      ?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Of course we should have w  ≤  sum(ni) as well. Try my tutorial
        :)
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          This is straight-up advertising. Fair competition though. Still my problem remains. Gotta debug more
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Bug Found. Problem ACed. Thank you all.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why WA on test3?
Problem B.
#include<iostream>
#include<string>
using namespace std;
string a;
long int k(long int );
int main(){
cin>>a;
long int j=a.length(),b,d=0,g=0;
long int c=0;
for(long int i=0;i<j-1;i++)
{
         b=k(i);
         if(b>1)
         i+=b-1;
         if(b!=0)
         {
         d=d+b;
         }
         else
         {
         d=0;
         }
         if(d>g)
         g=d;
}
cout<<g<<endl;
cin>>g;
return 0;
}
long int k(long int h)
{
    if(a[h]==')')
    return 0;
    long int s=0,f=0,n=0,j;
    j=a.length();
    for(long int i=h;i<j;i++)
    {
             if(a[i]=='(')
             s++;
             if(a[i]==')')
             f++;
             if(f==s)
             {
             n=i-h;
             return n+1;
             }
    }
    return n;
}
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I wrote the following for A. prime numbers but i am getting WA on test case 11. Can anybody help?


#include<map>
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>

using namespace std;


int main()
{
bool check[70];
for(int i=0;i<70;i++)
check[i] = false;
check[0] = 1;
check[1] = 1;
vector<int> primes;
for(int i=0;i*i<3000;i++)
{
if(check[i]==0)
{
primes.push_back(i);
for(int j=i*i;j*j<3000;j+=i)
check[j] = true;
}
}
int n;

cin>>n;
int last =0;

for(int i=2;i<=n;i++)
{
int count =0;
for(int j=0;j<primes.size();j++)
{
if(primes[j]*2>i)
break;
else if(i%primes[j]==0)
count++;
}
if(count==2)
last++;
}
cout<<last<<endl;
}






→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    You can't simply ignore primes larger than 70. For example, the number 142 is almost prime, but according to your code it's not.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
when will be the next contest?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why RTE???
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<vector>
using namespace std;

#define max 3500
bool prime[max];
void sieve()
{
int i, j;

for(i=1;i<=max;i++)prime[i]=1;

for(i=2;i<sqrt(max);)
{
for(j=i+i;j<=max;j+=i)
prime[j]=0;
i++;
for(;!prime[i];i++);
}
}

int main(){

sieve();
long low, high;low=1;
while(cin>>high){int i,j;
vector<long>count(max,0);long cou=0;

for( i=low;i<=high;i++)
{
if(!prime[i])
for(j=low;j<=high;j++)if(prime[j])if(i%j==0)count[i]++;
}
for(i=low;i<=high;i++)if(count[i]==3)cou++;
cout<<cou<<endl;
}
return 0;}
please give me some case so that i can understand
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Accessing prime[max] is undefined behaviour, AFAIK.
    BTW, your code passes under GNU C++
    → Reply