Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
[VM08] First round - solution (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - [VM08] First round - solution
#1635
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
[VM08] First round - solution 12 năm, 7 tháng trước   (+0)
Here are the solution of first round’s problems:

VSTEPS
Dynamic programming
Let f[i] be the number of way to reach the ith step
If the ith step is broken: f[i]=0
Otherwise, f[i]=f[i-1]+f[i-2]

VTRI
O((X*Y)^3) algorithm: consider all the triple (A,B,C) of verticles and add one to the result if the corresponding triangle has area equal to S. Remember to divide the result by 6. This algorithm earns you 50 points.
O((X*Y)^2) algorithm: The idea is to count equal triangles only once. We fix A(0, 0) to be the vertex with lowest y-coordinate then count the number of triangles that fit inside the X*Y grid. For each one, we add to the result the number of that triangle type which fit in the X*Y grid. To count, we consider all possible coordinates of B and C. This can earn you 100 points.

VTRI2
O(X*Y*min(X,Y)). This algorithm is similar to the previous one except that we only consider B and the y-coordinate (or x-coordinate) of C. Because we already know S, we can determine the other coordinate of C and check if it belongs to the grid.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#1663
vdmedragon (Thành viên)
vdmedragon+5
Không code nữa rồi
Bài viết: 726
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 7 tháng trước   (+0)
VSTEPS

Another solution for this problem is the multiplication of F[j] with j=a[i+1]-a[i]-1;a[0]=0;a[k+1]=n+1.
 
Đã lưu IP Đã lưu IP  
 
  Đã khóa chức năng gửi bài.
#1668
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 7 tháng trước   (+0)
QUOTE:

VTRI2
O(X*Y*min(X,Y))


The problem is solvable faster in O(X*Y*log(min(X,Y)+1)) steps.
For example computing 1600 1600 2400 takes about 12 seconds on my computer (this is a P4 Celeron 1.7 GHz), the answer is 12955978179188.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#1672
Taek (Thành viên)
Đã code là AC
Bài viết: 119
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 7 tháng trước   (+0)
Can you explain it ?
I'm very curious
 
Đã lưu IP Đã lưu IP  
 
About me: ngu dốt, lười biếng, ích kỉ, ki bo, xấu xí, nhút nhát, vô duyên,...........



và khiêm tốn
  Đã khóa chức năng gửi bài.
#1674
vdmedragon (Thành viên)
vdmedragon+5
Không code nữa rồi
Bài viết: 726
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 7 tháng trước   (+0)
With my computer, It took you 121.00000 seconds solve this problem. .
 
Đã lưu IP Đã lưu IP  
 
  Đã khóa chức năng gửi bài.
#1676
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 7 tháng trước   (+0)
QUOTE:

Can you explain it ?
I'm very curious


This is almost the above posted O(X*Y*min(X,Y)) solution, but here we replace the O(min(X,Y)) by O(log(min(X,Y)+1)).
Assume that X<=Y (otherwise swap them).
The triangle's signed area mutiplied by two is area2=(x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-x1*y3), if we fix A=(0,y1) and B=(x2,0) where x2!=0 and y1!=0 then
area2=const+x2*y3+y1*x3. So there are two possibilities:
x2*y3+y1*x3=-const+-2*A (the input area is A, so area2=+-2*A)
the sample solution just iterate x3 from 0 to X and solve the equation (then count how many ways can this triangle in the grid), but we can do it more effiecient way, observe that:
y1*x3==-const+-2*A mod x2 we can solve it in O(log(x2)) steps by extended euclidean algorithm, then we know that if there is a solution, then x3==res mod M, where M=x2/gcd(x2,y1), so we can iterate the x3 values by checking only X/x2*gcd(x2,y1) values only, the expected number of checked x3 values is about log(X) (without proof).
There is another case, where A=(0,0), but it is similar to the above,
here area2=x2*y3-x3*y2.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#2174
temper_3243 (Thành viên)
Đang tập code
Bài viết: 3
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 6 tháng trước   (+0)
I fix one point at 0,0 and other 2 between
(x1,y1) and (x2,y2) , 0<x1,x2<h , -w<y1,y2<w, my code is getting timeout.
It is o(n^3) actually h*h*2*w
What could be wrong below ?

Where is the judge solution code ?

Can anyone send me solution to this problem at Địa chỉ email này đang được bảo vệ khỏi chương trình thư rác, bạn cần bật Javascript để xem nó

Code:
 
#include<stdio.h>
#define mmax(a,b) ((a<b)?(b):(a))
#define mmin(a,b) ((a<b)?(a):(b))
#define myabs(a) ((a<0)?(-a):(a))
int
main ()
{
  int w, h, a;
  long long total = 0;
  register int i, j, p, q;
  int k1, dy, k,z,b1;
  while (scanf (" %d %d %d", &w, &h, &a) != EOF)
    {
  total=0;
  a=2*a;
  b1=w;
  if(h>w)
  {
    b1=h;
    h=w;
    
  }
 
      for (i = 0; i <= h; i++)
  for (j = -w; j <= w; j++)
    {
      if (i == 0 && j == 0)
        continue;
      for (p = 0; p <= h; p++)
        {
    k = (( -a) + p * j);
    k1 = ((p * j) +  a);
    z = ((h + 1) - mmax (p, i));
 
      
 
 
    if (i && j>=0 && (k1%i==0))
      {
        q = k1 / i;
          {
      if (q >= 0 && q <= b1 )
        {
          if (p == 0 && q == 0)
           goto other;
          total += z*((w + 1) - mmax (j, q));
        }
          }
      }
 
 
other:
 
    if (i && (k%i==0))
      {
 
        q = k / i;
        if (p == 0 && q == 0)
          continue;
        dy = -mmin (q, j);
        k=mmax(q+dy,j+dy);
          {
      if ( q>=-b1&& q <= b1)
        {
          if ( k<=w )
            {
        if (p == 0 && (q + dy == 0))
          continue;
        if (i == 0 && (j + dy == 0))
          continue;
        if ( j >= 0 &&  q >= 0)
          continue;
        total += z* ((w + 1) - mmax (k, dy));
            }
        }
          }
      }
 
        }
    }
 
      printf ("%lld\n", total);
 
 
    }
  return 0;
}
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#2220
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 6 tháng trước   (+0)
You may download the official test cases from here
Did you mean O(X*X*Y) by O(n^3)?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#2331
temper_3243 (Thành viên)
Đang tập code
Bài viết: 3
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 6 tháng trước   (+0)
i tried running the tests and they were taking more than 2.5 secs for 9.in 8.in etc.

When i meant o(n^3) was actually O(x*x*2w) instead of O(x*x*w) , we can swap x and w based on minimum one

Is your soln O(x*x*w) or O(x*x*2w) ?

Algorithm is
for(i=0;i<=h;i++)
for(j=-w ;j<=h;j++)
for(p=0;p<=h;p++)
{
1) (i,j in 1st quad) check for cordinate q in 1st quadrant and not origin or the other point but within boundary
2) Check if both js are in 1st , if yes ignore because 1 takes care of that
if not translate the minimum j (-dx) and the other js to j+dx , dx, compute number of triangles
}


It is of the order (h*h*2w), when i evaluate the test case (250*250*500)
250 250 1 (area)
ans is 3618895456
Time is
real 0m2.358s

Now if i reduce that 2w to w (250 125 1 ) (250*250*250)
it is 0m0.641s (approx 1/4 times , is the because of cache misses in the above case ?)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#2371
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: [VM08] First round - solution 12 năm, 6 tháng trước   (+0)
My algorithm is O(x*x*y):
Suppose the triangles have coordinates O(0,0), A(a,b) and B(c,d):
for (int a=-X; a<=X; ++a)
for (int b=1; b<=Y; ++b)
for (int d=b+1; d<=Y; ++d)
- Find c
- Check if OAB is within a x*y rectangle
- Add up to the number of triangles equal to OAB in a x*y rectangle
Besides, you have to consider some boundary cases separately.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS