teja349's blog

Invitation to CodeChef September Lunchtime 2018!
By teja349, history, 6 years ago, In English

Hello CodeForces Community!

We would like to invite you to our next monthly contest and we’re sure you’ll enjoy — the September Lunchtime 2018 sponsored by Sharechat! Get ready for a three-hour test of your coding brains and pit yourself against the best. And there’s more! We have exciting full-time job opportunities by ShareChat for professionals across the globe. More details can be found on the September Lunchtime contest page.

Joining me this time on the problem setting panel are:

  • Problem Setter: kingofnumbers (Hasan Jaddouh)

  • Problem Tester: teja349 (Teja Vardhan Reddy)

  • Editorialist: taran_1407 (Taranpreet Singh)

  • Statement Verifier: Xellos (Jakub Safin)

  • Russian Translator: Mediocrity (Fedor Korobeinikov)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Hindi Translator: Srijan Dubey

  • Bengali Translator: solaimanope (Mohammad Solaiman)

  • Vietnamese Translator: VNOI Team

Contest Details:

Time: 29th September 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

Good Luck! Hope to see you at the contest!

I am thinking about hosting a stream soon after the contest to discuss the tasks from the contest.
What is your opinion on it?
Incase there is good response from community, I will host a stream discussing problems from the contest.

Stream Details:

I will be starting the stream at 10:40 pm IST ( 10 minutes after the contest) at https://www.twitch.tv/teja349 . I will try to take questions after solving each problem. I see there is a lag close to 1 minute on twitch. Is there a way to get rid of it or maybe my system resources cannot process,

Youtube link: https://www.youtube.com/watch?v=GJfD2PEY7pA .

Comments and suggestions are most welcomed!!

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

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

I think streaming is a very good idea.

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

    Good opportunity to prove that you are not a robot

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

Incase you feel stream will be helpful. Upvote this comment.so as to get some quantitative idea.

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

    Will streamed video be available after live streaming?

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

I just hope the Codechef Server doesn't go down during the contest.

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

+1 for stream. :)

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

Nice problems.

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

Although not mandatory, but an explanation of sample should be given as it really helps.

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

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

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

How to solve "Match the Streams"?

I was using sqrt-decomposition with map to store frequencies of element, but it gave TLE for second subtask.

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

    You can map integers from sequence b before queries, all other values can be same as 0.

    P.S. I was doing this task for 2+ hours and still I didn't get AC :D

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

      Yeah I did same and then sqrt decomposition..Total complexity was , but it gave TLE :(

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

        Nope, my complexity is . You can have next value for each block cnt[i][j] ( amount of numbers i in block j).

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

          allllekssssa sorry if that's too trivial, but isn't i can be upto 109, which you can't store in cnt[i][j], and I don't think coordinate compression will help here because there's an incoming stream of c's...

          can you please elaborate a bit more on your approach or post your code.

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

            The main trick is mapping only elements from sequence B, all other values are not important for result and can be equal to 0. Now you will have at most 105 different mapped elements, and each will be in interval [0, 105].

            How will you calculate this array cnt[i][j], go over sequence B and when you come to element Bi, then ++.

            Update queries can be easily handled, for whole block i current answer is same as cnt[c][i], for edge blocks just go over all important position and change answer.

            You can see my code down in some of the next comments.

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

    My solution AC-ed with BlockSize=750.

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

      why? Isn't block size of 320 sufficient?

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

        No, my solution is O(Nlog(X)/X+X) per query. For N=100000, optimal X would be ~750.

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

          can you provide some hints for your solution

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

    You can make it in (or even if you use hash map):

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

I have 10-15s delay. Connecting through ethernet helped. It was worse via wi-fi. And don't use big high FPS, I guess.

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

The problems were nice, but the testcases were really weak. I got AC on 2 questions with a randomised approach.

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

    COINPART problem got accepted with randomised approach, but which is the other one?

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

You must change something on site, it is too slow for normal contest!

I am usual participant of Cook Offs/Lunchtimes, but this is too much for my nerves, and I seriously think to stop it after this bad experiences with site.

Tasks were interesting!

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

    yes, even after the contest end, some of the content is too slow to open.

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

Biased Juded Problem was really nice. I wish that problem was on codeforces, hundreds of hacks would have been there including mine (:( ) on not realizing that the minimum time limit was supposed to be equal to 1.

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

I got TLE on fourth task with time>3sec. I submited the same code after contest and I got AC for 1.15 sec. I really think problem is not in my submission and solution.

If someone would check my last submission for MATCH2, I would be really thankful.

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

I can't find it in problem statement of problem Biased Judgement, so I will ask it here. Can we test problem on an empty subset of tests?

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

    yes, it's allowed but we decided remove test-case where choosing empty subset is the only correct output because we noticed that wasn't clear from statement and we couldn't change the statement because it was already late and statement was already translated to many languages.

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

Can you tell why my code is giving TLE. for match2 According to me complexity will be (N+Q)log^2(n) https://www.codechef.com/viewsolution/20389388

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

Test cases of problem BJUDGE were weak particularly in Subtask #2 and that is the reason a lot of people managed to score 70 with incorrect code.

Please update the test cases in at least the practice version of the problem. teja349

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

The editorials for first four problems are ready and will be available once admin moves them to public. Editorials for last two would be available within one day.

Hope you all had a great contest.

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

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

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

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

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

I am getting runtime error in Match2. Can anyone help me in finding error? Solution link

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

Hi, teja349. I am doing the problem MATCH2 with sqrt decomposition. I have two code that is identical except for one line, but they did not behave as expected. Would you like to help me check them? I think it might be related to the compiler on the Codechef.

In this submission 1, I asserted "br < 349" on the 35th line and got passed. However, in this submission 2, I asserted "br < 350" on the same line but got runtime error. I felt somehow lost. Would you like to do a favor to help me figure it out?

Thanks in advance!

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

    Any other's help will also be appreciated :)

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

      Undefined behaviour or they changed tests, I guess.

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

https://www.codechef.com/viewsolution/20373923 and https://www.codechef.com/viewsolution/20400424

What's the difference? One got TLE 1s while the other one got AC 0.17s. Thanks for making me spend extra time to write a solution without map.

Edit:

https://www.codechef.com/viewsolution/20377308 and https://www.codechef.com/viewsolution/20377751

What's the difference? One got CE while the other one was able to compile.

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

Can't the problem "Biased Judgement" have multiple solutions? e.g. For the sample testcase 1, the time limit could have been any integer greater than 7 seconds.

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

    Yes it could have multiple solutions and you were allowed to print any of them. Just make sure that your solution will allow all submissions i with d[i] = 1 to pass and j with d[j] = 0 must fail

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

      If so, it should have been mentioned in the problem statement, wasted a lot of time trying to figure out a unique solution :/

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

How to solve Coin Partition?

→ Reply