Hey Codeforces!!

Greetings from NJACK, the Computer Science Club of IIT Patna,

We present to you ByteRace 2k20, as a part of our annual technical fest, Celesta.

The contest will be held on Codechef and is rated for all Div2 participants! (Rating < 1800)

Date and Time: It will take place on 29th December 2020, 20:00 IST to 22:30 IST. (IST = UTC+5.5)

It will be an ICPC styled contest with 7 problems.

Link to the contest: https://www.codechef.com/BYTR2020

We would like thank our problem-setters: V_S_M, jenishmonpara, aditigoel, Crocuta, 100gods and our organizers: kunj017 and hackcyborg.

Special thanks to the round coordinator jtnydv25 and our testers: darklight13, Nightmare05, aditya_sheth, l_returns and 7dan for their invaluable contributions.

Prizes:

Global Ranklist

1. ₹5k

2. ₹3k

3. ₹2k

Indian Ranklist (Apart from top 3 global)

1. ₹2k

2. ₹2k

IIT Patna Participants

1.₹500

2.₹500

Coupons and goodies worth ₹5k to 20 random participants!

To register for prizes fill this form before the contest: https://forms.gle/RrdUuwZUtGj6CKqW9

Hi guys,

I gave the Newton's coding challenge held today and could solve only 4, I got 15+ WAs on 5th and couldn't solve the 6th problem. Can anyone please tell me the solution for the last problem and if possible tell me the error in my code for 5th problem?

Also feel free to use the comment section to discuss other solutions as well.

Please visit this link to see a screenshot of the problem statement of P5

//Nightmare05
#include<bits/stdc++.h>

using namespace std;

#define sp << " " <<
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define int long long
#define double long double
#define INF (1e18+13)
#define PI 3.1415926535898

int power(int p,int j)
{
    int res=1;
    p=p%mod;
    while(j>0)
    {
        if(j&1)
            res=(res*p)%mod;
        j=j>>1;
        p=(p*p)%mod;
    }
    return res;
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dice(int d,int p)
{
    uniform_int_distribution<int> uid(d,p);//specify l and s.
    return uid(rng) ;
}

double s(double m1,double m2,double c1,double c2,double c3,double c4)
{
    double x1,x2,x3,x4,y1,y2,y3,y4;
    x1=(c2-c1)/(m1-m2);
    x2=(c3-c2)/(m2-m1);
    x3=(c4-c3)/(m1-m2);
    x4=(c1-c4)/(m2-m1);
    y1=m1*x1+c1;
    y2=m2*x2+c2;
    y3=m1*x3+c3;
    y4=m2*x4+c4;
    double d[4];
    d[0]=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
    d[1]=(y3-y2)*(y3-y2)+(x3-x2)*(x3-x2);
    d[2]=(y4-y3)*(y4-y3)+(x4-x3)*(x4-x3);
    d[3]=(y1-y4)*(y1-y4)+(x1-x4)*(x1-x4);
    sort(d,d+4);
    if(abs(d[3]-d[0])<0.01)
        return sqrt((d[0]+d[3])/2)+26.0;
    else
        return -1;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("elimination_validation_input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t;
    cin >> t;
    while(t--)
    {
        double dp=-1;
        double x1,x2,x3,x4,y1,y2,y3,y4;
        pair<double,double> a[4];
        cin >> a[0].first >> a[0].second >> a[1].first >> a[1].second >> a[2].first >> a[2].second >> a[3].first >> a[3].second;
        for(int j=0;j<6;j++)
        {
            if(j==1||j==3||j==5)
                swap(a[2],a[3]);
            if(j==2||j==4)
                swap(a[1],a[3]);
            x1=a[0].first;
            y1=a[0].second;
            x2=a[1].first;
            y2=a[1].second;
            x3=a[2].first;
            y3=a[2].second;
            x4=a[3].first;
            y4=a[3].second;
            for(double i=0.0;i<=1.0;i+=0.0001)
            {
                double m1=i*PI;
                m1=tan(m1);
                double c1=y1-m1*x1,c3=y3-m1*x3;
                double m2=-1/m1;
                if(m1==0.00000)
                    m2=tan(PI/2);
                double c2=y2-m2*x2,c4=y4-m2*x4;
                int h=1;
                double p[3];
                p[0]=y2-m1*x2-c1;
                p[1]=y3-m1*x3-c1;
                p[2]=y4-m1*x4-c1;
                if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y1-m2*x1-c2;
                p[1]=y3-m2*x3-c2;
                p[2]=y4-m2*x4-c2;
                if(abs(p[0])>abs(p[2])||abs(p[1])>abs(p[2]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y2-m1*x2-c3;
                p[1]=y1-m1*x1-c3;
                p[2]=y4-m1*x4-c3;
                if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                p[0]=y2-m2*x2-c4;
                p[1]=y3-m2*x3-c4;
                p[2]=y1-m2*x1-c4;
                if(abs(p[1])>abs(p[0])||abs(p[2])>abs(p[0]))
                    h=0;
                sort(p,p+3);
                for(int z=0;z<3;z++)
                    if(abs(p[z])<0.0000000001)
                        h=0;
                if(p[0]*p[2]<0)
                    h=0;
                if(h)
                    dp=max(dp,s(m1,m2,c1,c2,c3,c4));
            }
        }
        if(dp<26)
            cout << -1 << endl;
        else
            cout << fixed << setprecision(2) << dp << endl;
    }
    return 0;
}

I would be really thankful if someone can point out, exactly what edge cases did I miss!

Cheers!!!

Hi guys,

I just messed up Code Jam round 2 today and my Code Jam journey is done for the year, so I was wondering about Hackercup, but I didn't find any announcement on their Facebook page. So, can someone please confirm if it's announced somewhere and I missed it or just is it going to happen this year or not?

Thanks a lot in advance!!

Hello guys!!

Greetings from NJACK, the Computer Science Club of IIT Patna,

We feel very excited to announce our very first edition of Apeireon , the annual coding fest of the Department of Computer Science and Engineering, IIT Patna. The fest will be packed with a plethora of fun events.

I would love to thank you all for the huge participation in our Hacking Challenge and making it a grand success,

Introducing this time, Code Golf, a competitive coding event in which the aim is to solve problems while writing as short code as possible.

Imagine you are giving a coding contest and have spent the last 20 minutes on a problem and finally you submit it and it's accepted. You later find that some top-level coders have done it in less than a minute! What is their secret? Do they have a typing speed more than 20X that of a normal person? The real answer is NO, usually a high speed isn't the result of unusual typing speed, but that of super-short and elegant code. In fact, it often seems that code length is inversely related to coder strength and hence it's good to encourage the writing of short code.

Date : 6th April, 2020

Timings : 9:00pm — 11:00pm

Duration : 2 hours

Platform : HackerRank

Language : C++ only

Rule Book : http://bit.ly/CodeGolf

Registration : https://forms.gle/zv1ZzGmhvG4yKMYc7

Contest link :https://www.hackerrank.com/apeireon-code-golf

Prizes :-

First : 5000/-

Second : 3000/-

Third: 2000/-

Along with a lot other exciting goodies.

For any further queries, please feel free to contact : Ankit Singh (+91-9523867146)

Lastly, I would love to introduce the problem setters for the contest to you all : DeepThought42, Sixpathsguy, Adarsh_kc, Diksha11 and baba_yaaga

For more such fun events do check our Facebook page : https://www.facebook.com/njack.iitp/

Hope to cya all on the leader board!!

Hello guys!!

Greetings from NJACK, the Computer Science Club of IIT Patna,

We feel very excited to announce our very first edition of Apeireon , the annual coding fest of the Department of Computer Science and Engineering, IIT Patna. The fest will be packed with a plethora of fun events.

Hope you all had fun debugging codes in our hacking challenge.

Introducing this time, Mystery Language, an event that requires you to code a contest in a language which would be announced minutes before the contest.

A Competitive Programming contest with a slight difference, submit your solutions in a language, which might be unknown to you. The language will be announced 20 minutes prior to the contest. The contest will have 5-6 problems. This will give everyone an opportunity to evolve your skill to quickly adapt to a newly given framework or technology which is a very important skill in today’s rapidly growing techno-management corporate world.

Mystery Language Reveal : Scala

Date : 2nd April, 2020

Timings : 9:30pm — 12:30am

Duration : 3 hours

Platform : Codechef

Rule Book : https://bit.ly/2J1Hgx8

Registration : https://bit.ly/3aqLbzo

Contest link : https://www.codechef.com/MYL2020

Prizes :-

First : 5000/-

Second : 3000/-

Third: 2000/-

Other than the aforementioned there would be : 250 CodeChef laddus to all the 3 winners, which can be redeemed for awesome CodeChef goodies.

CodeChef DSA certification scholarship : 75%, 50% and 25% scholarship respectively for the top three participants.

CodeChef DSA certification scholarship : Additionally there would be a discount coupon of INR 200 for all the participants.

For any further queries, please feel free to contact : Shresth Walia (+91-9650771103)

Lastly, I would love to introduce the problem setters for the contest to you all : hackcyborg, smasHR, LightYear and StarnyC

For more such fun events do check our Facebook page : https://www.facebook.com/njack.iitp/

Hope to cya all on the leaderboard!!

Hi guys,

We recently gave ICPC regionals at Asia-Kharagpur site and there were some problems that we couldn't solve within the allotted time and we aren't yet allowed to make submissions on online mirror round on codechef, so is there any other way/loophole which we can use to make practice submissions on those problems now, we really wanna test our codes.

Any help would be appreciated.

Hi guys,

I would like to thank all participants for making this event a grand success and specially thank ck98, darklight13, LightYear, kunj017, scameeer, leviOosa and hackcyborg for the problem setting and testing efforts and specially for actively managing the queries during contest!!

So, without wasting more time I'd like to congratulate our winners:

1. nuip

2. Amoo_Safar

3. fugazi

4. kimden

5. scopeInfinity

Based on the leaderboards following people have qualified for prizes:

Overall top 3:

1. nuip

2. Amoo_Safar

3. fugazi

Top 5 Indians:

1. fugazi

2. scopeInfinity

3. cerberus97

4. _shanky

5. hitman623

Top 2 from IIT Patna(presently studying):

1. intruder_p

2. DeepThought42

Winner from 1st year IIT Patna

1. pac-man21

Editorals!

Is It Some Space Cakewalk?

Problem Author: darklight13

The main idea for problem was pigeon-hole principle i.e in worst case we pick all the different type of cakes first and then any additional cake would make a pair repeat. So the answer to the problem was number of different types of cake in the list + 1.

Time Complexity O(n+max(T)).

Author Solution

Kunj Destroys Asteroids in 13th Dimension

Problem Author: darklight13

This problem can be solved in many ways like prefix sum , window sliding or even binary search.

I will discuss one with partial sum. The equation of the rhombus can be represented by |x| + |y| = X. Thus we only need the manhattan distance of the points. We make a prefix array that will store number of points less than or equal to manhattan distance i for each i. We calculate the points lying between X and X+K using prefix sum for each X where X is prime which can be computed by sieve. For each X the number of points lying between the rhombi would be pre[X+k] — pre[X-1]. Maximum of all such iterations will be the answer.

Author Solution

1-2-3 Subsequence

Problem Author: scameeer

The naive solution of iterating from l to r for each query will give TLE. Thus we use segment tree. At each node in the segment tree we store 6 values. 1. Length of maximum subsequnce strating from 1 and containing only 1. 2. Length of maximum subsequnce strating from 2 and containing only 2. 3. Length of maximum subsequnce strating from 3 and containing only 3. 4. Length of maximum subsequnce strating from 1 and containing only 1 and 2. 5. Length of maximum subsequnce strating from 2 and containing only 2 and 3. 6. Length of maximum subsequnce strating from 1 and containing only 1, 2 and 3. Now when building the segment tree you can maximize these values at each node to get the answer. At each node combine when with possible combinations like 1+(2-3), (1-2)+3, 1+(1-2), (1), (2), (3), (1-3)+3, 1+(1-3). The answer to each query will be the maximum of the above values. This can be better understood in editorial code. A much clean solution can be: https://codeforces.me/blog/entry/71357?#comment-558146 Thanks to fugazi

Author Solution

Universe is random, but is it?

Problem Author: Nightmare05

First off, we begin by observing that since average of a child is his average over all exams he appears in, the expected score of a child is independent of E (the number of exams he appears in) and by a similar argument the answer is independent of N (number of students) as well. So, we know that answer is a function of M (maximum marks) and K (number of re-evaluations only) f(K,M). And now observe, a child would go for re-evaluation only if he scores less than or equal to f(K-1,M) else he won't go for further re-evaluations.

Author Solution

Divide the Country

Problem Author: LightYear

For this problem in particular we saw a lot of creative solutions. But still for the sake of editorials, here is the solution we thought.

First, check if the given graph is a tree. If yes, then output n — 1. If not then there exists at least one cycle. Choose any vertex which is part of a cycle. Let's call it u. Run dfs from u. Now suppose you are currently at vertex v. If there is a non-bridge vertex in the dfs subtree of v then you obviously cannot remove the edge between v and its parent and it is no longer a candidate for the answer. After checking that condition if the edge between v and parent of v is still a candidate then it means that the dfs subtree of v consists only of bridges. Keep track of the diameter of the subtree. If diameter is same as the current maximum diameter then check for the number of nodes in the subtrees.

Author Solution

Will You Win The Prize?

Problem Author: leviOosa

The question is given as if it has to be solved online, but actually it is an offline question. Take all the characters given in all queries in sequence to make a string (S1). The given string is named as (S). Make string (T)=S1+#+S. Now apply “KMP” on this string (T). In the array obtained by KMP take the answer from (n+1)th index to (2n)th index. This is our required l(i). So, ans(i)=l(i)*2^i. It’s easy to calculate the binary representation of ∑(i=1 to i=n) ans(i). Refer to the solution code for better understanding.

Author Solution

Yet Another Permutation Array!

Problem Author: scameeer

With the given cumulative sum array A, find out the elements in the array P. This can be easily done by knowing how cumulative array get build. The first element of the cumulative array will also be present the array P. The rest elements can be found using A[i]-A[i-1] for all i>=1 to n-1 (0-based indexing). Now in these conditions answer will be -1: 1. The number of distinct elements in P are not n. 2. If the distinct elements are n, all integers from 1 to n are not present. This can be done by storing the above made P array elements in set data structure and iterating them. In all other cases answer exists. Print the array P formed.

Author Solution

Binary Matching

Problem Author: Nightmare05

Since a lot of people were interested in the proof of this problem specially, I decided to write a complete rigorous proof and well since some stuff is mathematical I am writing on paper and uploading pics. Pic 1 Pic 2

Author Solution