catalystgma's blog

By catalystgma, history, 9 months ago, In English

Hello,

I wanted to ask if anybody knows about a subquadratic time complexity algorithm for figuring out the longest square substring of a string $$$s$$$. (i.e. $$$tt = ?$$$ s.t $$$\exists \, u, v$$$ s.t $$$s = uttv$$$, $$$|t|$$$ is maximized)

For example, if:

  • s = mississippi, tt = ssissi or tt = ississ.

  • s = aaaaa, tt = aaaa.

  • s = bababooey, tt = baba.

  • s = foopoopoofoo, tt = poopoo.

The related problem is much better documented (Longest Square Subsequence).

Sorry if the answer is trivial/known. Thank you for your help.

Full text and comments »

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

By catalystgma, history, 4 years ago, In English

Hi!

I tried coding Rectangle Cutting: Source Code with optimal complexity (O(n^3) with no recursion).

Submitted with the PyPy3 compiler, not Python3, yet still I got TLE on one case: 499 500(here)

I think that there is nothing to improve! It's not like in knapsack where modifying the order of the fors (range(10**2)/range(10**6) vs range(10**6)/range(10**2)) helps a lot.

Yet there are people who got AC with Python — I could see them in the statistics table.

Please help me out! I've run into this problem before and don't know what to do. Thank you!

Full text and comments »

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

By catalystgma, history, 4 years ago, In English

Last Sunday I was close to 1900, so I participated in the educational round. The problems were ok for me, but I made a stupid mistake on C (did brute force for intervals lower than some amount) and got FST (felt dizzy? Idk).

My rating prediction went from +19 to -50.

Today I said “ok, maybe I was nervous, I should participate”. Did awfully, -50, went through a lot of WAs to get AC on A/B/C. D was very awkward for me. My solutions look like spaghetti.

I suck on greedy/constructive problems and combining both results in a disaster. I will take a 2 month break, but I need to know what I have to do in order to improve.

Some DIV2s are great for me, while others make me question myself.

1) Should I solve greedy/constructive/math from here? Did some, not all https://codeforces.com/blog/entry/54526#comment-385354

2) Should I finish the 1800-1899 A2OJ ladder? Did almost half of it, learnt many things, but they were mainly related to DP/DS/Trees/Graphs, things I am relatively ok on (I don’t even have the rating for it now LOL)

3) A lot of virtual contests?

4) Do virtual contests/participate only in Educational rounds, because they have the same writers, so the topics will be generally the same?

5) ???

TY

Full text and comments »

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

By catalystgma, history, 4 years ago, In English

Hi,

I am trying to submit a solution for this problem. However, the judge flags my solution as giving WA on the example: image.

The outputs seem to be identical.

The filnames are correct (I copied them from the site).

What should be the problem?

Thanks!

Full text and comments »

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

By catalystgma, 4 years ago, In English

Hi,

I am facing a weird issue when trying to solve a problem, and I have replicated it here: http://cpp.sh/46vyc. I have a map (map<long long, bool>) and I try to iterate through pairs of consecutive indices from it. I print the pair after adding 1 to the first value, and subtracting 1 from the second value.

The output I get looks like:

bruh 3 2

bruh 4 4

....

However, when I uncomment the two lines at the end: http://cpp.sh/3auk3, which do not modify the contents of the map:

while (hh[itv.first] == 1) itv.first++;

while (hh[itv.second] == 1) itv.second--;

The output is now:

bruh 3 2

bruh 4 3

....

Why did the second line change from "4 4" to "4 3"? After all, I didn't modify the contents of the map, and I haven't altered the iterators. I'm not well informed about STL, so please help me.

Thanks!

Full text and comments »

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

By catalystgma, history, 5 years ago, In English

Hi,

I am trying to solve problem https://codeforces.com/contest/372/problem/A .

This is my sourcecode: http://cpp.sh/3rqwk. My codeforces submission is here: https://codeforces.com/contest/372/submission/55705312.

My code runs on my computer and cpp.sh on the two examples successfully but gets "Runtime Error" with a huge descrpition on the site. I know how volatile the are multiset erase operations, but I can't figure out why it won't run specifically on codeforces.

Thank you!

Full text and comments »

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

By catalystgma, history, 5 years ago, In English

Hi,

I tried to solve problem G from the 65th educational round: http://codeforces.com/contest/1167/problem/G

However, I get WA on test 1 because the difference between my answer and the expected one is 10^-7, instead of 10^-9: http://codeforces.com/contest/1167/submission/54524130

On my PC (ubuntu) the answer I get is 1.570796326796 with an error of -4.0001336*10^-12, which should pass the test.

What causes the difference and how can I solve it?

Thanks!

Full text and comments »

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