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

Автор yash_chad, 3 года назад, По-английски

Hello Codeforces!

Greetings from DJ Codestars, the official Coding committee of DJ Sanghvi College of Engineering.

We are back with a very unique and interesting coding contest: CONSIZE, a 2-hour long coding contest!! Here, participants will be given 2 hours to solve 5-6 problem statements, with increasing difficulty.

The twist here is that, the score you get is inversely proportional to the length of your code!

To make things even more interesting, the problem statements will be themed around your favourite Netflix shows. Stand a chance to win super exciting prizes, goodies and subscriptions!

Date : Saturday, November 20, 2021 at 5:00pm IST
Duration : 2 Hours
Registration Link: C++ Java Python

Fill in the form to be eligible for prizes and receive all future announcements/updates

Instructions / Rules :

So what are you waiting for? Hurry up and register yourselves for the contest.

Editorials

Problem: Kota Anomaly

Tutorial
Solution-cpp
Solution-java
Solution-python
C++ shortest code by h2972737475
Java shortest code by rohinth076
Python shortest code by tehlka

Problem: Emily and her team

Tutorial
Solution-cpp
Solution-java
Solution-python
C++ shortest code by karan221
Java shortest code by vinayakj592
Python shortest code by h1015634

Problem: Tokyo need Guns

Tutorial
Solution-cpp
Solution-java
Solution-python
C++ Shortest Code Submission by h2067571606
Java Shortest Code Submission by vinayakj592
Python Shortest Code by h1015634

Problem: Old Jonas loves Young Martha

Tutorial
Solution-cpp
Solution-java
Solution-python
C++ Shortest Code Submission by Minindu2006
Java Shortest Code Submission by kishore_shiyam
Python Shortest Code Submission by h1015634

Problem: Ammo Expectation

Hint 1
Hint 2
Tutorial
Solution-cpp
Solution-java
Solution-python
C++ Shortest Code submission by h2067571606
Java Shortest Code submission
Python Shorest Code submission by h1015634

UPD 1: Rule 3 has been updated.
UPD 2: Editorial for Ammo Expectation has been added, with shortest codes. Editorials and shortest codes for other problems will be added soon.
UPD 3: Editorials and Shortest Code Submissions have been added for all problems

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

great , damn excited to take part in it

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's coinciding with Atcoder ABC Contest please change the timeing?

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Different Codegolf contest link for every language? This is something unique!

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Interesting idea! What is the exact criteria/formula for awarding score on basis of length of code? Looking forward to participate!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The score assigned will be Sum $$$\sum_{}^{} k/(number Of Characters)$$$ over all accepted test cases. Here $$$k$$$ is a constant.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Once you register for one language say C++, you CANNOT participate in another language's contest.

I'm considering choosing either Python or C++ but I want to do the one with more people (because that'll have more competition :) so will we know how many people signed up for each language?

Also, why can we not register for multiple languages? If I'm not from India I won't be receiving any prizes anyway, so there won't be the problem of one person getting first in all three. Perhaps you could add an option "Register but with no prize" for other languages?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    At the moment we have maximum signups for C++, followed by Python and then Java.

    Yes you can participate in multiple contests, however you won't be considered for prizes in any of them. The changes can now be seen in Rule 3.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can you elaborate on what the prizes will be and how many will be eligible for the prizes?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

score you get is inversely proportional to the length of your code!

yash_chad please clarify what do you mean by length of code.

Is score will be given by the number of characters or number of lines in code

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Rule 5 says "The scoring system revolves around the length of your code. The shorter the code the more points you get as long as your code passes all the required test cases. Tabs, newlines and spaces don't contribute to character count."

    So only count of characters count (excluding tabs, newlines and spaces)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As dedsec_29 mentioned, the score will be inversely proportional to the number of characters in your code!

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Excited to take part in this event!!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are ties broken by number of problems solved or time taken ?? .

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    First the summation of total score of all questions solved by the participant is considered, if there's still a tie then it is resolved by the time taken

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I filled the registration form and received an email confirmation for the contest registration. However, no link to the contest appears in my HackerRank account. Am I missing something?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The link to the contests is given in this post itself, you need to use the same link you used for registration

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

I have a feeling that the problem names are

Spoiler

just guessing....

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Original Post

Edit: Nevermind, it has just been added.

Note: In the input format it says

A0, A1, A2, .., An

shouldn't the indexing start from $$$1$$$ instead of $$$0$$$?

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

damm i was able to solve 4 problem but i don't know about expected value and it's calculation
can somebody provide me a good tutorial or blog where i can learn this concept

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Thanks for the contest!

I am the winner of the Python contest (I'm not Indian so I'm ineligible for prizes), and managed to get the shortest in-contest python codes on all problems apart from the first one. I thought I'd share my codes here.

# Problem 1
f=input
f()
s=f()
print(sum(i!=j for i,j in zip(s,s[1:]))+1)

# Problem 2
f=lambda:[*map(int,input().split())]
for w in ' '*f()[0]:
    n,b=f()
    l=[b]*4
    for i,j in zip(f(),f()):
        l[j]=min(l[j],i)
    print('yneos'[sum(l)>b::2])
    
# Problem 3
n,x,*a=map(int,open(0).read().split())
t=x-1
print(min(a[i+t]-a[i]+min(abs(a[i]),abs(a[i+t]))for i in range(n-t)))

# Problem 4
n,*s=map(int,open(0).read().split())
s.sort()
print(sum(s[i]*(2*i-n+1) for i in range(n)))

# Problem 5
from decimal import *
n,k,*a=map(int,open(0).read().split())
m=4**10
p=[1]*m
s=[set()for i in' '*m]
for i in range(2,m):
    if p[i]:
        for j in range(i,m,i):
            p[j]=0
            s[j]|={i}
            
r=0
for x, y in zip(a, a[1:]+[a[0]]):
    z=m=Decimal(x*y)
    for i in s[x]|s[y]:
        z-=z//i
    r+=k*2*z/m
print(r)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Interesting how we reached almost exactly the same code!

    Note that I forgot whitespace wasn't counted so I was using semicolons everywhere until almost the end, oops. Also I didn't change a few things that would've reduced the char count.

    1) I used input() instead of your f() because I didn't have enough time to change it :( otherwise it's exactly the same. Nice how you can cast a bool to an int in Python.

    2) Added just now, but the following is shorter:

    P=lambda:map(int,input().split())
    t,=P()
    while t:
     n,b=P()
     s=[b]*4
     for p,x in zip(P(),P()):s[x]=min(s[x],p)
     print('yneos'[sum(s)>b::2])
     t-=1
    

    Mainly it's because changing the for-loop to a while loop is shorter. Also note the clever unpacking in t,=P() by using the comma equals operator

    3) Two seconds too late, the following is shorter:

    P=lambda:map(int,input().split())
    n,x=P()
    a=*P(),
    print(min(min(abs(C),abs(D))+abs(C-D)for C,D in zip(a,a[x-1:])))
    

    Note that using

    n,x,*a=map(int,open(0).read().split())
    

    instead of the first three lines is shorter. It got me 75.8 points.

    4) I was doing something slightly different, but I guess it ended up producing a longer solution:

    P=lambda:map(int,input().split());P();t=s=i=0
    for x in sorted(P()):s+=i*x-t;t+=x;i+=1
    print(s)
    

    Ugh those semicolons again

    Using your method and tweaking it a bit (walrus operator!) it's a little shorter:

    n,*s=map(int,open(0).read().split())
    i=0
    print(sum(x*((i:=i+2)+~n) for x in sorted(s)))
    

    5) I improved a few things to get this:

    from decimal import *
    n,k,*a=map(int,open(0).read().split())
    m=1<<20
    s=[set()for _ in '.'*m]
    for i in range(2,m):
        if not s[i]:
            for j in range(i,m,i):
                s[j]|={i}
    r=0
    for x, y in zip(a, a[1:]+[a[0]]):
        z=Decimal(1)
        for i in s[x]|s[y]:
            z-=z/i
        r+=z
    print(2*k*r)
    

    Note that the p array to check if a number is prime is redundant, because we can just check that the length of the prime factors set s[i] has length 0.

    I especially don't like that we need to use decimal.Decimal because of precision errors. The constraints should have been lowered instead.

    Here are the stats of my submissions:

    Problem In-contest After contest
    $$$1$$$ $$$55.6$$$ $$$56.6$$$
    $$$2$$$ $$$56.8$$$ $$$58.6$$$
    $$$3$$$ $$$58.58$$$ $$$75.8$$$
    $$$4$$$ $$$67.4$$$ $$$74.1$$$
    $$$5$$$ $$$27.58$$$ $$$79.9$$$

    I believe that the solution for 1 is optimal, but I want to keep trying to golf the rest.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Very cool, nice optimisations! Congrats on second place too!

      I spent most of the contest trying to debug problem 5, and only realised near the end of contest that I should have used the Decimal class (oops, should have thought of that earlier). So most of my time was spent debugging, not optimising the rest of the code. For most of the contest, my codes were not the shortest. Only in the last 15 or so minutes of the contest did I go back over my old codes and add optimisations such as

      n,x,*a=map(int,open(0).read().split())
      

      Also, looking at the leaderboard, I had so many points over the rest of the competitors that I didn't really have the motivation to grind for tiny optimisations with little score change. This was especially due to the fact that nobody else got AC on all test cases on problem 5 using python during the contest (I presume; either that, or the other person had extremely long code).

      Finally, somebody got a score of 60.0 during the contest for Problem 1, so my solution is definitely not optimal. I would be extremely curious to know what the optimal solution is!

      Can't wait for a similar contest in the future! (Hopefully someone makes one soon)

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

        The following code gives 63.8 points on problem 1: Walrus operator to the rescue!

        q=f=input
        f()
        print(sum((p:=q)!=(q:=y)for y in f()))
        
»
3 года назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

Great contest, i secured 4th rank. Kudos to abhinav sharma. My c++ codes:

Tokyo_need_Guns
Emily_and_her_team
Kota_Anomaly
Old_Jonas_loves_Young_Martha
Ammo_Expectation
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is the time complexity of your code for Ammo Expectation, is it O(n * log(m) * m)? m being max(Ai)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Here $$$h(n)$$$ is the phi function used from cp-algorithms. It's time complexity is $$$O(\sqrt{n})$$$. Overall time complexity is thus $$$O(n\sqrt{m})$$$.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You are calculating phi of values as big as 1012 along with gcd, total N times. Calculating phi using the sqrt algorithm will take O(sqrt(m2) + log(m)) time, i.e. O(m + log(m)) => O(m). Overall time complexity of your code seems to be O(n * (m + log(m))) => O(n*m)).
        Your code shouldn't pass in the time limit, but it did pass :0
        I had tried submitting O(n * (m + logm)) solution too but it TLEd. I think your solution shouldn't have passed. Is there anything wrong with my analysis?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          You are calculating phi of values as big as 10^12 along with gcd

          No h(a) is only called for value <= 10 ^ 6. I have used h(a, b) for calculating phi(a * b) which as time complexity O(sqrt(max(a, b)).

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Oh I missed that, my bad. Your solution then seems to be O(n*sqrt(m)), roughly 106 * 103 = 109 calculations. I still think it shouldn't have passed, test cases should've been tighter. Let me know again if I have analyzed anything incorrectly

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

My thoughts on the contest:

It was a very unique idea to have codegolf + competitive programming + 2 hours for the contest. I thought it was very fun.

Also, maybe if you do this again, have the contest be longer? I still feel like I had more to golf but the time was up. I think 3 hours would be better.

Note: Having the score depend on code size actually presented a decision to make: Do I reduce the size of the code for this problem or this other one? I really liked this aspect of the contest.

I missed the submission of the third problem by 2 seconds, which would've given me 9 more points. Luckily that didn't make me go down in the standings though!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you for your feedback on the contest!
    Sure, we will keep this in mind to have a longer contest of 3 hours next time, maybe with 6 problems? Or 5 problems but with higher difficulty. Let us know what you think sounds more fun

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      I don't think the problems should be made any harder — the contest is mainly a code golf contest, not a CP contest, and if the problems are made any harder, there may not be enough time for optimising code length. Already as it is, for the Python contest, only 3 users scored any points on the last problem, despite it not being particularly difficult (and I believe I was the only one who passed all test cases, although that was probably more due to precision errors than problem difficulty).

»
3 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Interesting contest, but the scoring system has a big issue — spaces and tabs can represent data, they shouldn't be simply ignored.

Here's a demo: Python code. It uses only "67 characters", and achieves full score easily on Ammo Expectation. However, the real code is encoded as binary text, and replaced with tab and space.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Yes, and it's on cses as well. I sent a dm to pllk a while back, so hopefully it'll be fixed soon. I was talking about Ruby but the same can be done, as you've shown, in Python. In essence, I suggested the following ideas:

    • Not take submissions if they have 100 consecutive whitespaces (or some other limit)
    • Only check that the 100 consecutive whitespaces are in a string. Now, I realize this can be bypassed by reading your own source code.

    The best solution would just be to count whitespace as well though. Perhaps only count \r\n as one character though.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      I think we may count the spaces in strings, and disable the program from reading its own source code.

      Counting all whitespaces is a good solution, but I think it increases coding difficulty, and is not the best option for a 2 hour contest.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I am surprised that contestants can exploit encoding into spaces. Thanks for bringing this to our attention. Counting all whitespace seems like a good idea. Also taken Ritwin's suggestions. We will experiment with the hackerrank custom_checker to score without letting the program read its own source code. I am not so sure how to achieve this right now.