ConstructorU's blog

SIT Star Contest
By ConstructorU, history, 4 years ago, translation, In English

Hey Codeforces,

SIT

Don’t miss tomorrow’s SIT STAR Contest 2021, organized by the Schaffhausen Institute of Technology (SIT) in Switzerland to promote interest in Computer Science and Software Engineering.

The online coding contest will be happening tomorrow on February 10, from 8:00 to 12:00 am UTC.

During the event, you will face 12 or 13 algorithmic programming challenges of increasing difficulty (Div 4, Div 3, Div 2). The contest is open to all, and you can sign up for free here.

Register Now→

Why participate?

Apart from being a fun coding experience, SIT STAR Contest 2021 is the easiest way to enroll in a fully-funded master’s program in Computer Science and Software Engineering at SIT. The prizes at stake range from small souvenirs from Switzerland to tuition waivers for master’s students to full scholarships the cover both tuition and living expenses.

Note that you must hold a bachelor’s degree or be in the final year of your studies to join SIT in September 2021.

Don’t miss your chance to continue your studies at SIT!

More about SIT

Schaffhausen Institute of Technology is founded by entrepreneurs, led by scientists, and advanced by world-class researchers. Based in Schaffhausen, Switzerland, SIT drives knowledge through science across many projects. In particular, SIT Master’s offers a blended degree in Computer Science and Software Engineering that you can attend in person, online, or as a mix of both.

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

Comments Comments (51)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ANIME NOT GUT!!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will the contest be rated?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

What was the intended solution for Problem K?
Was it SCC+combinatorics or not?
In either case, could someone please share the solution!?

UPD:Got the solution, thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't find my university when registering

So if my university is not in the list I can't participate ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can participate in the SIT STAR Contest. Just add the name of your university by entering it in this field. There is such an option. Thanks!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I am try to login with the credentials provided in the mail. But it says wrong username or password. Please help!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please delete spaces after your email. It should help

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I don't think that it's an issue with the e-mail address. I entered it by hand few times.

          → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I can't able to log in. It is showing "Suspicious activity registered". How to solve this?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I had same issue try to open the site from the first mail they sent for the verification

    → Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I'm trying to log in but it says "Suspicious activity registered. Repeat your action in a few minutes.". What should I do?

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I can't log in using provided password, anyone having the same issue?

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I'm getting this [user:SITstarContest,2021-02-10] Suspicious activity registered. Repeat your action in a few minutes.

Invalid handle/email or password

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with me.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Please make sure that you: 1) Registered here; 2) Received a confirmation letter with the credentials to log in. 3) Enter the data in the field without adding a space before or after;

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can't login.

Suspicious activity registered. Repeat your action in a few minutes.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me, too. What happened?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Please for entering the contest use the credentials we sent you in the email. When you enter credentials, please delete all the spaces after the email.

      It should help.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It doesn't help

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm copy/pasting the same but it still shows the same error: suspicious activity, and invalid handle/password

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Same with me . Help !

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please make sure that you: 1) Registered here; 2) Received a confirmation letter with the credentials to log in. 3) Enter the data in the field without adding a space before or after;

      → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Contest was nice, but unfortunately, Problem M — Binary Strings was available on SPOJ.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

willl there be prizes for top 70?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will there be a Editorial?

And how to do the problem -> (a, b) becomes (a + b, b) or (a, a + b).
Just came up with a BFS solution, but that would TLE obviously.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's like Euclidean algorithm for GCD. Our task is in minimization of given pair (x, y) and we can do the following transformation in one operation: (x, y) -> (x, y — x). Of course we can do it only with x < y. Notice that the order of numbers in pair doesn't matter(if we have (a, b), then we also have (b, a)). Then, just find is it possible to get (1, 1) from (x, y). You can do it iteratively, with one easy optimization(try it by yourself)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks got it but how to prove that going from (x, y) to (x, y%x) will give the minimum possible answer ?

      My Solution for E : https://pastebin.com/EF1M9G3V

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The smaller the difference between x and y, the faster numbers will decrease, right? So when you are doing y = y % x, you will get y between 0 and x — 1. You can not get something more closer to x

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The editorial was posted here https://drive.google.com/file/d/1CrBz9Ddk7LaLRhnjizUAo7IWv9JmOO-e/view

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution to the problem Cards and Numbers?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    We can use one or two the most frequent numbers. While counting the numbers, try to avoid cases, when a[i] == b[i].

    → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is it possible to submit for practice after the contest is over?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

could you please enable viewing other people's submissions? thanks

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

do we have an online mirror for the contest ??

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to be part of the group? I want to check the editorial but I can't view it. I am not able to find the invite anywhere. Where it was sent?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you register for the SIT STAR Contest? If yes, please check your promotions folder or spam for the link and your credentials. If you still can not find the email with the link and credentials, please contact us via messages here.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I participated in the contest. I have the credentials. How to view using them?

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

where i can find editorial ? I found https://sitstar2021.contest.codeforces.com/group/1HLBM0lmlk/blog pdf https://drive.google.com/file/d/1CrBz9Ddk7LaLRhnjizUAo7IWv9JmOO-e/view

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

When we will know about prizes and the free Master Degree program?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Winners will be announced next week.

    Thank you for your participation and interest in SIT! We hope you enjoyed the problems!

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you please allow us to view the submissions of other participants?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody show their solution to problem G? I read the editorial but still a little confused about it.

Thanks in advance.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am sharing my solution here, but note that it's for $$$O(|s|^2)$$$ which is a little overkill for this problem.

    Suppose there are 1000 rows and the string s is "abc".

    Now, let's consider how many solutions exist if you start at the first position of the first row. It's basically $$$2^{|s|-1} = 2^2$$$ (because you have two steps you can go from the first position: a->b, b->c; and in each step you can go either down or right).

    Note that the number of solutions for row 2, 3, 4, 5.... 998 is the same as well. So you can just add $$$998 \times 2^2$$$ to answer for that.

    Now, what about the rest? Consider row 999. In this case, the number of solutions is no longer $$$2^2$$$ as you can't go down twice. Note that there can be $$$|s|-1 = 14$$$ such rows at most. So for those, we can just do a DP where states are the number of rows left and the current position in string i.e. $$$O(|s|^2)$$$ complexity.

    The DP formula is $$$DP[rowLeft][pos] = DP[rowLeft][pos+1] + DP[rowLeft-1][pos+1]$$$.

    Here, the first term $$$DP[rowLeft][pos+1]$$$ represents going one step right, the second term $$$DP[rowLeft-1][pos+1]$$$ represents going one step down (this might be invalid, so that condition needs to be checked). The reasoning is like — when you go one step right or down, you are going into next position of string s, and when you are going one step down, you have one less rowLeft.

    See how this will fit in constraints of the original problem even if $$$rowLeft \leq 10^4$$$? That's the idea shown in the editorial. Just instead of rowLeft, they used something like currentRow and incremented that instead of decrementing (will give same result).

    Here's my code written based on the above idea.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Please could you make the test cases visible for the Practice and Main contests, now that they are over?

In particular in the case of the Practice contest, in the absence of an editorial I am at a loss on question K. With no editorial, no access to others' solutions, and no visibility of test case 22 (which I keep failing), it's very difficult to know what I've done wrong.

Thanks

→ Reply