xodiac's blog

Invitation for IUPC (Inter University Programming Contest)
By xodiac, history, 5 years ago, In English

Hello CodeForces community,


Do you have the spontaneous rationality to solve problems? Do you like to be logically challenged?
Cybros in association with Aavas presents IUPC'19 — a team based Inter University Programming Competition pertaining to the guidelines of the world famous ACM-ICPC .

We are delighted to invite you to this Coding Competition organised by The LNM Institute of Information Technology – Jaipur, during the two day Techno-Management-Literary Fest Plinth'19 to be held from 19th – 20th January, 2019.


The contest shall be a great opportunity for students to whet their programming aptitude. This national level programming contest shall assess the intelligence of participants through various rounds. It is an Online Qualifier Round for the Onsite Round to be held during Plinth'19.

There will be 2 rounds to decide the winner:
1. First Round: Online round will be held on 6th January, 2019 on Codechef.
2. Second Round: Onsite round will be held at The LNM Institute of Information Technology, Jaipur. More details will be announced later.

The Contest details of IUPC'19 are as follows:
- Contest duration will be 5 hours.
- Team with maximum of 3 members is allowed.
- Start time: 6th January 2019, 21:00 hrs IST
- End time: 7th January 2019, 02:00 hrs IST

Contest Link: Click here.

Prizes: 250 laddus to each member of the top 3 teams.
Cut off score for the onsite round would be declared after the contest.
For prizes and to be eligible to take part in onsite round please register yourself here.
Prizes for the onsite round will be released soon.

Problem Setter: alcatraz24, coderbond007, pa.n.ik, Shutterbug, garvitb12, Priyam2k, aditya10, titan_12 and Me.

For further details, feel free to contact us at [email protected] or visit our website..

Good luck and have fun.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by xodiac (previous revision, new revision, compare).

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

Auto comment: topic has been updated by xodiac (previous revision, new revision, compare).

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

Auto comment: topic has been updated by xodiac (previous revision, new revision, compare).

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

Great event! Surely to participate!

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

Great expectations from the event, last year's problem set was great.

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

plinth2k19

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

Can we participate in teams of 2?

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

    Yes. A team can have upto 3 members.

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

Clashes with January Easy' 19 on HackerEarth.

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

How do you solve Difference of Strings?

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

    Editorial of the contest would be released shortly on the CodeChef blog.

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

    We'll solve the problem character wise. Let dp[i][j][k] denote the number of strings up till the ith string, whose kth character is less than equal to j. This is all precomp. The size of the dp array will be hence (number of strings*total alphabets*max length of string). Now we answer each query character wise, by using the concept of prefix sum. Answering each query is O(length of string), hence fits the TL.

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

      Won't each query take 400 * 26 instructions in the worst case and since there are 105 queries, won't 8 * 108 just exceed TL?

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

        No, we iterate over the given string, and find the contribution of that character. Let the character be qs[k]. The ans will be summation abs(qs[k] — s[i][k]) over all i and k. We break the modulo into positive and negative cases, and calculate the contributions. 1e5 queries and O(400) per query makes it 4e7. It's implementation is pretty easy, you can check out my code here. My submission

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

        A lot of submissions have gotten away with this. If this was the intended solution, the time limit or constraints should have been more lenient.
        If it was not, I don't think it's a good problem where a factor of 26 decides AC vs TLE. It's hard to ensure that only the intended complexity passes, some slow solutions will almost surely slip through.

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

          May be they should have increased constraints. But input size must be kept in mind. Also factor of 26 is a lot. If you think factor of 26 is less, then as per you n = 1e5 and n^2 solution not passing is also bad.

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

            No, I do not think that because 1e5 is large factor and suboptimal solutions can be easily prevented from passing.

            Consider, for example, that the tester writes a decent q*400*26 solution like this. Since it takes, 1.12 sec, he sets TL to 1 sec (instead of 2 sec here). But then this code barely passes at 0.99 sec. Maybe TL should be tighter? But the author of this code has the bright idea of using #pragma GCC optimize and his code runs in 0.53 sec! How would you, as a setter, ensure that these solutions do not pass?

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

              Yeah I agree with you constraints were poor. From your previous comment I felt that you were saying that factor of 26 between AC and suboptimal is bad. I just wanted to oppose that statement.

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

How to solve last question. It is interesting.

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

    Your 2nd solution was correct, there was some issue in the TC,after solutions were rejudged you got an AC.

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

      We just tried to prune the brute Force solution. I think it can be made TLE easily. What was your approach??

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

When will the editorials be published?

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

For IUPC123 a lot of solutions do not work with this test case.

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

Can anyone briefly explain the solution for SPDT? Thanks

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

    Do knapsack dp with states as summation of ai , position, num of items left. Store max sum of bi possible.

    → Reply