Zzyzx's blog

By Zzyzx, history, 4 years ago, In English,

The other day, I was curious about this thing and couldn't find a similar older question so.. decided to post this.

I do not know much beyond the basic algorithms 101 knowledge. Probably the only stuff I know outside of that is Heavy-Light decomposition and Persistent Segment tree. My favorite problems are those which are hard but solvable with just the basic 101 knowledge.

I am curious if there are grandmasters who have the same level of knowledge that I do and not more. While knowing more algorithms/data structures may surely help, it's interesting for me to see high rated performers who got there with just the basic algorithms 101 knowledge.

Thanks!

Read more »

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

By Zzyzx, 4 years ago, In English,

Hello,

I want to discuss about a possible modification to how showing tags for problems is handled.

Right now, if you haven't solved a problem yet, you can save yourself from the spoiler tags by making changes to your Settings.

What I want to suggest is — Why not make an option to disable tags for previously solved problems as well? Many a time, I tend to forget that I have done a particular problem in the past and enjoy looking at it from a fresh perspective but now that I have already got it accepted way back in the past, the spoiler tags show up and ruin my fun.

I'm not sure if I'm the only one finding this to be an issue which is why I ask you, the community, your opinion.

EDIT: BTW, I am totally fine with the submission history shown on the right hand side for a problem. That is enough in my opinion and there is no need to show problem tags as well.

Read more »

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

By Zzyzx, 5 years ago, In English,

I tried to submit a solution about 9 hours back. Went to sleep and then woke up hoping to see the result but still In queue ?

Why is this happening?

UPD: My submission is now judged.

Read more »

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

By Zzyzx, 5 years ago, In English,

Just recently I was trying to solve a problem but repeatedly encountered TLE verdict. This was while I was using Java 7.

Just thought I'd give it a shot and submitted the ditto same code but in Java 8. Works like a charm.

Java 7 submission Java 8 submission

And it's not some minor difference. There's a running time difference of > 2s, with Java 8 being the faster one.

I'm really curious as to why this happens. Yes, I know some kind of optimization is happening but what kind? A 2s difference is a LOT so it is non-trivial. Somebody explain?

Read more »

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

By Zzyzx, 5 years ago, In English,

Spoiler Alert: This is regarding problem D of the latest Codeforces round (242).

Link to problem statement: http://codeforces.com/contest/424/problem/D

I have two solutions, Let's call them sol-1 and sol-2

Link to sol-1: http://codeforces.com/contest/424/submission/6472455

Link to sol-2: http://codeforces.com/contest/424/submission/6472637

In sol-1 I use a struct node

struct node {
  int tot, col;
  bool operator <(const node &rhs) const {
    return tot < rhs.tot;
  }
};

In sol-2 I use std::pair <int, int> with the necessary changes to the remaining part of the code.

In sol-1 I get TLE on test case 17.

But In sol-2 I get WA on test case 3.

How is that possible?! Can someone please help me out?

UPD: Found my mistake. Thank you so much igorjan94 and andreyv

Read more »

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

By Zzyzx, 5 years ago, In English,

Hello World!

Recently, I've found a deep interest in problems involving queries on Trees (Have you tried the ones on the monthly Codechef Long Contests? They are too good!) I want to practice more of them. Since this doesn't fall into a proper category per say, I wanted to ask if anybody can give me good links to similar problems for practice and resources if possible.

Here are a few examples of problems in recent contests that I found to be very interesting.

http://www.codechef.com/NOV13/problems/GERALD2 http://www.codechef.com/MARCH14/problems/GERALD07 http://www.codechef.com/APRIL14/problems/FBCHEF

Do you know where I can find more of such problems? Thanks and have a great day!

Read more »

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

By Zzyzx, 5 years ago, In English,

Here is the link to the problem: http://codeforces.com/contest/401/problem/D

So I was trying the same DP approach as most people did, but with a slight change in the state.

What most people used as their DP state: < remainder, mask_of_18_bits >

where 'mask_of_18_bits' is used to denote whether i-th digit in number 'n' is used or not.

What I used as DP state: < remainder, zeroes_left, mask_of_18_digits >

Please note that here the mask is entirely different.

where 'zeroes_left' = number of 0s left in the number 'n' to be used.

and 'mask_of_18_digits' is defined in this way 'aabbccddeeffgghhii'

aa = number of 9s left in 'n' to be used,

bb = number of 8s left in 'n' to be used,

....

....

ii = number of 1s left in 'n' to be used

Here is the link to my submission: http://codeforces.com/contest/401/submission/5990314

but with my approach, I used std::map and that gives TLE at test case 80.

Can someone please suggest a workaround using the same idea? I want to be able to define a state in terms of counts of the digits 0-9.

Read more »

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

By Zzyzx, 6 years ago, In English,

I've been trying to understand where my code for Problem B of the round 203 is eating up so much memory. Still haven't found it.

http://codeforces.com/contest/350/submission/4633434

Would be great if anyone could help me in finding it.

Thanks in advance!

Read more »

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

By Zzyzx, 6 years ago, In English,

I just recently came across the GregorianCalendar class in Java. http://docs.oracle.com/javase/7/docs/api/java/util/GregorianCalendar.html

I tried to see if it works well by using it for this practice problem -> http://codeforces.com/contest/304/problem/B

After writing the code, I tested the two given sample cases on my computer and it gives the right output. Nice! Ctrl+A -> Ctrl+C -> Ctrl+V -> Submit! But to my utter dismay, "Wrong Answer on pretest 1". I am dumbfounded and have no idea why this is happening.

Here are my (almost identical) submissions: http://codeforces.com/contest/304/submission/4106624 -> WA on pretest 1 (Why!?) http://codeforces.com/contest/304/submission/4106538 -> WA on pretest 2 (Why!?) http://codeforces.com/contest/304/submission/4107237 -> Accepted (How is this different!?)

Can anybody explain why this is so?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Zzyzx, 6 years ago, In English,

Hello,

Just today I took part in a virtual contest and I came across a question in which I had to use the Java equivalent of C++'s lower_bound() which searches in a given range in a sorted array (of integers, say),for the first element which is not less than a given value.

For example, suppose we have array A[] = { 1, 2, 3, 5, 6 }. Now in C++, lower_bound(A, A+5, 4) returns the index of 5 because it is the first element in the given range( here the entire array ) which is not less than the given value ( which is 4).

If there is a Java equivalent of the above function that can be used in arrays, what is it? The last thing I want to do is hard code this function every time I need to use it.

Thanks in advance for any pointers!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Zzyzx, 6 years ago, In English,

Does anyone know how to see the test case on which my submission(or any others') got hacked? I haven't found a way yet.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it