HusseinFarhat's blog

By HusseinFarhat, history, 13 months ago, In English

I came up with 2 problems, an "easy" version and a hard version

The easier version is:

If you have an array A composed of n integers, compute the array B under O(n^2), where $$$B_{i} = \displaystyle\sum_{j=1 \atop j \neq i}^{n} \frac{1}{(A_{i} - A_{j})^2} (where j \neq i)$$$. It seems like this problem should be solved by getting a common denominator, but the rest gets very confusing. It becomes: $$$\frac{\sum_{k = 1 \atop k \neq i}^{n} \Pi_{j = 1 \atop j \neq k j \neq i}^{n} (A_{i} - A_{j})^2}{\prod_{j = 1 \atop j \neq i}^{n} (A_{i} - A_{j})^2}$$$

The harder (or maybe even impossible) version is:

If you have an array A composed of n 3d vectors, and an array M composed of n real numbers, compute the array F of n 3d vectors, where each element is the total newtonian gravity force. $$$A_{i}$$$ is the current position of the particle i, and $$$M_{i}$$$ is the mass of the particle i. You can brute force this by just iterating through all possible pairs, then calculating this. Is it possible to do it under O(n^2)?

Note that these two problems, or the second one, may be impossible to solve. If that's the case, there might be a way to approximate it

Full text and comments »

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

By HusseinFarhat, history, 15 months ago, In English

There are multiple blogs showing that some users get away with cheating by obfuscating their code, so codeforces really needs to check if a submission is obfuscated. It looks like the cheaters copy a solution and they put each line/token in a define, with a lot of junk in between. This is currently being handled on a case by case basis, which is a problem

/*Example*/

#include <iostream>
#define awhHRUTH1x using
#define b589AHWUin namespace
#define iuhA2781AB std;
#define v1895Krnba int
#define bATT68125F main(
#define bba5891AW4 ){
#define JKT15jyT51 cout<<
#define abb151A5h1 "HelloWorld\n";
#define Uikta5UUNW return
#define bbbqrgq214 0;
#define btpIOUHBWW }

awhHRUTH1x b589AHWUin iuhA2781AB
/*#define aiw uahiuwhha ruahwihaiuwhviunpawrry1pqrawu;*/
/*int gcd(int a,int b) return a+b;*/
/*im not sure if this compiles*/
v1895Krnba bATT68125F bba5891AW4 JKT15jyT51 abb151A5h1 Uikta5UUNW bbbqrgq214 btpIOUHBWW

Right now, as most of these solutions are accepted and not skipped, it seems like there's not a proper obfuscation check, so we need MikeMirzayanov to make a good one. For example, checking the code after it gets preprocessed (remove defines and comments) so that the junk won't circumvent the checks. Or counting the amount of random strings in the code (like a551hawibBY). These ideas can be made into a deobfuscator that preprocesses the code before the actual cheating check

Full text and comments »

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