taran_1407's blog

By taran_1407, history, 2 years ago, In English

Hey all,

Codechef plan to have an informal series of live stream with the panelists of April Long Challenge 2020 discussing the problems from the contest.

The details regarding the first session are as follows:

If there are any specific queries that you have from these problems, please post them below, and I will try to answer them during the session.

P.S.: Keep watching this space for future sessions by fmota, 300iq and pieguy on the remaining problems!

Read more »

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

By taran_1407, history, 3 years ago, In English

Hi guys I was looking for someone who can partner me in some serious regular practice for improvement. PM me if you want to practice with me. I am looking for a guy at least above 2000, preferably yellow (or lower red).


[Edit] I have found a partner. Thanks, Codeforces :)

[Edit] You can still PM me if you want to discuss any interesting problem. :)

Read more »

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

By taran_1407, history, 3 years ago, In English

Hello Folks

Today, I'm going to write my first blog on Interactive problems and all you need to know about them.

First of all, Let us understand what are interactive problems.

Interactive problem is nothing but a problem where your solution should interact (send output to and receive input from) with a grader problem (also called problem judge). If your solution makes the queries to find out the answer or make the queries in a specific way as required in the problem statement, you get an accepted verdict. Otherwise, you get Wrong Answer or other verdicts. Usually, we have an upper limit on the number of queries too. Making queries in excess lead to the Wrong Answer.

Now, the Important thing about Interactive problems is flushing output.

In most languages, printing output to console/output screen is an expensive operation and thus, languages keep collecting the output (called buffered output), printing all the collected output in one go at the end of the program to improve efficiency. But this may cause us trouble with Interactive problems as we want our output to be sent to output console before terminating the program.

Fortunately, we have tools for this, called manually flushing output. Flushing output means, that you ask your program to print all buffered output and clear the buffer. This way, the output is sent to console before termination of the program, and only then we can receive input from the grader program since it returns the next input only after receiving previous output.

Flushing in c++ can be done using fflush(stdout) and in java, System.out.flush() or out.flush() where out represent our outputstream.

An example interactive problem.

I shall take probably the most popular interactive problem to explain how things work with interactive problems.

We have an array A of length N hidden from us, which is sorted in ascending order. We are given only N and a value Val. We are allowed to make logN queries of the form ? x y.

The answer of query shall be 0 if A[x] =  = y, -1 if A[x] < y and 1 if A[x] > y.

In the end, we are required to print output by printing ! x where x is the index of position such that A[x] = val. If no position contain value val, print  - 1.

The simple solution is to iterate over all position, make a query and if any position matches, print that position. It shall take N queries in the worst case which violate the query limit.

Let us utilize the ascending order of A to use binary search.

We have range [l, r] initially [0, N - 1] which may contain value Val. Let mid = (l + r) / 2 and make a query ? mid val. If we get 0, we have found the required position. Otherwise, if the answer to the query is -1, we are sure that no value in the range [mid, r] contain answer since all values in this range are greater than Val. So, we change the right end to (mid-1). Similar way, we change left end to (mid+1) if the answer to the query is 1. We are bound to find the required position in log2N queries due to dividing search space by half at each step.

Making query/Printing output

In interactive problems, we make query/print output in two steps.

Print the output in the normal manner (like non-interactive problems.) Using cout or scanf or any other method in c++ or out.println() in Java or similar ways in other languages.

Flush the output using following commands in various languages.

fflush(stdout) in C++.
System.out.flush() in Java.
stdout.flush() in Python.
flush(output) in Pascal.
See the documentation for other languages.

Important point Remember to close the output stream after the program completes. The reason is, that your program may keep waiting for grader while grader has completed its execution. It may lead to an unexpected verdict.

So this concludes our blog for interactive problems. I shall try to write more blogs soon. Let me know of any interesting topic you want the blog for. Discuss in comments.

For trying interactive problems, Codechef December Long Challenge 2018 has a lot of interactive problems. A recent interactive problem on codeforces can be found here.

Until then, see you all!

Edit: Just found MikeMirzayanov has already published a blog on same, which you may refer here.

Read more »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By taran_1407, 4 years ago, In English

Hello Codeforces community

I am delighted to announce ICO preparatory series contest #2 to be held on 26th August, 2018.

Contest Banner

The Aim of this contest is to introduce Competitive Programming at School student level as well as training for IOI aspirants. We hope to keep the problems sufficient to keep you engaged for four hours. The editorials would be detailed enough for beginners to understand the concepts.

As an incentive, The top 3 Indian school students would be getting 250 laddus each.

The contest Panel includes

Problem Setters: vijju123 and taran_1407
Problem Testers: vijju123 and taran_1407
Editorials by this taran_1407

The round is unrated for both divisions, so, join the fun without the stress of rating and feel free to attack any problem. :D

Access this Contest here.
Contest Date: 26th August, 2018, 7:00PM IST (19:00 IST)
Contest Duration: 4 hours

Hoping to see you all on 26th.

PS: Why down voting?? Please drop a comment if you didn't like it and why, so that we can improve. Would be glad to hear you. Thanks

UPDATE: Owing to the overlapping timings of this round with Codeforces Round #506 (Div. 3), we have decided to conduct this round on sunday, 26th August. Inconvenience is regretted. Good Luck for CF Div 3 round too.

Read more »

  • Vote: I like it
  • -18
  • Vote: I do not like it