text:
a cos x + b sinx

• Jul 19th 2012, 04:11 PM
Furyan
a cos x + b sinx
Hello

I would appreciate some help with the following question, which is, prove that:

$\cos\theta - \sin\theta = -\sqrt{2}\sin(\theta - 45^o)$

If I do it like this:

$\cos\theta - \sin\theta \equiv R\sin(\theta + \alpha)$

$\equiv R(\sin\theta\cos\alpha + \cos\theta\sin\alpha)$

$1 = R\sin\alpha$

$-1 = R\cos\alpha$

$R = \sqrt{2}$

$\alpha = arctan (-1) = - 45^o$

I get:

$\sqrt{2}\sin(\theta - 45^o)$

I thought of doing it like this:

$\cos\theta - \sin\theta \equiv\sin(\theta - \alpha)$

$\equiv R(\sin\theta\cos\alpha - \cos\theta\sin\alpha)$

$\equiv -R(-\sin\theta\cos\alpha +\cos\theta\sin\alpha)$

but then $(-R)^2 = R^2$

So I can't seem to do it.

I did first have to show that:

$\cos\theta - \sin\theta = \sqrt{2}\cos(\theta + 45^o)$, which I was able to do.

Any help would be very much appreciated,

Thank you
• Jul 19th 2012, 04:43 PM
emakarov
Re: a cos x + b sinx
Quote:

Originally Posted by Furyan
prove that:

$\cos\theta - \sin\theta = -\sqrt{2}\sin(\theta - 45^o)$

Rewrite the right-hand side using the formula $\sin(\theta-\alpha)=\sin\theta\cos\alpha - \cos\theta\sin\alpha$.
• Jul 19th 2012, 04:52 PM
Kmath
Re: a cos x + b sinx
Why you do not try this,

$\cos \theta -\sin \theta=\sqrt{2}(\cos \theta \frac{1}{\sqrt{2}}-\sin\theta\frac{1}{\sqrt{2}})$
$=-\sqrt{2}(\sin\theta\cos 45 -\cos\theta\sin45)=-\sqrt{2}\sin{(\theta-45)}$
• Jul 19th 2012, 05:03 PM
emakarov
Re: a cos x + b sinx
Quote:

Originally Posted by Furyan
If I do it like this:

$\cos\theta - \sin\theta \equiv R\sin(\theta + \alpha)$

$\equiv R(\sin\theta\cos\alpha + \cos\theta\sin\alpha)$

$1 = R\sin\alpha$

$-1 = R\cos\alpha$

$R = \sqrt{2}$

$\alpha = arctan (-1) = - 45^o$

I get:

$\sqrt{2}\sin(\theta - 45^o)$

The error here is that $\tan(\alpha)=-1$ does not imply that $\alpha=-45^\circ$. In this case, $\sin\alpha=1/\sqrt{2}$ and $\cos\alpha=-1/\sqrt{2}$, so $\alpha=135^\circ$. Thus,

$\cos\theta-\sin\theta=\sqrt{2}\sin(\theta+135)=\sqrt{2}\sin(1 80-\theta-135)=\sqrt{2}\sin(45-\theta)$ $=-\sqrt{2}\sin(\theta-45)$.
• Jul 19th 2012, 05:23 PM
Furyan
Re: a cos x + b sinx
Thank you both for taking the time to reply.

(There's nothing in the chapter I'm working through about either of the methods you have shown me, but I will study your posts in detail to see what I can learn from them.

Thank you very much for you efforts.)

Edit: Ah, actually there is an example showing how to determine which quadrant the angle is in. I never learnt that, I'm not sure how I got by without it. It seems pretty important, in fact, looking back it's one of the first things I should have learnt in trigonometry. (Doh)
• Jul 19th 2012, 05:42 PM
Furyan
Re: a cos x + b sinx
(Bow)Thank you,

(I will see if I can get:

$\sqrt{2}\sin(45 - \theta)$

just now seeing that $\alpha= 135$ is beyond me, but I guess I need to know that.)

Thank you very much indeed for your help. (Bow)

Edit: I think I understand now. Since $\sin\alpha > 0$ and both $\cos\alpha$ and $\tan\alpha < 0, \alpha$ is in the second quadrant, $90^o \leq \alpha \leq 180^o$. Thanks for pointing that out. I'm glad I know that now.(Happy)


text:
# saveSession -- save the actual Polyhedra session to a file

## Synopsis

• Usage:
saveSession F
• Inputs:
• F,

## Description

All convex polyhedral objects (Cone,Fan,Polyhedron) that have been assigned to a Symbol will be saved into the file F. If the package PPDivisor is loaded, then also all PolyhedralDivisors are saved into F. Also every List or Sequence containing any of the above types or lists and sequences of them in arbitrary nested depth of lists is saved.

To recover the session simply call load F. It is not necessary that Polyhedra is already loaded (if not, it will be) and also PPDivisor is loaded if it was loaded when the session had been saved.

## Ways to use saveSession :

• "saveSession(String)"

## For the programmer

The object saveSession is .

format: plain


text:
LaTeX problem sets with hidden answers

# LaTeX problem sets with hidden answers

I like being able to hide content in documents, for example including but not revealing the answers in a problem set. That makes it very easy to then produce the problem set solutions, simply by revealing the answers. I made this easier with a \hide{} command, that can be “turned off” so the answers are revealed.

This is the basic code I use for producing problem sets. The only change needed to convert a problem set into a solution set is to redefine the \showanswers variable to equal 1 rather than 0.

\documentclass{article}

% Set this =0 to hide, =1 to show

\newcommand{\hide}[1]{

#1 \vspace{\baselineskip}
\fi

\vspace{2\baselineskip} \hspace{2cm}
\fi
}

\begin{document}

\begin{enumerate}
\item This is question 1.
\hide{Here is a hidden solution.}

\item What is the answer to question 2?


text:
# If $K\cong K(X)$ then must $K$ be a field of rational functions in infinitely many variables?

If $k$ is any field, then the field $K=k(X_0,X_1,\dots)$ of rational functions in infinitely many variables satisfies $K(X)\cong K$ (by mapping $X$ to $X_0$ and $X_n$ to $X_{n+1}$). My question is, does the converse hold? That is:

Suppose $K$ is a field such that $K\cong K(X)$. Must there exist a field $k$ such that $K\cong k(X_0,X_1,\dots)$?

(If such a $k$ exists, then we can in fact take $k=K$, by splitting the variables into two infinite sets.)

Note that if we were talking about polynomial rings instead of fields of rational functions, the answer would be no: there exists an integral domain $R$ such that $R\cong R[X]$ but $R\not\cong S[X_0,X_1,\dots]$ for any ring $S$. A counterexample is given at A ring isomorphic to its finite polynomial rings but not to its infinite one. However, for that example the field of fractions of $R$ actually is a field of rational functions in infinitely many variables, so it does not give a counterexample to this question.

In any case, I suspect the answer is no and it may be possible to find a counterexample using some idea similar to the example there (some sort of "all but finitely many..." construction), but don't have any concrete idea of how to make it work.

Some other (unanswered) questions that may be related: Is there a field $F$ which is isomorphic to $F(X,Y)$ but not to $F(X)$? (also on MO), The field of fractions of the rational group algebra of a torsion free abelian group. (In particular, an answer to the former question would give a field $F$ such that $F\cong F(X,Y)$ but $F$ is not isomorphic to a field of rational functions in infinitely many variables, which is very close to this question.)

• Might it be worth asking this interesting question on MathOverflow? – Watson Jul 23 '18 at 17:56
• Sure. Given that your related question hasn't gotten an answer there I would be surprised if this one got an answer there quickly, though. Feel free to crosspost it if you want. – Eric Wofsey Jul 23 '18 at 18:10
• Do you know that the field of fractions of the rational group algebra of the Baer-Specker group is not a counterexample? Given the links in the question, I’m guessing you’ve thought about it. – Jeremy Rickard Jun 15 at 13:09
• @JeremyRickard: That's a neat idea. I don't actually recall thinking through it before (I think the constructions I was trying were all countable). – Eric Wofsey Jun 15 at 14:50
• It’s an example of something. Either it’s a counterexample for your question, or the rational group algebras of the nonisomorphic groups $\mathbb{Z}^\omega$ and $\mathbb{Z}^\omega\oplus\mathbb{Z}^{(\omega)}$ have isomorphic fields of fractions, answering my question. – Jeremy Rickard Jun 16 at 9:25


text:
# Is there a generalization of Burnside's theorem for compact Lie groups?

Recall the following theorem due to Burnside:Let $G$ be a finite group and let $V$ be its irreducible complex representation of dimension greater than 1, then the character of this representation is $0$ on some element of $G$. Is this statement still correct if $G$ is any compact Lie group? Thanks.

-
Some context for the question would be helpful. It seems to reduce to looking at the well-studied finite dimensional representations (over $\mathbb{C}$) of a connected semisimple compact Lie group. Why would an answer be interesting? There are similarities with the finite group situation, including orthogonality relations, but also some big differences. As far as I can see, the proof for finite groups doesn't readily translate to compact Lie groups. The answer could well be yes (or no), but does it have implications? –  Jim Humphreys May 28 '10 at 22:21


text:
What is the difference between --split-files and --split-3 when using fastq-dump?
2
3
Entering edit mode
5.3 years ago
elenajmichel ▴ 90

Hello,

I have been using --split-files when using fastq-dump, but I have seen a lot of posts saying to use --split-3. The manual page is not quite clear about the difference between the two commands (besides the number of files generated), so could someone tell me what the difference is between the two commands, and under what circumstances it may be better to use one over the other?

Thank you.

RNA-Seq fastq-dump paired end reads • 6.0k views
2
Entering edit mode

Also, please look there --> C: SRA to BAM - to see about --split-files option

1
Entering edit mode

Thank you! The fastq-dump split-3 output link helped a lot.

2
Entering edit mode
5.3 years ago

According to the manual It looks like split-files creates a file for every read. Meaning the output will have a lot of files.

--split-3 is for paired-end reads. So it will produce 2 fastq files only.

If your data is single-end you don't need to use these options.

1
Entering edit mode

--split-files actually behaves the same as --split-3 and produces 2 fastq files for each SRA, hence my confusion.

2
Entering edit mode

"--split-3 will output 1,2, or 3 files: 1 file means the data is not paired. 2 files means paired data with no low quality reads or reads shorter than 20bp. 3 files means paired data, but asymmetric quality or trimming. in the case of 3 file output, most people ignore <file>.fastq . this is a very old formatting option introduced for phase1 of 1000genomes. before there were many analysis or trimming utilities and SRA submissions always contained all reads from sequencer. back then nobody wanted to throw anything away. you might want to use --split-files instead. that will give only 2 files for paired-end data. or not bother with text output and access the data directly using sra ngs apis." (from Question: fastq-dump split-3 output )

1
Entering edit mode

Actually split-3 outputs 3 files:

two files for the paired and another one for single-tone. I just run split-files on my end and it did output 2 files only. I guess the difference is the single-tone output. I'm not sure though

1
Entering edit mode

1
Entering edit mode

Split-files option outputs two fastq files in teh case of paired-end reads: one file - for forward, another - for reverse reads.

1
Entering edit mode
5.3 years ago
GenoMax 104k

Explained in the inline help for fastq-dump.

\$ fastq-dump -h

--split-files                    Dump each read into separate file.Files
number
--split-3                        Legacy 3-file splitting for mate-pairs:
conditions are placed in files *_1.fastq and
*_2.fastq If only one biological read is
present it is placed in *.fastq Biological

1
Entering edit mode

Hi, as I stated in my question I don't think it is clearly explained because the explanation for --split-files makes it sound as if a separate file will be created for each read, which isn't correct as it just splits them into two files. Based on that, I don't really understand why you would use --split-3 vs --split-files to get the same result.

2
Entering edit mode

"fastq-dump" is used with Illumina data and traditionally "read" data in Illumina speak refers to Read 1 or Read 2 (not individual reads in the files, which if you think about logically would not make sense i.e. a separate file for each read).


text:
Ask Your Question

# Why setting U and V channels to 0 leads to displaying a Blue picture?

What I did:

• I read a BGR image and convert it to YUV color space.

• Then I set its U and V channels to 0

• I display the image and I see it is all blue (as if I set R and B to 0, instead)

Questions:

• Why setting U and V values to 0 leads the the G and R channels of the picture set to 0 also ?
• Why the image is displayed in blue (BGR color space) instead of YUV color space ?

Code:

import cv2
import numpy as np

img=cv2.imread('rgb_pic.png')
yuv_img=cv2.cvtColor(img,cv2.COLOR_BGR2YUV)
cv2.imwrite('yuv_pic',yuv_img)

cv2.namedWindow('YUV',cv2.WINDOW_AUTOSIZE)
cv2.imshow('YUV',yuv_img) # Displayed image is YUV, that is ok
cv2.waitKey(0)
cv2.destroyAllWindows()

im=yuv_img # Copy the YUV image to an other one
for in in range(im.shape[0]):
for j in range(im.shape[1]):
im[i,j,1]=0 # Set U to 0
im[i,j,2]=0 # Set V to 0
cv2.namedWindow('Result',cv2.WINDOW_AUTOSIZE)
cv2.imshow('Result',im) # Displayed image is totally BLUE :(
cv2.waitKey(0)
cv2.destroyAllWindows()

Results:

yuv_img displayed like this (that is ok for me):

im displayed like this (I do not understand why it is blue):

Regards, from BEGUERADJ

edit retag close merge delete

## 1 answer

Sort by » oldest newest most voted

Because imshow displays the image az a BGR image.

In fact the im variable is a WxHx3 matrix, and OpenCV doesn't know if it's RGB, HSV, YUV or something else. so it considers that it's BGR. The fact that you set to 0 the second and third channels basically erases the green and red channels. That's why your image turned blue.

To display it correctly, you have to convert it back to BGR color space:

cvtColor(im,result,COLOR_YUV2BGR);
imshow(result);

(add the cv2. before the expressions for python)

It should show correctly the grayscale image.

more

## Comments

come back to you again if I may: I did exactly what you said. By curiosity, I run print im[130,290,1] and I get a value other than 0 whereas I am supposed to get 0 since I set it to 0 previously. Why is this ?

( 2015-03-12 05:40:38 -0500 )edit

Official site

GitHub

Wiki

Documentation

## Stats

Asked: 2015-03-11 04:49:56 -0500

Seen: 964 times

Last updated: Mar 11 '15


text:
# Properties

 Label 1911.1.h.d Level $1911$ Weight $1$ Character orbit 1911.h Self dual yes Analytic conductor $0.954$ Analytic rank $0$ Dimension $4$ Projective image $D_{8}$ CM discriminant -39 Inner twists $4$

# Related objects

## Newspace parameters

 Level: $$N$$ $$=$$ $$1911 = 3 \cdot 7^{2} \cdot 13$$ Weight: $$k$$ $$=$$ $$1$$ Character orbit: $$[\chi]$$ $$=$$ 1911.h (of order $$2$$, degree $$1$$, minimal)

## Newform invariants

 Self dual: yes Analytic conductor: $$0.953713239142$$ Analytic rank: $$0$$ Dimension: $$4$$ Coefficient field: $$\Q(\zeta_{16})^+$$ Defining polynomial: $$x^{4} - 4 x^{2} + 2$$ Coefficient ring: $$\Z[a_1, a_2]$$ Coefficient ring index: $$1$$ Twist minimal: yes Projective image: $$D_{8}$$ Projective field: Galois closure of 8.2.90724673403.2

## $q$-expansion

Coefficients of the $$q$$-expansion are expressed in terms of a basis $$1,\beta_1,\beta_2,\beta_3$$ for the coefficient ring described below. We also show the integral $$q$$-expansion of the trace form.

 $$f(q)$$ $$=$$ $$q -\beta_{1} q^{2} - q^{3} + ( 1 + \beta_{2} ) q^{4} -\beta_{3} q^{5} + \beta_{1} q^{6} + ( -\beta_{1} - \beta_{3} ) q^{8} + q^{9} +O(q^{10})$$ $$q -\beta_{1} q^{2} - q^{3} + ( 1 + \beta_{2} ) q^{4} -\beta_{3} q^{5} + \beta_{1} q^{6} + ( -\beta_{1} - \beta_{3} ) q^{8} + q^{9} + \beta_{2} q^{10} + \beta_{1} q^{11} + ( -1 - \beta_{2} ) q^{12} + q^{13} + \beta_{3} q^{15} + ( 1 + \beta_{2} ) q^{16} -\beta_{1} q^{18} -\beta_{1} q^{20} + ( -2 - \beta_{2} ) q^{22} + ( \beta_{1} + \beta_{3} ) q^{24} + ( 1 - \beta_{2} ) q^{25} -\beta_{1} q^{26} - q^{27} -\beta_{2} q^{30} -\beta_{1} q^{32} -\beta_{1} q^{33} + ( 1 + \beta_{2} ) q^{36} - q^{39} + 2 q^{40} + \beta_{3} q^{41} + ( 2 \beta_{1} + \beta_{3} ) q^{44} -\beta_{3} q^{45} + \beta_{3} q^{47} + ( -1 - \beta_{2} ) q^{48} + \beta_{3} q^{50} + ( 1 + \beta_{2} ) q^{52} + \beta_{1} q^{54} -\beta_{2} q^{55} -\beta_{1} q^{59} + \beta_{1} q^{60} + q^{64} -\beta_{3} q^{65} + ( 2 + \beta_{2} ) q^{66} -\beta_{3} q^{71} + ( -\beta_{1} - \beta_{3} ) q^{72} + ( -1 + \beta_{2} ) q^{75} + \beta_{1} q^{78} -\beta_{2} q^{79} -\beta_{1} q^{80} + q^{81} -\beta_{2} q^{82} + \beta_{1} q^{83} + ( -2 - 2 \beta_{2} ) q^{88} + \beta_{1} q^{89} + \beta_{2} q^{90} -\beta_{2} q^{94} + \beta_{1} q^{96} + \beta_{1} q^{99} +O(q^{100})$$ $$\operatorname{Tr}(f)(q)$$ $$=$$ $$4 q - 4 q^{3} + 4 q^{4} + 4 q^{9} + O(q^{10})$$ $$4 q - 4 q^{3} + 4 q^{4} + 4 q^{9} - 4 q^{12} + 4 q^{13} + 4 q^{16} - 8 q^{22} + 4 q^{25} - 4 q^{27} + 4 q^{36} - 4 q^{39} + 8 q^{40} - 4 q^{48} + 4 q^{52} + 4 q^{64} + 8 q^{66} - 4 q^{75} + 4 q^{81} - 8 q^{88} + O(q^{100})$$

## Character values

We give the values of $$\chi$$ on generators for $$\left(\mathbb{Z}/1911\mathbb{Z}\right)^\times$$.

 $$n$$ $$638$$ $$1471$$ $$1522$$ $$\chi(n)$$ $$-1$$ $$-1$$ $$1$$

## Embeddings

For each embedding $$\iota_m$$ of the coefficient field, the values $$\iota_m(a_n)$$ are shown below.

For more information on an embedded modular form you can click on its label.

Label $$\iota_m(\nu)$$ $$a_{2}$$ $$a_{3}$$ $$a_{4}$$ $$a_{5}$$ $$a_{6}$$ $$a_{7}$$ $$a_{8}$$ $$a_{9}$$ $$a_{10}$$
1520.1
 1.84776 0.765367 −0.765367 −1.84776
−1.84776 −1.00000 2.41421 −0.765367 1.84776 0 −2.61313 1.00000 1.41421
1520.2 −0.765367 −1.00000 −0.414214 1.84776 0.765367 0 1.08239 1.00000 −1.41421
1520.3 0.765367 −1.00000 −0.414214 −1.84776 −0.765367 0 −1.08239 1.00000 −1.41421
1520.4 1.84776 −1.00000 2.41421 0.765367 −1.84776 0 2.61313 1.00000 1.41421
 $$n$$: e.g. 2-40 or 990-1000 Significant digits: Format: Complex embeddings Normalized embeddings Satake parameters Satake angles

## Inner twists

Char Parity Ord Mult Type
1.a even 1 1 trivial
39.d odd 2 1 CM by $$\Q(\sqrt{-39})$$
3.b odd 2 1 inner
13.b even 2 1 inner

## Twists

By twisting character orbit
Char Parity Ord Mult Type Twist Min Dim
1.a even 1 1 trivial 1911.1.h.d 4
3.b odd 2 1 inner 1911.1.h.d 4
7.b odd 2 1 1911.1.h.e yes 4
7.c even 3 2 1911.1.w.f 8
7.d odd 6 2 1911.1.w.e 8
13.b even 2 1 inner 1911.1.h.d 4
21.c even 2 1 1911.1.h.e yes 4
21.g even 6 2 1911.1.w.e 8
21.h odd 6 2 1911.1.w.f 8
39.d odd 2 1 CM 1911.1.h.d 4
91.b odd 2 1 1911.1.h.e yes 4
91.r even 6 2 1911.1.w.f 8
91.s odd 6 2 1911.1.w.e 8
273.g even 2 1 1911.1.h.e yes 4
273.w odd 6 2 1911.1.w.f 8
273.ba even 6 2 1911.1.w.e 8

By twisted newform orbit
Twist Min Dim Char Parity Ord Mult Type
1911.1.h.d 4 1.a even 1 1 trivial
1911.1.h.d 4 3.b odd 2 1 inner
1911.1.h.d 4 13.b even 2 1 inner
1911.1.h.d 4 39.d odd 2 1 CM
1911.1.h.e yes 4 7.b odd 2 1
1911.1.h.e yes 4 21.c even 2 1
1911.1.h.e yes 4 91.b odd 2 1
1911.1.h.e yes 4 273.g even 2 1
1911.1.w.e 8 7.d odd 6 2
1911.1.w.e 8 21.g even 6 2
1911.1.w.e 8 91.s odd 6 2
1911.1.w.e 8 273.ba even 6 2
1911.1.w.f 8 7.c even 3 2
1911.1.w.f 8 21.h odd 6 2
1911.1.w.f 8 91.r even 6 2
1911.1.w.f 8 273.w odd 6 2

## Hecke kernels

This newform subspace can be constructed as the intersection of the kernels of the following linear operators acting on $$S_{1}^{\mathrm{new}}(1911, [\chi])$$:

 $$T_{2}^{4} - 4 T_{2}^{2} + 2$$ $$T_{61}$$ $$T_{199} - 2$$

## Hecke characteristic polynomials

$p$ $F_p(T)$
$2$ $$2 - 4 T^{2} + T^{4}$$
$3$ $$( 1 + T )^{4}$$
$5$ $$2 - 4 T^{2} + T^{4}$$
$7$ $$T^{4}$$
$11$ $$2 - 4 T^{2} + T^{4}$$
$13$ $$( -1 + T )^{4}$$
$17$ $$T^{4}$$
$19$ $$T^{4}$$
$23$ $$T^{4}$$
$29$ $$T^{4}$$
$31$ $$T^{4}$$
$37$ $$T^{4}$$
$41$ $$2 - 4 T^{2} + T^{4}$$
$43$ $$T^{4}$$
$47$ $$2 - 4 T^{2} + T^{4}$$
$53$ $$T^{4}$$
$59$ $$2 - 4 T^{2} + T^{4}$$
$61$ $$T^{4}$$
$67$ $$T^{4}$$
$71$ $$2 - 4 T^{2} + T^{4}$$
$73$ $$T^{4}$$
$79$ $$( -2 + T^{2} )^{2}$$
$83$ $$2 - 4 T^{2} + T^{4}$$
$89$ $$2 - 4 T^{2} + T^{4}$$
$97$ $$T^{4}$$


text:
Question: Why does Deseq, Deseq2, and EdgeR give vastly different results.
1
2.4 years ago by
michael.steffen20 wrote:

I am trying to understand why I am getting vastly different results between these 3 different program. I understand why Deseq probably isn't appropriate to use anymore, but I don't understand why Deseq2 and EdgeR are giving such different numbers of DEGs.

Below is the code for Deseq. This results in 146 DEGs:

expt_design <- data.frame(row.names = colnames(total_counts),
condition = c("YQ", "YW", "OQ", "OW", "OQ", "OW", "OQ", "OW", "YQ", "YW", "YQ", "YW", "OS", "YS", "YS", "OS", "YS", "OS"))
conditions = expt_design$condition # Input Data into DESeq data <- newCountDataSet(total_counts, conditions) #Estimate size factors - difference in coverage between replicates data <- estimateSizeFactors(data) sizeFactors(data) # Estimate dispersion which is computed per-condition data <- estimateDispersions( data, method="blind", sharingMode="fit-only") dispTable (data) #Example pairwise minimum group test. OQ_YQ <- nbinomTest( data, "OQ", "YQ") write.table(OQ_YQ,file="TotalResults.txt",sep="\t",row.names=rownames(OQ_YQ), col.names=colnames(OQ_YQ),quote=F) OQ_YQ.Sig <- OQ_YQ[ OQ_YQ$padj < .05, ]
OQ_YQ.Sig <- OQ_YQ.Sig[complete.cases(OQ_YQ.Sig),]
write.table(OQ_YQ.Sig,file="Results_sig.txt",sep="\t",row.names=rownames(OQ_YQ.Sig),
col.names=colnames(OQ_YQ.Sig),quote=F)
#End DESeq (v1) example

Below is the code for Deseq2. This results in Zero DEGS:

expt_design <- data.frame(rows = colnames(total_counts),
condition = c("YQ", "YW", "OQ", "OW", "OQ", "OW", "OQ", "OW", "YQ", "YW", "YQ", "YW", "OS", "YS", "YS", "OS", "YS", "OS"))

dds <- DESeqDataSetFromMatrix( countData = total_counts, colData = expt_design,
design = ~ condition)

dds <- estimateSizeFactors(dds)
dds <- estimateDispersions(dds)
dds <- nbinomWaldTest(dds)
dds
OQ_YQ <- results(dds, contrast=c("condition","QW","YQ"))
OQ_YQ <- as.data.frame(QWvsYQ)
write.csv(OQ_YQ, "Results.csv", row.names=TRUE)
#End Deseq2 examples

Below is the code I have used for EdgeR. This results in 15 DEGs:

#Start edgeR example
group <- factor(c("YQ", "YW", "OQ", "OW", "OQ", "OW", "OQ", "OW", "YQ", "YW", "YQ", "YW", "OS", "YS", "YS", "OS", "YS", "OS"))
y <- DGEList(counts=x,group=group)
y <- calcNormFactors(y)
design <- model.matrix(~0+group)
y <- estimateGLMCommonDisp(y, design)
y <- estimateGLMTrendedDisp(y, design)
y <- estimateGLMTagwiseDisp(y, design)
fit <- glmFit(y, design)

#Test Group 1 vs Group 2
lrt <- glmLRT(fit, contrast=c(-1,1,0,0,0,0))
topTags(lrt)
tab1 <- topTags(lrt, n=Inf)
write.csv(tab1, file="Results.csv")

So why do you get such differences? Its all using the same data. Am I doing something wrong in these? All data is raw count data from an RNAseq experiment. The thing that particularly concerns me is using the same code on different data, the DEG breakdown goes as follows: Deseq:59, Deseq2:606, EdgeR: 350. This is going in vastly different directions than the previous dataset, so consistence kind of goes out the window.

Thanks,

Mike

edger deseq deseq2 • 1.8k views
modified 2.3 years ago • written 2.4 years ago by michael.steffen20
Answer: Why does Deseq, Deseq2, and EdgeR give vastly different results.
2
2.4 years ago by
Aaron Lun25k
Cambridge, United Kingdom
Aaron Lun25k wrote:

Well, for starters, it seems like you're using edgeR's glmLRT to compare the first two groups, which are OQ and OS. But it looks like you're comparing different groups with DESeq2, namely QW and YQ (despite the fact that the variable is named OQ_YQ). And for DESeq, again a different comparison: OQ and YQ.

Needless to say, there's no guarantee of getting the same DE genes across different contrasts.

1

Sorry, yeah, that was a typo. It was meant to be the same exact comparisions that I posted. I had done multiple comparisons across different things and copied the wrong comparisons code, but everything should be the same across comparisons.

I edited the question to now reflect that properly.

Mike

Different methods will produce different sets of results, this is true for even basic statistical tests (t-test and Wilcoxon and so on). The methods' operating characteristics also depend on the dataset (in terms of sample size, dynamic range, biological variability, effect size distribution, etc., etc.). If you look at benchmarks, the behavior is pretty consistent, and methods tend to have high overlap on the top 'x' genes. See e.g.:

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4878611/


text:
# Thread: how to differentiate e^(x/y) with respect to 1) x and 2) y

1. ## how to differentiate e^(x/y) with respect to 1) x and 2) y

how to differentiate e^(x/y) with respect to
1) x and
2) y

2. Originally Posted by itsmusa7
how to differentiate e^(x/y) with respect to
1) x and
2) y

$\displaystyle f(x,y) = e^{\frac{x}{y}}$

Now for (1) calculate $\frac{df}{dx}$, treating y as constant

then for (2) calculate $\frac{df}{dy}$, treating x as constant

If you are stuck at the beginning tell us and we'll start with the definitions.

http://www.freemathhelp.com/forum/th...217#post322217

3. ## Re: how to differentiate e^(x/y) with respect to 1) x and 2) y

Thank You sir for helping me, but I think I haven't got the help I needed. I needed the process of differentiating e^(x/y) with respect to 1) x and 2) y, especially " y ", because I know the process of differentiating it with respect to " x ", but never did it with respect to " y ". And I think I've posted my question in the wrong category. Sorry for that. I have read your forum rules " before posting " and I'll be careful in future. Thanks

4. Originally Posted by itsmusa7
Thank You sir for helping me, but I think I haven't got the help I needed. I needed the process of differentiating e^(x/y) with respect to 1) x and 2) y, especially " y ", because I know the process of differentiating it with respect to " x ", but never did it with respect to " y ". And I think I've posted my question in the wrong category. Sorry for that. I have read your forum rules " before posting " and I'll be careful in future. Thanks

z = e^(a/x) ................ where 'a' is a constant

can you calculate dz/dx?

5. What you need is the "chain rule": the derivative of $e^{f(x)}$ with respect to x is $e^{f(x)}\frac{df}{dx}$.

Now, differentinating $e^{x/y}$ with respect to x, f(x)= x/y. What is the derivative of x/y with respect to x?

Differentiating $e^{x/y}$ with respect to y, $f(y)= x/y= xy^{-1}$. What is the derivative of $xy^{-1}$ with respect to y?


text:
# Partial derivative properties rule

Hi I need help regarding following

can I write following partial derivative wrt x multiplied by Ax

(∂A[x])Ax =∂(Ax^2)

mathman
Hi I need help regarding following

can I write following partial derivative wrt x multiplied by Ax

(∂A[x])Ax =∂(Ax^2)

Usually they would by interpreted differently. The left side is Ax multiplied by the derivative of Ax, while the right side is the derivative of the square.

What do you mean by the square brackets on the LHS? I.e., does it mean A is a function of x or is it an unnecessary bracket?

Are you asking does the following hold true
$$\left( \frac{\partial}{\partial x} \left( Ax \right) \right) Ax = \frac{\partial}{\partial x} \left( (Ax)^{2} \right)$$

(i.e., is the derivative of the square of the function##Ax## wrt x (right hand side) equal the derivative of the function ##Ax## multiplied by ##Ax##)

?

Or is A a constant? If so then they aren't the same thing,

Last edited:
Fredrik
Staff Emeritus
Gold Member
Hi I need help regarding following

can I write following partial derivative wrt x multiplied by Ax

(∂A[x])Ax =∂(Ax^2)
It's impossible to know what you mean by that notation. You have to provide more information when you ask a question.

Looks like more than one person in this thread might find the LaTeX FAQ useful. https://www.physicsforums.com/showthread.php?p=3977517#post3977517

Last edited:
HallsofIvy
$$\frac{\partial Ax}{\partial x} Ax= \frac{\partial Ax^2}{\partial x}$$?
$$\frac{\partial Ax}{\partial x}Ax= A^2x \frac{\partial x}{\partial x}= A^2x$$
$$\frac{\partial Ax^2}{\partial x}= A\frac{\partial x^2}{\partial x}= 2Ax$$


text: In this talk we present some recent results obtained in a joint work with K. Li and J. M. Martell, about a multivariable Rubio de Francia extrapolation theorem for multilinear Muckenhoupt classes $A_{\vec{p}}$, and also some extensions to more general classes of weights.To illustrate the power of extrapolation methods we will present some applications of the beforementioned results and some mixed weak-type weighted estimates obtained in a joint work with K. Li and C. P\'erez.


text:
# Unusual Rotary Encoder Output

I'm trying to replace a rotary encoder with push switch from a Boss SE70 effects unit as the switch is broken; the same encoder is apparently used in a number of Roland products such as the JD-990, JV-1080, SC-880 and JV-880 (all '90s vintage I think).

This type of repair is normally straightforward: find something that is roughly the same mechanically and electrically. The part is listed as an RK09710WL, with Roland part number 13289196. I can't find any data on this part other than it was made by Alps (marked on the base). It has 20 detents.

I chose a Bourns PEC11R-4230F-S0024 as it was the right length, had a switch and had roughly the same amount of pulses (24 rather than 20 on the original) and detents. It even had pretty much the same footprint.

However it does not work. It seems that the encoder used by Roland gives a very different output to commonly used rotary encoders.

With the replacement encoder installed (that does not work correctly), the output from the two pins is as expected (direction reversed half way) for most rotary encoders:

With the standard (working correctly bar switch) encoder in place, the output is:

The stock encoder sends a short pulse (<50ms) on one pin only when turned in one direction and a pulse on the other pin only when turned in the opposite direction.

I've never seen a rotary encoder with this kind of output - does anyone know what it is and how to find a replacement? The dimensions are not too important as the encoder mounts on a small PCB (no other components on the board) and is chassis mounted so anything can probably be made to work, but that unusual output is needed.

Here is the excerpt from the schematic:

The rotary encoder lines connect to pull up resistors and debounce/filter resistors and capacitors, then to microprocessor pins as expected.

Can anyone provide any help, information or guidance?

• I'm noticing, but perhaps over-thinking it, that the width of the pulses correlates with the rate of rotation vs time -- slower rates yield wider pulse widths. This is perhaps useful information used by Roland. It might change the "feel" to always use the same pulse width. Do you notice the same here? Or is this just me? Can you consider a full break-down of one of these switch systems? – jonk Nov 16 '18 at 21:13
• The width of the pulse probably does change with the speed of turning, but the knob is only used to scroll through presets and so on, so is only used in quite a basic way. It is tempting to dismantle it, but it (the switch) works enough that I don't want to do that if I can't find a replacement. It isn't held together with tabs, so would be destroyed. – Duntle Nov 16 '18 at 22:01
• that is a rotary pulse switch ...... see comment from @Justme here electronics.stackexchange.com/questions/404734/… – jsotola Nov 17 '18 at 7:47
• Excellent information - does anyone know where such things can be bought or even anyone that makes them? – Duntle Nov 17 '18 at 9:53
• It seems these things are very few and far between and there is not necessarily any specific name for them. Searching for rotary pulse switch often finds rotary encoders. Alps sell a couple and call them rotary switches: SRBM1L0800 & SRBM1L1400, but neither have a push switch as well. – Duntle Nov 17 '18 at 14:56

Apparently, that encoder has built-in circuitry

1. to debounce the signal edges;
2. to detect the direction (by reading the state of the other line when an edge happens on the first one); and
3. to generate a short pulse.

Nowadays, all this can be done in a microcontroller, so it is unlikely that a direct replacement is still made.

It would be possible to build your own circuit to do this (with RC filters, logic gates, and a monostable (555 or 74xx123)), but a microcontroller board might be easier.

• It's a fun exercise to do that one with a 555, a JK flip-flop and some gates. I've done it on paper before but never for real. There may actually be a chip out there that does that, but I have no clue what name to look for (aside from "itty bitty microcontroller with custom programming). – TimWescott Nov 16 '18 at 21:36
• It does seem like there is some processing going on in the encoder, but is that possible given it is no bigger than a normal encoder and has no power. The debouncing is done outside the switch and it then connects to a microcontroller or microprocessor (custom Roland chip), which surely could also do all decoding of "normal" signals. It all just seems a bit odd. – Duntle Nov 16 '18 at 21:58
• Hmm, without power, all I can imagine would be some mechanical contraption. But that makes it even less likely to find identical hardware. – CL. Nov 17 '18 at 8:27


text:
### platypus179's blog

By platypus179, history, 5 years ago, translation,

Ladies and Gentlemen!

The Codeforces round #359 for both divisions will happen on 23 June at 7:35 PM MSK. We have been choosing and solving problems for a long time and we hope that they will seem quite interesting.

All of the problems were created under guidance of Endagorion (Mikhail Tikhomirov) by Moscow high school graduates: cdkrot (Dmitry Sayutin), ch_egor (Egor Chunaev), themikemikovi4 (Mikhail Sorokin) and me. It is our second Codeforces Div.1 + Div.2 round.

Thanks to coordinator GlebsHP (Gleb Evstropov) for help with preparing problems and to MikeMirzayanov (Mikhail Mirzayanov) for excellent systems Polygon and Codeforces. Also, the round is possible only because of Endagorion's help.

Participants will be given five problems in both divisions. The scoring distribution will be announced later.

Good luck to all!

UPD: All statements are based on the fairy tale "The Snow Queen" by H. C. Andersen.

UPD2: The scoring distribution:

Div. 1: 500-1250-1250-2000-2500

Div. 2: 500-1000-1500-2250-2250

UPD3: Congratulations to the winners!

Div. 1:

Div. 2:

UPD4:

Cheating detection may affect the ratings a little.

UPD5:

The editorial can be found here.

• +461

 » 5 years ago, # | ← Rev. 2 →   +8 Before 3 days , that's too early ! thanks at all
•  » » 5 years ago, # ^ |   -55 Road to 1720+
• »
»
5 years ago, # ^ |
-31

### Road to 1800+

•  » » 5 years ago, # ^ |   -52 EZ PZ +1720
•  » » 5 years ago, # ^ |   -27 HI EVERYBODY!!!!!!!!!! try pressing the the Caps Lock key O THANKS!!! ITS SO MUCH EASIER TO WRITE NOW!!!!!!! fak me
•  » » » 5 years ago, # ^ |   +9 What's your meaning?
•  » » » 5 years ago, # ^ |   +20 Feel like you are drunk.
•  » » » » 5 years ago, # ^ |   -10 No, it is a joke.Just the high rating can understand it.
•  » » » » » 5 years ago, # ^ |   +26 Okay then. Wish I will understand it someday.
•  » » » » » » 5 years ago, # ^ |   -14 ROAD TO FUCKING +1720
•  » » » » » » » 5 years ago, # ^ |   +24 don't think you can fuck a number
•  » » » » » » » » 5 years ago, # ^ |   +21 I see you are humorist.
 » 5 years ago, # |   -41 Good luck for everybody !
 » 5 years ago, # |   -58 Hoping to step up my game in this contest. :D
 » 5 years ago, # |   +59 This will be my first Div1 contest! Hope I don't do anything silly!
•  » » 5 years ago, # ^ |   +13 It's strange, I also hope I don't do anything silly, but it's not my first div 1 round :-? wonderful! isn't it?!
•  » » » 5 years ago, # ^ |   +12 Your commitment counts more than your performance. Looking at your history you definitely have commitment and I have the utmost respect for that!
 » 5 years ago, # |   -21 My rating has been dropping since forever. Hope i do not do anything stupid and finally increase my rating. :)
•  » » 5 years ago, # ^ |   +27 and your contribution.
 » 5 years ago, # |   +346
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 EDIT: ignore my reply, I mistook the post for something else, not a big dealThis glitch has been around for as long as I can remember, hope it gets a quick fix
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Which glitch are you talking about? If I am not mistaken, I don't see any glitch there.
•  » » » » 5 years ago, # ^ |   0 Sorry my bad, I thought the entries were doubled
 » 5 years ago, # |   -25 Hope Everyone Gets a new level up color , me also :)
 » 5 years ago, # |   -34 looking forward to do 3/5. :D
 » 5 years ago, # |   +32 Its just the right time, the contest is just being held on the day without Euro
•  » » 5 years ago, # ^ | ← Rev. 3 →   -36 Lucky you :D , it's the contrary here, the timing couldn't be worse for any rated round as I have to do stuff in the middle having only 1.5 hours at best :(
 » 5 years ago, # |   -15 Your last round was a round for hackers, not for coders, I hope we won't see the same tomorrow...
•  » » 5 years ago, # ^ | ← Rev. 6 →   +58 Actually, last time we just didn't put the overflow test in Div2A pretests.Of course, in some problems we will exclude some special cases from pretests. The process of dividing tests on pretests and system tests has many functions that are not related to the testing speed. For example, some people may learn to test their code after they get hacked.And of course, we try to make the round interesting to solve. We didn't expect to have so much hacks on integer overflow. Hope this particular mistake is an exception rather then the rule.
•  » » 5 years ago, # ^ |   +26 So as you wish, this round there were no hacks (at least in Div.1)
•  » » » 5 years ago, # ^ |   +9 And also in Div.2 :V
 » 5 years ago, # |   +19 This is one of the reasons that make codeforces a special site.. Its attractive way of announcements. Thanks platypus179
 » 5 years ago, # |   -42 it's summer and the contest labeled with " The Snow Queen " , Nice name in wrong time
•  » » 5 years ago, # ^ |   +65 Im quite sure that Snow Queen will ask us for a help because of such a nice(not for her) weather.
•  » » 5 years ago, # ^ |   +37 It's summer only in the Northern Hemisphere.
 » 5 years ago, # |   -21 platypus179 Said, "the round is possible only because of Endagorion's help ". And I love Endagorion's Problems.
 » 5 years ago, # |   -40 What's up with so many downvotes on simple good luck wishes or hopeful comments? :O
•  » » 5 years ago, # ^ |   0 because these comments are common and annoying.
 » 5 years ago, # |   +2 The only time I've got rating rise is when I'm in a foul or depressed mood. This isn't good I'm afraid
 » 5 years ago, # |   0 How can a contest be based on a fairy tail? Can anyone explain? Thank u.
•  » » 5 years ago, # ^ |   0 Something like that: http://codeforces.com/blog/entry/13247.
 » 5 years ago, # |   -24 I wish the time of the contest will be any time instead of breakfast time for muslims people in ramadan :/ , there is many contest in this time , can any one who will create a new contest can make it any time but not in our breakfast time ?, i think there is many Programmers will join it
•  » » 5 years ago, # ^ |   +14 time comfortable for you maybe uncomfortable for someone else
•  » » » 5 years ago, # ^ |   0 i think so :/ , but i need to change my rating :"(
•  » » 5 years ago, # ^ |   +21 Happy Ramadan
•  » » » 5 years ago, # ^ |   0 Thanks :) !
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I wanted to write something insulting here about muslims misconceptions, but didnt find proper words.
 » 5 years ago, # |   +7 It's so sad that I have two exams after tomorrow. But I can't help but give up this contest because the time of the contest is too late for me to have a good sleep. I really want to be a Div.1 player.
•  » » 5 years ago, # ^ |   +14 So sad.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -23 That story is fake
 » 5 years ago, # |   0 Who can tell me what the picture means?
•  » » 5 years ago, # ^ |   +145 The Snow Queen shows a young boy how it is to participate in a Div1 contest.Seriously, what explanation do you expect? If you're interested in the story then google "Andersen Snow Queen".
•  » » » 5 years ago, # ^ |   +12 Thank you
•  » » 5 years ago, # ^ |   +13 This has a complete explanantion of the story and of the picture. Here is what it says about the picture: "The following winter, Kay goes out with his sled to play in the snowy market square and — as was the custom — hitches it to a curious white sleigh carriage, driven by the Snow Queen, who appears as a woman in a white fur-coat. Outside the city she reveals herself to Kay and kisses him twice: once to numb him from the cold, and a second time to make him forget about Gerda and his family; a third kiss would kill him. She takes Kay in her sleigh to her palace."
 » 5 years ago, # |   +2 Good luck to all !
 » 5 years ago, # |   -6 The scoring distribution will be announced later？
•  » » 5 years ago, # ^ |   +32 You have to form the word "eternity" from pieces of ice to know the score distribution
 » 5 years ago, # |   +17 The score distribution shows D and E have same points...this one is going to be a tricky contest :D
 » 5 years ago, # |   +27 Summary of my participation:-Solves A relatively fast--Solves B relatively fast-"Hey, C is as hard as B so that shouldn't take long."-Proceed to dwell for an hour and a half without any results-I god damn hope C has some very magical and easy observation that leads to an elegant solution, cause else that scoring was atrocious :D
•  » » 5 years ago, # ^ |   0 How to solve your B?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -14 Don't know if you meant the division 1 B, but for Div2 I brute forced it, manually swapping two elements at a time when necessary and after every swap checking if it's sorted.
•  » » » » 5 years ago, # ^ |   0 I don't say div.2 B!
•  » » 5 years ago, # ^ |   -9 Yeah, you can simply check all pairs if sum of number of digits in the first one and the second one is <= 7, there are not many of those pairs I assume :D
•  » » » 5 years ago, # ^ |   +6 He's talking about Div.1 C I believe.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 I don't think he is talking about div2 C :P
•  » » » » 5 years ago, # ^ |   0 Oops, I forgot that there was a Div1, not used to it, sorry!
•  » » 5 years ago, # ^ |   +23 In C I moved to 4-dimensional space: (x, y, z) -  > (x + y + z, x + y - z, x - y + z, x - y - z) and used binary search in which I just intersected 4-dimensional cubes. But it's not enough to check that the intersection is not empty, you should also check that it has nonempty preimage.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +11 I used the same approach but failed. It might be easier if the distance was asked instead of the actual point :(
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 I can't understand, can you elaborate please? How does 4 dimension help? Also, can anyone suggest some problems which can be solved in similar way?
•  » » » » 5 years ago, # ^ |   +8 In Manhattan metric sphere is octahedron. Mentioned transform maps it to hypercube. Intersecting hypercubes is done coordinate-wise. After that we need to check that intersection has nonempty preimage. Ifa = x + y + z, b = x + y - z, c = x - y + z, d = x - y - z, thenx = (a + d) / 2 = (b + c) / 2, y = (a - c) / 2 = (b - d) / 2, z = (a - b) / 2 = (c - d) / 2.So the image of contains all integer points in hyperplane a - b - c + d = 0 with a ≡ b ≡ c ≡ d(mod 2). So we need to intersect that hyperplane with our cube and check some cases.There was similar problem on IOI 2007(link, problem "pairs").
•  » » 5 years ago, # ^ |   +1 Don't worry, it could have been much worse :D-Solves A relatively fast--Solves B relatively fast--Codes C relatively fast-Then try to debug WA for 1 hour. The only mistake in the code? I was checking if the number was odd by doing "number % 2 == 1".
•  » » » 5 years ago, # ^ |   0 What is wrong with that check?
•  » » » » 5 years ago, # ^ |   +6 -1 % 2 is -1, not 1 :(
•  » » » » » 5 years ago, # ^ |   0 Ok, I've forgotten about negative numbers.
•  » » » » » 5 years ago, # ^ |   0 Yeah, this test was put in statement by exactly same reason.
•  » » » 5 years ago, # ^ |   0 Solving B after 50 minutes seems relatively slow for you :p
 » 5 years ago, # | ← Rev. 2 →   +3 Do DIV 2 4th has a solution with binary search and dfs at each node?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 Yes, it can be done with binary search. First , we need to decompose the tree into chains using a dfs, by moving from a node to its largest sized sub-tree . Centroid of the subtree of node v, will lie somewhere on the chain consisting of v,below v.Now independently solve each chain. Suppose our chain has size x and we want to find the centroid for ith node in this chain , say chain[i].Now the centroid of chain[i] will be the first node chain[j] , i <  = j <  = x , such that maxChildSubtreesize[j] <  = Subtreesize[i] / 2 . Also , maxChildSubtreesize[j] is a decreasing function since we are moving down the tree. So, we can apply binary search with lower bound as i and upper bound as x.Overall Complexity :O(nlogn)Code
 » 5 years ago, # |   +9 Was O(log3(1018)) enough in C? I implemented O(log(1018)) but damn, that wasn't easy.
•  » » 5 years ago, # ^ |   0 What's your solution?I implemented binary search to get 4 inequalities A<=x +/- y +/- z<=B (assuming that 3d solution should be similar to 2d vesrion) and then realized that I have no idea how to actually find some integer solution (x,y,z) from these inequalities, or at least how to check that there exists one :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Ternary search on one coordinate z. For fixed z I have four inequalities and I claim that the value of answer is maximum of distances between parallel inequalities. This allows to find optimal z but not to find optimal x, y then.Maybe I should then ternary search the next coordinate but I think it's hard to implement. So instead for the found four inequalities I imagines drawing four lines, then I found two intersections (an intersection of leftup and leftdown lines, and an intersection of rightup and rightdown lines) and then the answer should be in the middle of segment connecting the two intersections. I didn't know if I can round the answer (found x, y) to closest integers so I checked brutally all 22 possibilities of rounding.
•  » » » 5 years ago, # ^ |   0 Is this correct for 2D version ? A=(min(Xi+Yi)+max(Xi+Yi))/2; B=(min(Xi-Yi)+max(Xi-Yi))/2; and you can get answerX and answerY from this answerX+answerY=A; answerX-answerY=B; answerX=(A+B)/2; answerY=(A-B)/2; I used same solution for 3D (4 coordinates for each point) , but got WA 6
•  » » » » 5 years ago, # ^ |   0 It is a bit more complicated. You have constrains on x + y + z, -x + y + z, x — y + z, x + y — z.The problem is about solving them
•  » » » » 5 years ago, # ^ |   -10 Same, I got WA4. I'm 99% sure it's correct for the 2D case, and some version of this idea really ought to work for the 3D one. One mistake which I couldn't fix in time: Adding 3 coordinates (or even 6 when taking average by (min+max)/2) can get you an overflow! Did you avoid that?
•  » » » » » 5 years ago, # ^ |   0 after WA#5 I checked x-3..x+3 y-3..y+3 z-3..z+3 , and it helped for test #5 :D
•  » » » 5 years ago, # ^ |   +10 It really is the same, you can consider: x + y + z, x + y — z, x — y + z and y + z — x. Transforming a point in such a tuple, it becames similar to 2D version(the rotation in 2D) and binary searching is enough. The very very stupid thing is that you really have to take care of overflow and of some parities as well and it's pretty ugly. The problem would have been much nicer if they fixed the limita 10^17 and the problem had a higher score. I didn't even had time to think at the other tasks and still have to write some more lines...I guess that in k-D plane, you have 2 ^ (D — 1) elements in tuples. I really liked that the rotation can be generalizate but the overflow really destroy the task
•  » » » » 5 years ago, # ^ |   0 I thought about overflow, but I don't think I can get any number out of range {-6*10^18 .. 6*10^18 }
•  » » » » » 5 years ago, # ^ |   0 Ohh never mind, thought the long long limit was around 2*10^18. No idea what my mistake was, in this case...
•  » » » » » » 5 years ago, # ^ |   0 Try this test: 1 3 10 10 10 10 9 10 10 10 9 This is a test where, in my source, at least, I had to take care at parity. I think I solved it now but I am unable to submit because it seems that they didn't enable the practice session yet
•  » » » » » » » 5 years ago, # ^ |   0 That is a counterexample indeed, thanks!
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Could you explain how you got overflow?Proposed solution fits in long long quite well.
•  » » » » » 5 years ago, # ^ |   +5 Well I didn't but theoretically some lines could get overflow so I thought a lot about how to improve them. For example, as in editorial, let's fix L the maximum distance, we had relations like maxA — L <= a <= minA + L and so on and we had one more for their sum maxS — L <= a + b + c <= minS + L. We had to intersect the intervals [maxS — L, minS + L] with [maxA + maxB + maxC — 3 * L, minA + minB + minC + 3 * L]. The ends of the later are very big in worst case...I hardly came up with a solution to treat those overflows.
•  » » » » » » 5 years ago, # ^ |   +33 Ouch, i see now. I should have set 1017 bound.My solution got over this trouble because of parity handling, when replacing a = 2a' + r, not only parity restriction goes away, but coordinates also become twice less.
•  » » » » » » » 5 years ago, # ^ |   0 Yeah, I made the same mistake once in one of my problems — 611G - New Year and Cake.We realized about possible problems with overflow in the day of the contest and I didn't have time to decrease constraints from 109 to 108. In hurry I added two tests designed to cause overflow (because if such malicious tests are valid then a setter should add them) and I put one of them in pretests. One participant had a bad luck and his solution passed pretests but didn't pass the other overflow-test and thus got WA on systests. Fortunately, he won anyway.One thing is that I should have set 108 in the first place. But since there was no time, I should have include both malicious tests in pretests. I learnt a lesson that day.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +10 Let x+y+z=C, x-y+z=D, x-y-z=E, x+y-z=F.There is integral solution to system if and only if C,D,E,F all have the same parity and C-D+E = F.What I did was, for each possible parity, take C,D,E to be the smallest possible and calculate value of C-D+E. Then try to make it fit into range of F inequalities by increasing C/E (if C-D+E is too small) or increasing D (if C-D+E is too big).
•  » » » 5 years ago, # ^ |   0 Turns out that bruteforcing a 3x3 cube around the non-integer solution works. No need to do any parity fiddling.18693710
•  » » 5 years ago, # ^ |   +79 Seems this was the worst difficulty estimation I made this year :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +47 But problems were nice and there were no issues. #smallmiraclesAnd I liked the fact that pretests were strong.
•  » » » » 5 years ago, # ^ |   +5 True. No hacks in Div1, only 5 hacks in Div2
•  » » 5 years ago, # ^ |   0 No, it wasn't. O(log) is proposed solution.
 » 5 years ago, # |   +15 The problem C sucks. Don't know what the statement want to say. My poor English. :(
•  » » 5 years ago, # ^ |   -31 Yeah me too so I send them this But they didn't respond for some reason i can't explain.But i was able to solve it somehow!
 » 5 years ago, # |   0 I loved the contest — the tasks were challenging but I hope I did 4 tasks correctly, we'll see :)
 » 5 years ago, # |   +3 Unexpected typing contest :P I thought Div1D was relatively easy than Div1C, and wanted to submit it T.T
 » 5 years ago, # |   +6 Testcase 11 div2 C :|
•  » » 5 years ago, # ^ |   +3 same here
•  » » 5 years ago, # ^ |   +6 Did you take log(n) or log(n — 1) ?
•  » » 5 years ago, # ^ |   0 I also stuck at that testcasebut after change (hourlength+minutelength > 6) to ( > 7)it passed.
•  » » 5 years ago, # ^ |   0 i was also stuck on that tc, implemented a recursive descent solution, testing out all possible combinations of different numbers. then i realised that i need to make room for 0 to n-1, instead of 0 to n so i think the tc is something like: 343 2401, where my program would output 0, while there is a solution :(
•  » » » 5 years ago, # ^ |   0 just had to do a n--,m--; at the start done the same mistake :(
•  » » 5 years ago, # ^ |   0 Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
•  » » » 5 years ago, # ^ |   0 LOL same xD
•  » » 5 years ago, # ^ |   +1 Don't remind me :"( That pretest 11, I really wonder what it is.
 » 5 years ago, # |   0 How to solve E ? I have a O(n m) solution that runs in 1450ms on a random test of maximum size, how to do better ?
 » 5 years ago, # | ← Rev. 2 →   +11 What is 11 pretest in Div2C?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 try this one:7 7the answer is 42
•  » » » 5 years ago, # ^ |   0 Answer?
•  » » » 5 years ago, # ^ |   0 getting 0
•  » » » 5 years ago, # ^ |   0 Shouldn't it be 0? Any single digit hour will have leading zero and so the single digit minute too? 01:02. Then 0 is duplicated (?)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 You need only one digit for hours and one digit for minutes.not 01:02 but 1:2
•  » » » » 5 years ago, # ^ |   +6 No, the watch will only have 1 digit because 1 digit is sufficient to represent 0-6. (6 = n — 1 = 7 — 1)
•  » » » » » 5 years ago, # ^ |   +1 Oh shit, forgot than numbers are in range 0, n — 1 and 0, m — 1.
•  » » » » » » 5 years ago, # ^ |   +1 same here. forgot to n--;m--;
•  » » » 5 years ago, # ^ |   0 Answer to the Ultimate Question of Life, the Universe, and Everything...
•  » » 5 years ago, # ^ |   0 Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)
 » 5 years ago, # |   +101 Div1 B and C having same score doesn't even sound funny...
 » 5 years ago, # |   +11 Problem B is classic. So many people know it. I remember have solved it! It's not fair!
•  » » 5 years ago, # ^ |   +8 How do you solve it? I've never seen finding centroid before...
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 My idea is tree dp. Here's a brief sketch of my idea :Do standard subtree size dp. For each node, determine the maximum subtree size of its children. Then, we calculate the answer for each node which is closest to the root. (actually I think I implemented something slightly different in my solution) We consider whether the node itself is actually a centroid and also which nodes to take from the childrens. This sketch is not very detailed but this is briefly what I did.UPD : It got Accepted! Basically, I stored a "jump pointer" on each node, which is initially the answer for that node (after we finish dfsing the node). Then, when we process the parent, this "jump pointer" jumps depending whether jumping to the parent will yield a better centroid (better centroid means maximum subtree size is lesser, with ties broken using distance from root). Using this, for each child of a node that we're currently processing, if the node itself is a centroid, we take the node. Otherwise, we check the jump pointers in the childrens. Code
•  » » » » 5 years ago, # ^ |   0 Why closest to the root? And what's the time complexity?
•  » » » » » 5 years ago, # ^ |   0 It's ~3am here so I'm lazy to go over the details. Actually, it doesn't need to be closest to the root I think, it's something like this.Time Complexity should be O(n) I think.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Brief basica idea: dp on tree when you process subtree rooted at v check if v can be centroid if it can't be centroid, then the centroid will be on the path largest_child_of_v -> centroid[largest_child_of_v] It is enough to start with the centroid on the largest child and move up by parents until you find the centroid of the v. Amortized time os O(n).
 » 5 years ago, # |   +3 Div1C: I found a possible overflow bug 10 sec before the end, couldn't submit in time... I REALLY hope that wasn't my only mistake and I didn't mess up by literally less than a minute :D
 » 5 years ago, # |   -29
 » 5 years ago, # |   +8 Why is the memory limit so tight in Div1-D? My solution went a few MB over. :(
•  » » 5 years ago, # ^ |   -16 We know solution with linear amount of memory.
•  » » » 5 years ago, # ^ |   +11 The solution in the editorial uses O(nk) memory. I had two arrays of size n*k each, they require some 228 MB. 256 MB memory limit definitely seems too strict if you intended to allow O(nk) memory solutions to pass.
 » 5 years ago, # | ← Rev. 2 →   0 In task E (div. 2) we need to find min-size enclosing octahedron, but it turns out a little bit difficult...
 » 5 years ago, # |   +3 My solution for D went stack-overflow on my computer but passed the pretest :v Guess it will fail the system test :v
•  » » 5 years ago, # ^ |   +8 Same happened with me. I wasted 25 minutes on this issue. Later I tested it through custom invocation and it worked.
•  » » » 5 years ago, # ^ |   +11 Same with me. I resubmitted in panic, only to realise it wasn't necessary!
 » 5 years ago, # |   0 Can someone give hint for DIV2 C ? Cheers =)
•  » » 5 years ago, # ^ |   +14 bruteforce , the max length of answer can be 7 as for answer more than 7 , atleast 1 digit will be repeated.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 My bruteforce seems to give TLE on pretest 13. Plz look at this code: http://codeforces.com/contest/686/submission/18685502
•  » » » » 5 years ago, # ^ |   0 dont use strings
•  » » » » » 5 years ago, # ^ |   0 Why do they take more time as compared to arrays?
•  » » » » » 5 years ago, # ^ |   0 I used strings and didn't get TLE
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Though an overkill, you can use digit dp to solve it too O(log(N) * 210 * log(M)) which is O(logN * log(M)) (Not really :P ).18689097I had to code both the solutions as digit dp didn't pass as I was missing returning 0 when the input was 0 in the base_7 function, so eventually writing this code so fast was of no use.
 » 5 years ago, # |   +8 Somehow misread that m ≤ 1000 (instead of correct 200'000), invented a n3 / 32 solution, implemented it... and finally noticed that I'd misread the constraints.***k.
 » 5 years ago, # |   +1 Going through the stats:pretest ones: Div 2 Problem B was solved by 2700+ and Div 2 Problem C was solved by only 791 which suggests that C should be of more points as compared to B
•  » » 5 years ago, # ^ |   0 Good thing it is I guess?
 » 5 years ago, # | ← Rev. 3 →   +3 Python is really troublesome:A: O(7^7) [7^7 is less than 1 million] run in >3s on custom invocation, need O(7!) [7 factorial] to pass pretest.B: Fast I/O required, otherwise it will be TLE on pretest 3, (I'm not sure if it can pass systest even after using fast I/O)So for this contest I spend most of my time optimizing slow pyhon solution.From next contest, I'll use faster language, goodbye beautiful Python! Hello div2 :D
 » 5 years ago, # |   0 this round is hard but interesting.what is the solution of Div2E,Div1C ?
 » 5 years ago, # |   0 How to solve Div 2B?
•  » » 5 years ago, # ^ |   +4 Bubble sort is the easiest way — just swap two neighbours, and there will be no more than n*(n-1)/2 swaps (approx 5000) so it should pass every test.
•  » » 5 years ago, # ^ |   0 You can just sort the animals with bubble sort, and just print all the swaps you do. Since bubble sort has complexity n^2 it is guaranteed to do no more than n^2 swaps. From the constraints of the problem, the maximum value for n is 100, so the bubble sort will do at most 10000 swaps (less than that really, but it doesn't matter). So you are always guaranteed to make less than 20000 swaps.
 » 5 years ago, # |   +16 Submitted at the last minute with this for div1 E...  for( int i = 0 ; i < q ; i ++ ) puts( ans[ i ] ? "YES" : "NO" ); It should be "Yes"/"No" instead of "YES"/"NO"....
•  » » 5 years ago, # ^ |   +3 Isn't checker case-insensitive? I think it is by default. Are you sure you get correct answers on sample tests, besides case?
•  » » » 5 years ago, # ^ |   +35 The checker is case-insensitive for a single yes-no. For a sequence of Yes\No wcmp is used, and it's not case-insensitive.
•  » » » » 5 years ago, # ^ |   +18 Can this be made case-insensitive? Such inconsistency is a bit confusing.
•  » » » » » 5 years ago, # ^ |   0 Testlib checkers' home is here. Perhaps one can combine yesno and fcmp/wcmp, and then propose a pull request to add it to the default checkers? Or just make a case-insensitive fcmp/wcmp version.
•  » » » » » » 5 years ago, # ^ |   0 Nothing that I have against it, but I sometimes wonder why problem setters not have binary values as output (0/1) instead of ("YES/NO", "ALICE/BOB") etc.
•  » » » » » » » 5 years ago, # ^ |   +5 Are you saying 0/1 is better than Alice/Bob? How? The former one needs explaining in the statement, the latter doesn't.
•  » » 5 years ago, # ^ |   0 So would you have got AC if you hadn't made this mistake?
•  » » » 5 years ago, # ^ |   0 Fortunately, Nope. It got TLE with time complexity O(NM).However, I still get AC with another O(NM) solution which has less constant.
 » 5 years ago, # |   +7 Yeah, Div2C/Div1A had a really bad english problem statement. I managed to understand it, but it must have been hard for some contestants whose first language is not english.
 » 5 years ago, # | ← Rev. 2 →   +4 The pretests were too strong. I didn't see any hack during the contest.
•  » » 5 years ago, # ^ |   +1 Yeah. But I have nothing to complain. I would have failed in two problems if they were weak. LOL
 » 5 years ago, # |   0 Anyone stuck on pretest 4 in Div 2 C ? If passed some test cases please ...
•  » » 5 years ago, # ^ |   +4 check for n=1 or m=1 case
•  » » » 5 years ago, # ^ |   0 thanks
•  » » 5 years ago, # ^ |   0 You may also want to check for n = 7^3 and m = 7^4, or 1 and 7^7
 » 5 years ago, # |   +10 Why Div1E's Time limit were set too strict?
•  » » 5 years ago, # ^ |   +15 Maybe intended solution is O(N2 + M)
•  » » » 5 years ago, # ^ |   +5 I don't think so. And I agree that it is too strict.
•  » » » » 5 years ago, # ^ |   +31 If it's really O(NM) it becomes very easy, strict, stupid problem
 » 5 years ago, # |   0 English is not my native language, for problem DIV2 D / DIV1 B what does "Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)." means?
•  » » 5 years ago, # ^ |   +2 Take a node in a tree. Remove it. You get some disconnected components (corresponding to the edges the node had). If none of these components contains more than half of the original tree, that node is a centroid.
•  » » 5 years ago, # ^ |   +1 If a tree has n nodes, then the centroid of that tree is a node such that when you remove that node (and its edges), the remaining graphs that are left from the tree all have at most n/2 nodes.
 » 5 years ago, # |   +38 OMG!!! 2 weeks ago on a Xellos's SRM hard problem was like "count centroid for every subtree and do something easy". Today's problem B was "count centroid for every subtree". On that SRM I did that problem and took 4th place, so I simply copy-pasted my code and printed computed centroids, but I got TLE on 14th test. After few tries of optimizing constant I thought that there is probably something wrong with the idea and maybe I was just lucky on SRM, because maybe proof of time amortization was not right. I thought that one of authors saw my description in the discussion of that SRM, found a counterexample and thought it is a good idea to give that as a problem on CF. That would be perfectly cruel, right :P? However it turned out, that I got that incredibly idiotic piece of code auto UpperTree = [&](int guy) { int upper_tree = sz[v] - 1; for (auto s : sons[guy]) { upper_tree -= sz[s]; } return upper_tree; }; computing number of vertices outside guy's subtree when restricted to v's subtree, whereas it should have simply returned sz[v] — sz[guy] --__--. I'm such a moron xd. On SRM that code passed because input was given by a random number generator there. "Broom test" obviously makes my solution TLE here. However that code was written at ~4AM, maybe that could be forgiven xD.
•  » » 5 years ago, # ^ |   +33
•  » » 5 years ago, # ^ |   +26 Shit, looks like I have to start competing in SRM again (
•  » » » 5 years ago, # ^ |   -11 Можете проверить у меня задача А отправилось 2 раза? 18677724 и 18677705
•  » » 5 years ago, # ^ |   +8 Wow, you're red and you can't handle broom test in tree problems. I totally did the same thing during the round
•  » » » 5 years ago, # ^ |   0 On Petrozavodsk camp there was a problem where many contestants had got AC even though broom test would have made almost all of them TLE :P.
•  » » » » 5 years ago, # ^ |   0 What is broom test? I couldn't find what it means
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +27 In that case: parent[i] = min(i - 1, n / 2)
•  » » » » » » 5 years ago, # ^ |   +5 Wow, I've should understand from "broom" xd
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 It's not like we didn't have a problem in a rated contest in which the editorial solution used to TLE on broom test :PEdit: I now see they changed the editorial to the official solution, which is correct :)
 » 5 years ago, # | ← Rev. 2 →   0 My E is still in queue :oEdit: It is judged now.
 » 5 years ago, # |   +25 Why does systest always get stuck on 100%?
•  » » 5 years ago, # ^ |   0 I think that's to eliminate the cases of cheating.
•  » » 5 years ago, # ^ |   +20 that's called suspense
 » 5 years ago, # |   +6 What I did for Div 2-D (Div 1-B) got Accepted, but it took 2 seconds and I'm having a hard time analyzing the time complexity.I computed centroids bottom up. So for current node u, if it is a centroid of the subtree rooted at u, great, else set the current node to the centroid of the largest subtree of the current node. While the current node isn't the required centroid, go to either the centroid if its largest subtree, or to its parent depending on which direction the centroid should lie (using sizes).I precomputed the largest subtree and the size of the subtree for each node in O(n) in advance.Can someone estimate the time complexity of this solution? Thanks a lot.
•  » » 5 years ago, # ^ |   +5 You're visiting every node at most 2 times. First time when computing it's answer, second time when testing it for another node's answer. (Assuming that you're breaking the loop that goes up after finding the centroid). 2*n -> O(n)
•  » » » 5 years ago, # ^ |   0 Hi,Sorry I didn't completely understand. Could you give me an intuitive reason why a node will only be tested once for another node's answer?
•  » » 5 years ago, # ^ |   +11 I did the same, it's O(N), surprisingly.Consider the paths formed by only taking the edges from each parent to its largest subtree child. These are the paths where you'll be "moving the centroids upwards", so to speak, so that part is O(number of edges) = O(N), and the rest are simple — e.g. finding the child with the largest subtree is also O(number of edges) = O(N).
•  » » » 5 years ago, # ^ |   0 Hi,Sorry I didn't really understand why those particular edges (connecting a node to its largest subtree) will be the only ones where I'll move centroids upwards. Also, why would each such edge be used only once?
•  » » » » 5 years ago, # ^ |   +6 My explanation was pretty bad actually :D It's kind of hard to explain though. But I'll try again in more detail.The centroid of a tree is always either its root or some node in its largest child subtree. If it's the latter, it's always the root of the subtree or in the largest "sub-subtree" of that subtree and so on. Therefore, when you want to calculate the centroid of a tree and you start "moving" the centroid of its largest subtree upwards, you're always following such "largest-subtree-edges", so to speak.As for why they each occur only once: Imagine taking the leaf, then following these edges upwards, each time calculating the centroid of subtree rooted at your current position. Since you're following these "largest-subtree-edges", at each step, you're going to adjust the previous subtree's centroid by moving it upwards. And you never move it down. So the only situation when you have to examine the possible movement of the centroid on the same edge multiple times is when you have chosen not to move it previously. But when you don't move the centroid, you finish calculating it for the current subtree, so there can be no more than N non-moving examinations. And each moving examination looks at a different edge, so there are also no more than N of those. All in all, it's O(N) checks!Phew, that was hard to clear rigorously... Hope it helped somewhat.
•  » » » » » 5 years ago, # ^ |   0 Thanks a lot!I understand why the complexity is O(N) now.Is it right then, that my second check (searching for the centroid further down) was unnecessary as the centroid can only move up (after initially setting it to the centroid of the largest subtree)?
•  » » » » » » 5 years ago, # ^ |   +3 Indeed, you're right :)
•  » » » » » » 5 years ago, # ^ |   +3 Yes. You're adding more nodes to the subtree at its top, so the centroid is going to move upwards, intuitively. (Unless you add so many nodes to the top that the previous subtree is not even the largest, in which case you'd pick a different child of the new root and you're never going to visit this subtree again.)
 » 5 years ago, # |   -17 I think there should be atleast one problem with weak pretests. Otherwise there is no meaning of keeping the hacking feature.
 » 5 years ago, # |   +23 Why Div1-C's points are 1250???? I think this problem is very hard...
 » 5 years ago, # |   +114
 » 5 years ago, # |   +13 It looks perfect when there are no fakes in div2 top
 » 5 years ago, # |   +22 I bet tourist will compete in next round!
 » 5 years ago, # |   0 Well Div2C is quite a tricky problem. You just have to decrement n and m then start solving, it is mentioned (numbers from 0 to n — 1/m — 1) And when converting a number to base 7 just make sure that you are considering the case of 0. I couldn't solve it in contest because of those two bugs.
 » 5 years ago, # | ← Rev. 2 →   0 Can somebody show me just one valid pair for div2C TC11: 16808 7 ?I just can't understand how there are 720 valid pairs
•  » » 5 years ago, # ^ |   +1 012345:6
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 ohhh, I thought we should take 2 places for 7but we need only 1 place for 7-1 = 6
•  » » » 5 years ago, # ^ |   0 Quite tricky :(,
 » 5 years ago, # |   +70 congratulations for the first Arabic/Egyptian Grandmaster TsunamiNoLetGo
•  » » 5 years ago, # ^ |   +11 Thanks :)
 » 5 years ago, # | ← Rev. 2 →   0 Why do I get WA (=5040) for my submission 18687880 for test case 7 (problem C)344 344whereas on my compiler and ideone I get the correct answer = 0.Any help is appreciated.
•  » » 5 years ago, # ^ |   0 log is at fault here.
•  » » » 5 years ago, # ^ |   0 fault where, at the CF server?
•  » » » » 5 years ago, # ^ |   +7 No, the log function (and floating point computation in general) is only an approximation. They do their best to implement the closest answer, but they are not necessarily exact. For example, in your solution, you have int(tmp), where tmp is a double. This simply truncates tmp (it does not round it). So if tmp=24.999999.., it would simply be truncated to 24 instead of giving the exact answer of 25 as you would expect.The take home message is to not use floating point computations unless you actually need to. If you have to use them, you should always check that no significant errors have occurred. Here are some common functions that lots of people mess up on: pow, sqrt, fabs, log.
 » 5 years ago, # |   0 Can anyone help me debug this?This solution got accepted http://codeforces.com/contest/686/submission/18688448 And this got Wrong Answer: http://codeforces.com/contest/686/submission/18688414However, the only change I made was comparing the subtrees of the centroid pretender and the current node, at line 28. This shouldn't change the program's behaviour. I'm following this solution: http://codeforces.com/blog/entry/45556?#comment-301968
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 sub[cur] - sub[cen[cur]] > sub[cur]/2 and sub[cen[cur]] < sub[cur]/2are not equal because sub[cur]/2 will round down. For example, lets say sub[cur] is 3 and sub[cen[cur]] is 1. 3 - 1 > 3 / 2 is true while 1 < 3 / 2 is false.
•  » » » 5 years ago, # ^ |   0 Thanks, it works declaring sub and msub as double. Didn't think this would affect.
•  » » 5 years ago, # ^ |   0 Hi,Not sure, but I think that in the second submission, your condition sub[cen[cur]] < sub[cur]/2 should use a <= sign?
•  » » » 5 years ago, # ^ |   0 Actually not. If it compares equal, the candidate is necessarily a centroid, as there would be a subtree with n/2 nodes and another (or more than one) with n/2-1 nodes.
 » 5 years ago, # |   +20 Is Petr going to cross tourist next time?????? Or tourist is gonna come back to defend the title???????????????? Keep watching on Codeforces!!!!!!!!!!! Yayyyyyyyyyyyyyyy :D
•  » » 5 years ago, # ^ |   +88 I think your keyboard may be broken. Some keys keep getting stuck.
 » 5 years ago, # | ← Rev. 3 →   -20 The "optimal point" problem only uses well known school topics.You needed to know how to expand module inequalities:|x - x1| ≤ A if and only if x1 - A ≤ x ≤ x1 + A.And then notice the simple replacement of variables.Very surprised about number of Ac's.
•  » » 5 years ago, # ^ |   0 I don't think you can do anything with it in this problem. Did you get accepted?
•  » » » 5 years ago, # ^ |   +18 He is author btw
•  » » » » 5 years ago, # ^ |   +72 But did he get accepted? :D
•  » » » » 5 years ago, # ^ |   +5
•  » » 5 years ago, # ^ |   -16 Unfortunately, this is not clear enough. And the fact that you don't have the editorial makes it look even worse.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 The editorial is been prepared, please wait.UPD. It is here: http://codeforces.com/blog/entry/45558
•  » » » 5 years ago, # ^ |   0 We don't have the editorial yet but we are working on this issue...
•  » » 5 years ago, # ^ |   +25 Measuring difficulty in terms of required knowledge is not a good idea. If you measure difficulty that way then why did you set E as E :)? Indeed this problem doesn't require sophisticated knowledge and I got a right idea pretty quickly, but got a hard time figuring out the details and carefully implementing it (at which I failed). And as already pointed out what you have said does not seem to be sufficient to describe main idea. However maybe there is some significantly easier solution than those I already know.
 » 5 years ago, # |   0 In Codeforces Round #359 (Div. 2) Problem 686B - Little Robber Girl's Zoo sample test cases Outputs were wrong. Correct me if i am wrong.
•  » » 5 years ago, # ^ |   +6 If it was wrong, how can 1000 users solve it?
•  » » » 5 years ago, # ^ |   -11 If it was right then check outputs of 18671047 . I am talking about sample testcases. Take a look at written outputs in sample testcases of problem and outputs of the submission (which has been accepted) .
•  » » » » 5 years ago, # ^ |   -8 Test case output is correct.This problem allows to have multiple correct solutions.
•  » » » » » 5 years ago, # ^ |   -8 But it is not mentioned in English version.
•  » » » » » » 5 years ago, # ^ |   0 <> (C) statement.
•  » » » » » » » 5 years ago, # ^ |   +4 Ohh My mistake. I wish i had read that during contest time.Thank you for pointing out cdkrot. I had already solved that using Bubble sort but, i thought it is wrong since it was not matching with sample test cases.
•  » » » 5 years ago, # ^ |   0 As Written on problem : 4 2 1 4 3 Output of 18671047 1 2 3 4 `How can it become correct ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.
•  » » » » » 5 years ago, # ^ |   0 It was not mentioned in the Problem statement that "any solution" that minimize the number of operations will be accepted.
•  » » » » » » 5 years ago, # ^ |   0 Just scroll down to the notes section.
•  » » » » » » » 5 years ago, # ^ |   0 Got it, It was my mistake. I wish, i had noticed that during contest. Even after solving i didn't submitted because it was not matching with sample test cases.
 » 5 years ago, # |   +43 It would be nice if in some of these problems, you would provide a formal definition using mathematical symbols to avoid ambiguity."Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)."That isn't correct English. I think "at least two times smaller" is the main problem :(
 » 5 years ago, # |   +1 Editorial posted.