sigma_g's blog

By sigma_g, history, 12 months ago, In English

Hi, I was trying to solve 702F — T-Shirts. These are four interesting submissions:

  1. AC — both <=
  2. AC — both <
  3. TLE — split < and insert <=
  4. TLE — split <= and insert <

Use the "Compare" tool on CF to see the diff between these submissions and notice for yourself that the changes are only in the sign of inequality of split_by_val and insert_by_val! In fact, the AC is in <500ms whereas TLE is on 4000ms, quite significant difference!

I do not understand why the signs of inequality actually matter. Here are my thoughts:

  1. Splitting by value and insertion by value should be able to operate independent of each other. The only prerequisite for both of them is that the treap should be BST ordered, which it always is. Therefore, the correctness of split should not depend on whether insert uses < or <= (and vice-versa).
  2. The only reason it may TLE is because of unbalancedness in the treap. But for the purpose of balancing we are using a random priority which should rebalance the treap everytime we insert by value.

So, either this an actual theoretical issue in treaps that I have not seen mentioned anywhere before (unlikely), or I have made another error in implementation due to which this issue shows up (likely) [Although I have cross checked my implementation with my friend's] Regardless, I don't understand why it TLEs!

Please help me understand the issue, thanks!

Read more »

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

By sigma_g, history, 15 months ago, In English

Hello all!

We are proud to invite you to CodeCraft-21, which takes place on Mar/29/2021 17:35 (Moscow time). It is rated for all Div2 participants (rating under 2100).

This contest comes under Threads'21, as a part of our annual techno-cultural fest Felicity, IIIT Hyderabad. We have special prizes for Indian participants!

You will be given six problems to solve in a duration of two hours.

We have tried our best to keep clean statements, useful samples with good explanations, and strong pretests! We have written step-wise editorials, and will also release video editorials!

We would like to thank these amazing people for helping make the contest happen:

There will be an interactive problem! You are recommended to read the corresponding guide.

We hope you enjoy the contest as much as we did preparing it! Good luck!

Update: The scoring distribution is 500/1000/1750/2500/2500/3000.

Update: Editorial is up! Video editorials available on our YouTube channel.

We are sorry for the sudden increase in difficulty from C to D. Nonetheless we hope you enjoyed the problems! :)

PRIZES: The following twenty lucky participants receive a tshirt:

  • top 10 Indian participants
  • random 10 from top 100 (ranks 11-100) Indian participants

These ranks are determined from the combined unofficial ranklist. We are coordinating with the CF team for the tshirt design, and we'll update the blog post when it is finalized. We also have INR 7K worth prizes exclusively for IIIT-Hyderabad students!

Read more »

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

By sigma_g, history, 16 months ago, In English

Tired of writing AC solutions? We've got you covered! This contest turns the usual format on its head. You'll be given problems and their buggy code submissions. Your job will be to figure out a test case where the buggy solution fails.

We are proud to invite you to DeCode 2021, as a part of Threads, Felicity IIIT Hyderabad! We have prizes for top three GLOBAL as well as top three INDIAN participants.

Date and Time: March 1st, 2100-2300 IST
Contest Link: CodeChef DGTC2021
Registration for prizes: Feliciy website (during registration, enter team name as your codechef username)

You will have eight problems and two hours to solve them. The problems are a good mix for all difficulty levels, from grandmasters to pupil. We have some hard problems, and some very easy too, and everything in between.

The rules and prizes have been announced on the contest page.

There's a good mix of logically enthralling bugs, and bugs that make you go "Dude just how? :O", so you'll have tons of entertainment throughout the contest.

Thanks to the setters: ltc.groverkss, amul_agrawal, kjain1810, fangahawk, akcube, and myself for setting amazing problems. And thanks to the testers: madlad, aditya.verma, ninja_28, akshat_goyal, Zshan and oreos, for debugging our contest in beta stage (inception?!).

We'll post an editorial after the contest is over. We hope you'll enjoy it!

Read more »

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

By sigma_g, 20 months ago, In English

We the Programming Club at IIIT Hyderabad (along with E-Cell IIIT-H) are proud to present to you an approximation-style coding contest Kaizen!

Date and Time: October 28, Wednesday 2100-2300 IST

Get ready with your team (of upto 2) for prizes upto 15K INR! There's prizes for random top 50 and random top 100 as well! All prizes are global, so we would recommend non-Indian users to register as well!

The contest is aimed at beginners and advanced participants. I am sure that several masters will also find it interesting.

The tests are designed in a way that there exist multiple approaches, which you can try and achieve high scores. Detailed editorials will be released after the contest, so even if you don't make it to the top, you'll learn new techniques from the contest.

I would like to thank ninja_28, AnimeshSinha1309, Arpanet, nikhil_c, shash42, yoogottamk and myself for contributing to the problem statement. And special thanks to night_fury208, dixitgarg, akshat_goyal, Horcrux1729, kunalvaswani123 and matcoder for testing the initial draft of the problemset and providing a lot of helpful feedback on it.

We hope you have fun!

Clarification: it's not rated on CodeChef.

Read more »

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

By sigma_g, 2 years ago, In English

Tired of ACing problems? Bored of seeing green Accepted all over your submissions page? Want something more adventurous?

What if we gave you the complete solution, and challenged you to then get an AC? Confused? We are proud to invite you to DeCode 2020, as a part of Threads, Felicity IIIT Hyderabad! The contest will be held on [contest_time:268401]. We will have prizes for top three Indian participants.

You'll be given problems and their buggy solutions. Your job will be to figure out on what test cases the buggy solution fails, and also fix the buggy solution itself. The solutions are exclusively written in C++.

You will have eight problems and two hours to solve them. The problems are a good mix for participants from international masters to pupil, but of course, we welcome everyone to participate!

Registration link. Please register as a participant. The rules, scoring distribution, etc. have been announced on the group blog, please check it out!

Thanks to the setters: night_fury208, AnimeshSinha1309, madlad, Arpanet, firebolt, pragunsaxena, and me, sigma_g and the testers: dixitgarg, ninja_28, akshat_goyal, Horcrux1729, and b00merang. Special thanks to MikeMirzayanov for the wonderful Codeforces and Polygon systems for making this contest possible!

We'll post an editorial in this thread after the contest is over. We hope you'll enjoy it!

Read more »

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

By sigma_g, history, 3 years ago, In English

Hi all, I have made a dark theme for Codeforces. Solving problems on Codeforces at night becomes very tough due to the completely white theme. Even in the morning, staring at the white screen for long does not help people who develop eye strain quickly, like I do. Hence, I made this dark theme.

Quick access installation link

I was not content with simply using a color inverter for the website, as there are many subtle elements, especially the rating colors, which would lose their essence when inverted.

It will surely take your eyes some time to adapt to this new format of colors. However, I would really suggest you to use it for at least a day or two.

I have been using this daily for over two months now, so it's safe to assume it's very well battle-tested :) (except the problem setters page though, I am not really sure how that looks) I have added dark theme formatting for the source code viewer and submission editor as well!

Currently it's a userscript. Please find installation instructions on the GitHub repo. If enough people start using this, I might package this into a Chrome extension.

I would really welcome any constructive feedback that you have regarding it :)

Thank you!


Read more »

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

By sigma_g, history, 3 years ago, In English


My solution:
Editorial solution:

Both of the codes look exactly the same, and have the same logic. Yet mine is TLE. Could anyone please help me understand why that is the case?

Read more »

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