Replay of Intra RUET Junior Contest (Round 1)

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Hello, Codeforces community.

It is my pleasure to invite you all to the replay contest of Intra RUET Junior Contest (Round 1), which took place two days back with the beginner contestants of Rajshahi University of Engineering & Technology. The contest will follow the format of regular ICPC contests.

The contest will be suitable for beginners (ie. Codeforces Div3 contestants) but we invite you all to participate for fun. :D

Contest Link: https://toph.co/c/intra-ruet-junior-contest-round-1-r

Start time: 19:15(+6GMT) 10/08/2020

Duration: 3 hours

Number of Problems: 7

The contest platform is toph.co, you can register for the contest here.

The problems of the contest were reviewed, authored and tested by Shefin_, I_love_ProParThinkNot, Hasnaine_, tanus_era, wan-_-s, Abdur_Rahman_Shajib, Hasinur_, tahsin_protik, Moshiur_, tux, JOYTUN_17, Complexity_Cutter, Salam_35, Emama.emu

We look forward to your participation and hope that you enjoy the problem set, best of luck in the contest.

UPD: The editorial for the problems are click here

Комментарии (6)

Написать комментарий?

wan-_-s

4 года назад, # |

Remainder: less than an hour remaining to start the contest.

→ Ответить

4 года назад, # ^ |

10m remaining.

muhammadhasan01

How to solve B? I used two dp for prefix and suffix, but I don't know what's wrong :(

← Rev. 3 →

Its can be solved by using dp for suffix and prefix. For a certain position i if (i>0) then if there is a way to make sum equal to X using first i-1 pairs then check there is any possible way using rest pairs except i-th thus sum is equal to (M-X).

tahsin_protik

You can check out the editorials. We've uploaded it just now.

AK.

I also used suffix and prefix dp .

Code

#include<bits/stdc++.h>
using namespace std;
int lft_dp[101][10001];
int rgt_dp[101][10001];
int n,m;
int a[101],b[101],ok[101];
int solve(int pos,int sum)
{
    if(sum<0)return 0;
    if(pos>n)
    {
        if(sum==0)return 1;
        else return 0;
    }
    int &ret=rgt_dp[pos][sum];
    if(ret!=(-1))return ret;
    ret=0;
    if(solve(pos+1,sum-a[pos]))ret=1;
    if(solve(pos+1,sum-b[pos]))ret=1;
    return ret;
}
int sol(int pos,int sum)
{
    if(sum<0)return 0;
    if(pos<1)
    {
        if(sum==0)return 1;
        else return 0;
    }
    int &ret=lft_dp[pos][sum];
    if(ret!=(-1))return ret;
    ret=0;
    if(sol(pos-1,sum-a[pos]))ret=1;
    if(sol(pos-1,sum-b[pos]))ret=1;
    return ret;
}
void s()
{
    memset(rgt_dp,-1,sizeof rgt_dp);
    memset(lft_dp,-1,sizeof lft_dp);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    solve(1,m);
    sol(n,m);
    int pos=-1,dan,bam;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            int rgt=j;
            int lft=m-j;
            if(sol(i-1,lft) && solve(i+1,rgt))
            {
                 pos=i;
                 bam=lft;
                 dan=rgt;
                 break;
            }
        }
    }
    if(pos==-1)
    {
        printf("NO\n");return ;
    }
    printf("YES\n");
     for(int i=pos-1;i>=1;i--)
    {
        if(sol(i-1,bam-a[i]))
        {
            bam=bam-a[i];
            ok[i]=1;
        }
        else
        {
            bam=bam-b[i];
            ok[i]=2;
        }
    }
    ok[pos]=0;
    for(int i=pos+1;i<=n;i++)
    {
        if(solve(i+1,dan-a[i]))
        {
            dan=dan-a[i];
            ok[i]=1;
        }
        else
        {
            dan=dan-b[i];
            ok[i]=2;
        }
    }
   for(int i=1;i<=n;i++)
   {
       if(i!=n)printf("%d ",ok[i]);
       else printf("%d\n",ok[i]);
   }

}
main()
{

   int t;
   scanf("%d",&t);
   while(t--)s();
}

Блог пользователя tahsin_protik